QoS-Aware Web Service Selection with Internal Complementarity

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

8 Scopus Citations
View graph of relations



Original languageEnglish
Pages (from-to)276-289
Journal / PublicationIEEE Transactions on Services Computing
Issue number2
Online published9 Aug 2016
Publication statusPublished - Mar 2019
Externally publishedYes


Service composition is a key enabling technology in service-oriented computing for developing versatile applications by integrating various existing interoperable services. Although actively studied, most existing works on service composition neglect the existence of complementarity among candidate services within a service class, so-called internal complementarity. In fact, complementary candidate services within a service class can be composed to form a composite candidate service which may yield better service utility than that provided by any existing candidate service within that service class. This work focuses on web service composition where internal complementarity is more likely to happen. Specifically, we aim at addressing the problem of QoS-aware web service selection with internal complementarity (WSS-IC). We first transform this problem into a multi-choice multi-dimensional knapsack problem (MMKP) and prove such a transformation per se has non-polynomial time complexity in the worse case.Then, we perform complexity analysis to demonstrate that existing approaches to MMKPs are not computationally feasible to resolve QoS-aware WSS-IC. This fact motivates us to propose an iteratively improving framework for deriving the solution iteration by iteration while taking into account both solution structure and QoS constraints. At each iteration, the current solution gets improved by solving a disjunctively constrained knapsack problem. To verify the effectiveness of the proposed framework, two heuristic approaches are implemented under this framework. Experimental results demonstrate that our approaches outperform the compared methods in terms of both solution quality and computation time. © 2008-2012 IEEE.

Research Area(s)

  • internal complementarity, iteratively improving framework, QoS-aware, service composition

Citation Format(s)

QoS-Aware Web Service Selection with Internal Complementarity. / Liang, Xinle; Qin, A. K.; Tang, Ke; Tan, Kay Chen.

In: IEEE Transactions on Services Computing, Vol. 12, No. 2, 03.2019, p. 276-289.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review