• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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

Type
Article accepté pour publication ou publié
Date
2015
Journal name
Discrete Applied Mathematics
Volume
196
Publisher
Elsevier
Pages
100-114
Publication identifier
10.1016/j.dam.2014.10.020
Metadata
Show full item record
Author(s)
Manouvrier, Maude cc

Gabrel, Virginie

Murat, Cécile
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 / Keywords
Web service composition; QoS; Workflow; Complexity; Series–parallel directed graph; Mixed integer linear program

Related items

Showing items related by title and author.

  • Thumbnail
    Web Services Composition : Complexity and models 
    Gabrel, Virginie; Murat, Cécile; Manouvrier, Maude (2013) Communication / Conférence
  • Thumbnail
    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
  • Thumbnail
    A new 0–1 linear program for QoS and transactional-aware web service composition 
    Gabrel, Virginie; Manouvrier, Maude; Murat, Cécile; Megdiche, Imene (2012) Communication / Conférence
  • Thumbnail
    QoS-aware automatic syntactic service composition problem: Complexity and resolution 
    Gabrel, Virginie; Manouvrier, Maude; Moreau, Kamil; Murat, Cécile (2018) Article accepté pour publication ou publié
  • Thumbnail
    A new linear program for QoS-aware web service composition based on complex workflow 
    Murat, Cécile; Manouvrier, Maude; Gabrel, Virginie (2013) Document de travail / Working paper
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo