Show simple item record

dc.contributor.authorGabrel, Virginie
dc.contributor.authorManouvrier, Maude
HAL ID: 182131
ORCID: 0000-0001-8878-058X
dc.contributor.authorMoreau, Kamil
dc.contributor.authorMurat, Cécile
dc.date.accessioned2017-11-27T13:32:20Z
dc.date.available2017-11-27T13:32:20Z
dc.date.issued2018
dc.identifier.issn0167-739X
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/17064
dc.language.isoenen
dc.subjectService composition
dc.subjectWeb Service Challenge
dc.subjectAND/OR constraints
dc.subjectQoS optimization
dc.subject.ddc004en
dc.titleQoS-aware automatic syntactic service composition problem: Complexity and resolution
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenAutomatic syntactic service composition problem consists in automatically selecting services, from a registry, by matching their input and output data. The composite service, resulting from this selection, allows producing a set of output data, needed by a user, from a set of input data, given by the user. Adding Quality-Of-Service (QoS) values for each service (for example execution time and cost values), this selection problem becomes an optimization one called the QoS-aware automatic syntactic service composition problem. Depending on the QoS criterion used, many models and algorithms resolving the aforementioned problem are proposed in the literature. The aim of this article is twofold. Firstly, we provide a unified understanding of the wide variety of existing approaches and we analyse and compare the theoretical complexity induced by each QoS criterion. We state that optimal solution for execution time or throughput QoS criteria can be determined in polynomial time but optimality is no more guaranteed in polynomial time for QoS criteria like cost or reliability. Indeed, we show that the composition problem becomes NP-hard when optimizing such QoS criteria. Secondly, we propose a novel approach for solving more efficiently polynomial cases. This approach is based on a scheduling formulation with AND/OR constraints, using a directed graph structure. For the Web Service Challenge-09 benchmark (considering execution time and throughput QoS criteria), our exact algorithm outperforms the related work.
dc.relation.isversionofjnlnameFuture Generation Computer Systems
dc.relation.isversionofjnlvol80
dc.relation.isversionofjnldate2018
dc.relation.isversionofjnlpages311-321
dc.relation.isversionofdoi10.1016/j.future.2017.04.009
dc.subject.ddclabelInformatique généraleen
dc.relation.forthcomingouien
dc.relation.forthcomingprintouien
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2018-01-08T10:42:39Z


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