Résumé en anglais

This paper addresses the QoS-aware service selection problem considering complex workflow patterns. More specifically, it focuses on the complexity issues of the problem. The NP-hardness of the problem, under various settings, has been open for many years and has never been addressed thoroughly. We study the problem complexity depending on the workflow structure, the number of workflow tasks, the number of alternative services per task and the categories of quality of service criterion associated to services. We provide for the first time the NP-hardness proof of the problem. Additionally, we show that the problem is polynomial in case of only one criterion per task and pseudo-polynomial if there is a fixed number of criteria.