• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Web services composition: Complexity and models

Thumbnail
Date
2015
Dewey
Programmation, logiciels, organisation des données
Sujet
Web service composition; QoS; Workflow; Complexity; Series–parallel directed graph; Mixed integer linear program
Journal issue
Discrete Applied Mathematics
Volume
196
Publication date
2015
Article pages
100-114
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.dam.2014.10.020
URI
https://basepub.dauphine.fr/handle/123456789/15516
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Manouvrier, Maude
Gabrel, Virginie
Murat, Cécile
Type
Article accepté pour publication ou publié
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.