Hybrid Algorithm on Timeline Matrix for Task Scheduling in Clouds

In recent years, cloud computing is an emerging industry that serves many people who do not own sufficient compute resources in a flexible and efficient approach. However, it is difficult to optimize the cost of computing while meeting the QoS requirements of users, especially for those time-constrained workflows. In this article, we present a hybrid particle swarm optimization (PSO) scheduling algorithm, called HPSOTM, which aims to optimize the scheduling strategy of workflows while meeting deadline constraints in a cloud environment. In HPSOTM, a more suitable and refined optimization and solution-repair strategy is constructed for the timeline matrix of the virtual machine pool to improve the efficiency. At the same time, it also enriches the diversity of solutions in particle swarms and improves the convergence speed of feasible solutions. It mainly contains two major highlight features: 1) design a new slot-aware rule to reduce VM idle time, which could reduce execution costs; 2) apply the concept of partial critical path to complete deadline distribution, which could fit to time constraints precisely. Extensive experiments are conducted and the results show that the proposed algorithm outperforms other existing algorithms that minimize the execution cost of scheduling workflows with deadline constraints.