QoS-aware automatic syntactic service composition problem: Complexity and resolution

Automatic 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.