Minimum cost service composition in service overla

Authors: Jin Wang Jianping Wang Biao Chen Naijie Gu

Publish Date: 2010/09/04

Volume: 14, Issue: 1, Pages: 75-103

PDF Link

Abstract

In service computing it is often desirable to find the service composition solution for a given service composition request such that the total cost of the service composition solution is minimized In this paper we study the problem of finding the minimum cost service composition MCSC for a general service composition request which is represented by a directed acyclic graph DAG We first prove that the general case of the MCSC problem is NPHard We then show that optimal solutions can be found in polynomial time for some special structured service composition requests To this end we derive a sufficient condition on the service composition request graph and propose corresponding algorithms to find the optimal solutions in polynomial time Using such algorithms as building blocks we propose heuristic algorithms to decompose the general service composition request graph into service composition request subgraphs with optimal structures Simulation results demonstrate the effectiveness of the proposed heuristic algorithms

Keywords: