An adaptive decoding biased random key genetic algorithm for cloud workflow scheduling

With the ever-growing data and computing requirements, more and more scientific and business applications represented by workflows have been moved or are in active transition to cloud platforms. Therefore, the cloud workflow scheduling has become a hot topic. As a well-known NP-hard problem, many heuristic or metaheuristic algorithms/methods have been proposed. However, the heuristic method is problem-dependent which fits only a particular of problems, while the metaheuristic method has the problems of incomplete search space or low search efficiency in the complete space. To fill these gaps, a novel adaptive decoding biased random key genetic algorithm for cloud workflow scheduling is proposed. In this algorithm, the improved real number coding based on random key with limited value range is employed, and some novel schemes such as the population initialization based on level and heuristics including dynamic heterogeneous earliest finish time, the dynamic adaptive decoding, the load balance with communication avoidance and iterative forward–backward scheduling are designed for population initialization, chromosome decoding and improvement. To evaluate the performance, extensive experiments have been conducted on various real and random workflow applications, which demonstrates that the proposed algorithm outperforms the conventional approaches.

Authors

• Yi Xie Department of Electrical & Computer Engineering, University of Arizona Tucson, Arizona, USA
• Yuhan Sheng
• Moqi Qiu
• Fengxian Gui

Keywords

• Workflow
• Genetic algorithm
• Scheduling
• Cloud computing
• Makespan