An adaptive decoding biased random key genetic algorithm for cloud workflow scheduling. (June 2022)

• Record Type: Journal Article
• Authors: Xie, Yi; Sheng, Yuhan; Qiu, Moqi; Gui, Fengxian
• Is Part Of: Engineering applications of artificial intelligence. Volume 112(2022)
• Publication Date: 2022-06
• Subjects: Workflow -- Genetic algorithm -- Scheduling -- Cloud computing -- Makespan; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2022.104879
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: 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. Highlights: Propose a novel genetic algorithm for cloud workflow scheduling. Use real number coding and dynamic adaptive decoding to improve efficiency. Use level and heuristics including the DHEFT for a good initial population. Use load balance and forward and backward scheduling to improve individual. Verify the effectiveness of our algorithm by extensive experiments.