Show simple item record

hal.structure.identifier
dc.contributor.authorManouvrier, Maude
HAL ID: 182131
ORCID: 0000-0001-8878-058X
*
hal.structure.identifier
dc.contributor.authorGabrel, Virginie*
hal.structure.identifier
dc.contributor.authorMurat, Cécile*
dc.date.accessioned2016-06-03T15:16:27Z
dc.date.available2016-06-03T15:16:27Z
dc.date.issued2015
dc.identifier.issn0166-218X
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/15516
dc.language.isoenen
dc.subjectWeb service composition
dc.subjectQoS
dc.subjectWorkflow
dc.subjectComplexity
dc.subjectSeries–parallel directed graph
dc.subjectMixed integer linear program
dc.subject.ddc005en
dc.titleWeb services composition: Complexity and models
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenA 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.
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol196
dc.relation.isversionofjnldate2015
dc.relation.isversionofjnlpages100-114
dc.relation.isversionofdoi10.1016/j.dam.2014.10.020
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2016-09-27T09:32:59Z
hal.identifierhal-01326521*
hal.version1*
hal.update.actionupdateFiles*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record