%0 Journal Article %1 RySw2010-SS %A Rygielski, Piotr %A Światek, Pawel %C Wroclaw, Poland %D 2010 %I Wroclaw University of Technology Press %J Systems Science %K Optimization SOA descartes t_journalmagazine %N 3 %P 25--32 %T Graph-fold: an Efficient Method for Complex Service Execution Plan Optimization %U http://linksource.ebsco.com/linking.aspx?issn=0137-1223&volume=36&spage=25 %V 36 %X The task of optimization of the complex service execution plan is the last stage of the process of complex services composition in systems based on the SOA paradigm. In general this task consists of choosing proper versions of atomic services, delivering requested functionalities, such that non-functional requirements for complex service are satisfied. In most real-life cases this task is reduced to the problem of multidimensional knapsack problem (MKP), which is known to be NP-hard. Therefore, in order to facilitate effective complex service composition, it is crucial to provide an efficient MKP solution algorithm. In this paper a novel approach to the problem of optimization of complex service execution plan is introduced. In the proposed approach the MKP feasible solution space is constructed in such a way, that the optimal solution can be found in constant time. Of course, since MKP is NP-hard, the process of solution space construction takes an exponential time, This time, however, is amortized by multiple usages of single solution space for determination of optimal execution plans for multiple complex service requests.

@article{RySw2010-SS, abstract = {The task of optimization of the complex service execution plan is the last stage of the process of complex services composition in systems based on the SOA paradigm. In general this task consists of choosing proper versions of atomic services, delivering requested functionalities, such that non-functional requirements for complex service are satisfied. In most real-life cases this task is reduced to the problem of multidimensional knapsack problem (MKP), which is known to be NP-hard. Therefore, in order to facilitate effective complex service composition, it is crucial to provide an efficient MKP solution algorithm. In this paper a novel approach to the problem of optimization of complex service execution plan is introduced. In the proposed approach the MKP feasible solution space is constructed in such a way, that the optimal solution can be found in constant time. Of course, since MKP is NP-hard, the process of solution space construction takes an exponential time, This time, however, is amortized by multiple usages of single solution space for determination of optimal execution plans for multiple complex service requests.}, added-at = {2020-04-05T23:15:38.000+0200}, address = {Wroclaw, Poland}, author = {Rygielski, Piotr and {\'S}wi\k{a}tek, Pawel}, biburl = {https://www.bibsonomy.org/bibtex/2c93b60ff744feb3bff9c611009d80e1c/se-group}, interhash = {383136716ce4afd0e9f58a71fb9ed86d}, intrahash = {c93b60ff744feb3bff9c611009d80e1c}, journal = {Systems Science}, keywords = {Optimization SOA descartes t_journalmagazine}, number = 3, pages = {25--32}, publisher = {Wroclaw University of Technology Press}, timestamp = {2020-10-07T11:44:17.000+0200}, title = {{Graph-fold: an Efficient Method for Complex Service Execution Plan Optimization}}, url = {http://linksource.ebsco.com/linking.aspx?issn=0137-1223&volume=36&spage=25}, volume = 36, year = 2010 }