Since the birth of web service composition, minimizing the number of web services of the resulting composition while satisfying the user request has been a significant perspective of research. With the increase of the number of services released across the Internet, seeking efficient algorithms for this research is an urgent need. In this paper we present an efficient mechanism to solve the problem of web service composition. For the given request, a service dependency graph is firstly generated with the relevant services picked from an external repository. Then, each search step on the graph is transformed into a dynamic knapsack problem by mapping services to items whose volume and cost is changeable, after which a knapsack-variant algorithm is applied to solve each problem after transformation. Once the last search step is completed, the minimal composition that satisfies the request can be obtained. Experiments on eight public datasets proposed for the Web Service Challenge 2008 shows that the proposed mechanism outperforms the state-of-the-art ones by generating solutions containing the same or smaller number of services with much higher efficiency.
A scalable and approximate mechanism is presented in @cite_16 to get the near-minimal compositions against time. The authors proposed an on-the-fly strategy to construct only a path of the auxiliary graph instead of the complete graph. Additionally, a deterministic approach and a probabilistic approach are discussed to find the path with the minimal number of services, which is the final result of composition. Though the algorithm has a superior service composition time compared to other algorithms, the greedy strategy adopted always gets stuck in local optima. As a result, it always generates compositions with more services than the others. In a word, it performs well in efficiency but it remains to be improved in terms of the quality of solutions.
@cite_16
1576894720
In recent times, automated business processes and web services have become ubiquitous in diverse application spaces. Efficient composition of web services in real time while providing necessary QoS guarantees is a computationally complex problem and several heuristic based approaches have been proposed to compose services optimally. In this paper, we present the design of a scalable but approximate QoS-aware service composition mechanism which balances the computational complexity of service composition with the QoS guarantees of the composed service and achieves scalability for dynamic service composition. We present experimental results to show the efficiency of our proposed mechanism.