Decomposition-based multi-objective evolutionary algorithm for virtual machine and task joint scheduling of cloud computing in data space

Efficient Virtual Machine (VM) placement and task scheduling is considered a major challenge in cloud computing, given that the scheduling results directly affect user satisfaction and vendor benefits. This paper investigates the VM and task joint scheduling (VTJS) problem, and establishes a multi-objective mathematical model with the aim to minimize makespan, cost, and total tardiness. To solve this problem, a problem -specific three-layer encoding approach is designed, and a decomposition-based multi-objective evolutionary algorithm with pre-selection and dynamic resource allocation (MOEA/D-PD) is proposed, in which a customized two-stage guided local search method is also embedded. In MOEA/D-PD, a classifier model is built to filter the offspring solutions in decision space so that only promising solutions are evaluated, and computational resources are dynamically allocated to the subproblems on the bases of their contributions. The proposed algorithm is validated on a series of instances of different scales and compared with six state-of-the-art MOEAs. Experimental results show that the proposed algorithm outperforms the most known approaches from the literature.

Automated summary

This paper investigates the VM and task joint scheduling problem and proposes a multi-objective mathematical model to optimize makespan, cost, and total tardiness. A problem-specific three-layer encoding approach is designed and a decomposition-based multi-objective evolutionary algorithm with pre-selection and dynamic resource allocation (MOEA/D-PD) is proposed. Experimental results show that the proposed algorithm outperforms existing approaches in the literature.