A multi-hierarchy particle swarm optimization-based algorithm for cloud workflow scheduling

In this paper, we consider the market-driven workflow scheduling problem on heterogeneous cloud resources with deadline constraints. The transmission delay between dependent tasks on different virtual machines (VMs) is considered. The objective is to minimize the total monetary cost, which is computed based on the on-demand price structure. Inspired by the heuristic and meta-heuristic algorithms, a multi-hierarchy particle swarm optimization (MHPSO) algorithm is proposed, which mainly consists of three components: (1) the workflow aggregation method to pretreat the workflow structure considering the transmission cost and the VM utilization; (2) the initial population generating method to create a set of initial particles with the given encoding method and the solution generation method; and (3) the hierarchical evolving process where particles are divided into multiple groups and evolved iteratively. We calibrate the parameters and components of the proposal statistically over five well-known workflows with different deadline settings. A comparison of the proposed algorithm to existing methods for the considered problem is carried out. Experimental results demonstrate the proposal is effective for the problem under study.