Abstract

Automatic Service Composition (ASC) is the generation of a business process to fulfill business goals that cannot be fulfilled by individual services. Planning algorithms are frequently used to solve this problem. In addition to satisfying functional goals, recent research is geared towards selecting the best services to optimize the QoS of the business process results. It is a challenge to fulfill functional goals and achieve QoS optimization at the same time.

In this thesis, we propose to combine a planning algorithm called GraphPlan, with a systematic search algorithm like Dijkstra's algorithm to achieve functional goals and QoS optimization at the same time. The GraphPlan algorithm has the advantages of easily modeling business logic, reusing the actions in one plan, and planning parallel actions in a plan. The planning graph generated by the GraphPlan algorithm is a compact representation of all execution paths, which makes it feasible to apply Dijkstra's principle. Two methods have been proposed to combine the Graphplan with Dijkstra's algorithm.

In the first method, we extend Dijkstra's algorithm from working on a single source graph to working on the extended planning graph whose nodes have multiple sources. The advantage of this method is that it gets an optimal plan with the best QoS value for the single criteria of throughput or response time in polynomial time. However, this method does not provide a uniform graph structure (\ie an extended planning graph with single or multiple tag, to generate an optimal plan for all kinds of quality criteria).

In the second method, we improve the idea of combining the Graphplan with Dijkstra's algorithm by providing a uniform graph structure to generate a QoS optimal solution for all kinds of quality criteria. A Layered Weighted Graph (LWG) is generated and provides a uniform structure for the easy use of Dijkstra's algorithm to find an optimal plan for all kinds of quality criteria. By using multi-objective shortest path algorithms, this method can be easily extended to solve QoS optimization on multiple QoS criterion for service composition problem.

In this thesis, we also study redundant service removal to further optimize QoS optimal solutions. The removal of redundant services does not worsen the QoS value of the optimal solution. Fewer numbers of services indicates less execution costs to invoke these services. A redundant service removal problem is modeled as an optimization problem such that the optimal solution without redundancy is found.