Knowledge-driven adaptive evolutionary multi-objective scheduling algorithm for cloud workflows

Workflow scheduling in cloud platforms is a highly challenging issue because it faces multiple conflicting optimization objectives and large-scale decision variables. Most of the existing multiobjective workflow scheduling algorithms regard the focused problems as black boxes, and optimize large-scale decision variables as a whole. This leads to inefficiency in searching solution spaces that grow exponentially with the increase of decision variables. To compensate the above deficiency, this paper proposes a knowledge-driven adaptive evolutionary multi-objective scheduling algorithm, KAMSA for short, to optimize makespan and cost of workflow execution in cloud platforms. Specifically, we excavate the knowledge that adjustment of a task's execution only affects its successor tasks to divide large-scale decision variables into a series of groups, so as to give play to the strengths of divide-and-conquer technology to improve the evolutionary search efficiency. Moreover, we develop an adaptive resource allocation scheme to reward more evolution opportunities for groups with high contributions to further improve the evolutionary search efficiency. We compare the proposed KAMSA with five state-of-the-art competitors in the context of 20 real-world workflows and the Amazon elastic compute cloud (EC2). The comparison results verify the KAMSA's advantages by prevailing over the five competitors on 18 out of the 20 test cases with respect to the metric hypervolume.& COPY; 2023 Elsevier B.V. All rights reserved.

Automated summary

This paper proposes a knowledge-driven adaptive evolutionary multi-objective scheduling algorithm (KAMSA) for optimizing makespan and cost of workflow execution in cloud platforms. It divides large-scale decision variables into groups using divide-and-conquer technology to improve evolutionary search efficiency. Comparison with five state-of-the-art competitors demonstrates KAMSA's advantages in 18 out of 20 test cases.