Abstract: With the development of web services, the dynamic composition technique of web service provides a new solution to solve the problem of information sharing and the application cooperating.However, generating the composition plan to meet QoS requirement of client is a time-consuming optimization problem.To solve the problem in a timely manner, this paper presents a heuristic method based on A-star algorithm by modeling the Qos-drived dependency graph.The algorithm can be applied to the situation with multi-inputs to generate a simpler calling sequence with lowest cost.The experiment shows that our method has good efficiency.