Abstract: The quality of service (QoS)-aware web service composition problem is a research hotspot. Its objective is to select a composite service which can maximizes the QoS utility while preserving QoS constraints. By giving the definition of usual workflow and the combination rule of virtual tasks, a top-k based web service composition approach is proposed. Its core idea is to transform the original workflow into a virtual task by recursively calling the combination rule of virtual tasks. Moreover, a new scheme is presented to select suitable replaceable services to support the self-healing property. The effectiveness of the k value and the performances of algorithms are analyzed through simulation experiments.