Critical-Task-Driven Multi-Objective Evolutionary Algorithm for Scheduling Large-Scale Workflows in Cloud Computing

Simultaneously optimizing energy consumption and makespan is essential for deploying workflows on cloud platforms. Meanwhile, it poses various challenges, such as multiple types of decision variables and large-scale decision variables. Until now, some studies have adopted multi-objective evolutionary optimization techniques to handle these challenges. But, most relevant studies regard the optimization problem as a black box and do not fully explore the domain knowledge to strengthen the search efficiency. To further answer the above challenges, this study tailors a critical-task-driven evolutionary algorithm, namely CTMOEA, to optimize both energy consumption and makespan by evolving two types of decision variables: 1) mappings from tasks to resources; and 2) task runtime. In particular, an adaptive incentive mechanism is designed to distinguish decision variables with higher criticality and allocate more computing resources to evolve them, thus handling large-scale decision variables in a targeted manner. Moreover, a critical task remapping mechanism is designed to adaptively remap critical tasks onto the same resources as their successor tasks to eliminate data transfer time between them, thus pursuing a simultaneous reduction in energy consumption and makespan. At last, based on 16 real-world workflow traces, we validate the superior overall performance of the proposed CTMOEA by significantly outperforming five baselines on 13 test instances. Also, we conduct an ablation analysis to demonstrate the contributions of the three problem-specific mechanisms to overall performance.