@article{XU2010, 
author = {Bin XU and Sen LUO and Yixin YAN},
title = {Efficient Composition of Semantic Web Services with End-to-End QoS Optimization},
year = {2010},
journal = {Tsinghua Science and Technology},
volume = {15},
number = {6},
pages = {678-686},
keywords = {semantic web service, web service composition, QoS, optimization},
url = {https://www.sciopen.com/article/10.1016/S1007-0214(10)70115-2},
doi = {10.1016/S1007-0214(10)70115-2},
abstract = {The efficiency of QoS-aware service composition is important since most service composition problems are known to be NP-hard. With the growing number of web services, service composition is like a decision problem on selecting services or/and execution plans to satisfy the users' end-to-end QoS requirements (e.g. response time, throughput). Composite services with the same functionality may have different execution plans, which may cause different end-to-end QoS. This paper presents a model combining semantic data-links and QoS, which leads to an efficient approach to automatic construction of a composite service with optimal end-to-end QoS. The approach is based on a greedy algorithm to select both services and execution plans for composite services. Empirical and theoretical analyses of the approach show that its time complexity is O(mn2) for a repository with n services and an ontology with m concepts. Moreover, the approach increases linearly in time when using an index to search services in the repository. Tests with a repository with 20000 services and an ontology with 300000 concepts show that the algorithm significantly outperforms current existing algorithms in terms of composition efficiency while achieving optimal end-to-end QoS.}
}