Web services composition: Complexity and models
Manouvrier, Maude; Gabrel, Virginie; Murat, Cécile (2015), Web services composition: Complexity and models, Discrete Applied Mathematics, 196, p. 100-114. 10.1016/j.dam.2014.10.020
TypeArticle accepté pour publication ou publié
Journal nameDiscrete Applied Mathematics
MetadataShow full item record
Abstract (EN)A web service is a modular and self-described application callable with standard web technologies. A workflow describes how to combine the functionalities of different web services in order to create a new value added functionality resulting in composite web service. QoS-aware web service composition means to select a composite web service that maximizes a QoS objective function while satisfying several QoS constraints (e.g. price or duration). The workflow-based QoS-aware web service composition problem has received a lot of interest, mainly in web service community. This general problem is NP-hard since it is equivalent to the multidimensional multiple choice knapsack problem (MMKP). In this article, the theoretical complexity is analysed more precisely in regard to the property of the workflow structuring the composition. For some classes of workflows and some QoS models, the composition problem can be solved in polynomial time (since the workflow is a series–parallel directed graph). Otherwise, when there exist one or several QoS constraints to verify, the composition problem becomes NP-hard. In this case, we propose a new mixed integer linear program to represent the problem with a polynomial number of variables and constraints. Then, using CPLEX, we present some experimental results showing that our proposed model is able to solve big size instances.
Subjects / KeywordsWeb service composition; QoS; Workflow; Complexity; Series–parallel directed graph; Mixed integer linear program
Showing items related by title and author.
Gabrel, Virginie; Murat, Cécile; Manouvrier, Maude (2013) Communication / Conférence
Optimal and Automatic Transactional Web Service Composition with Dependency Graph and 0-1 Linear Programming Gabrel, Virginie; Manouvrier, Maude; Murat, Cécile (2014) Communication / Conférence
Gabrel, Virginie; Manouvrier, Maude; Murat, Cécile; Megdiche, Imene (2012) Communication / Conférence
Gabrel, Virginie; Manouvrier, Maude; Moreau, Kamil; Murat, Cécile (2018) Article accepté pour publication ou publié
Murat, Cécile; Manouvrier, Maude; Gabrel, Virginie (2013) Document de travail / Working paper