Recently,a growing number of scientific applications have been migrated into the cloud.To deal with the problems brought by clouds,more and more researchers start to consider multiple optimization goals in workflow sc...Recently,a growing number of scientific applications have been migrated into the cloud.To deal with the problems brought by clouds,more and more researchers start to consider multiple optimization goals in workflow scheduling.However,the previous works ignore some details,which are challenging but essential.Most existing multi-objective work-flow scheduling algorithms overlook weight selection,which may result in the quality degradation of solutions.Besides,we find that the famous partial critical path(PCP)strategy,which has been widely used to meet the deadline constraint,can not accurately reflect the situation of each time step.Work-flow scheduling is an NP-hard problem,so self-optimizing algorithms are more suitable to solve it.In this paper,the aim is to solve a workflow scheduling problem with a deadline constraint.We design a deadline constrained scientific workflow scheduling algorithm based on multi-objective reinforcement learning(RL)called DCMORL.DCMORL uses the Chebyshev scalarization function to scalarize its Q-values.This method is good at choosing weights for objectives.We propose an improved version of the PCP strategy called MPCP.The sub-deadlines in MPCP regularly update during the scheduling phase,so they can accurately reflect the situation of each time step.The optimization objectives in this paper include minimizing the execution cost and energy consumption within a given deadline.Finally,we use four scientific workflows to compare DCMORL and several representa-tive scheduling algorithms.The results indicate that DCMORL outperforms the above algorithms.As far as we know,it is the first time to apply RL to a deadline constrained workflow scheduling problem.展开更多
基金the National Natural Science Foundation of China(Grant No.61672323)the Fundamental Research Funds of Shandong University(2017JC043)+1 种基金the Key Research and Development Program of Shandong Province(2017GGX10122,2017GGX10142,and 2019JZZY010134)the Natural Science Foundation of Shandong Province(ZR2019MF072).
文摘Recently,a growing number of scientific applications have been migrated into the cloud.To deal with the problems brought by clouds,more and more researchers start to consider multiple optimization goals in workflow scheduling.However,the previous works ignore some details,which are challenging but essential.Most existing multi-objective work-flow scheduling algorithms overlook weight selection,which may result in the quality degradation of solutions.Besides,we find that the famous partial critical path(PCP)strategy,which has been widely used to meet the deadline constraint,can not accurately reflect the situation of each time step.Work-flow scheduling is an NP-hard problem,so self-optimizing algorithms are more suitable to solve it.In this paper,the aim is to solve a workflow scheduling problem with a deadline constraint.We design a deadline constrained scientific workflow scheduling algorithm based on multi-objective reinforcement learning(RL)called DCMORL.DCMORL uses the Chebyshev scalarization function to scalarize its Q-values.This method is good at choosing weights for objectives.We propose an improved version of the PCP strategy called MPCP.The sub-deadlines in MPCP regularly update during the scheduling phase,so they can accurately reflect the situation of each time step.The optimization objectives in this paper include minimizing the execution cost and energy consumption within a given deadline.Finally,we use four scientific workflows to compare DCMORL and several representa-tive scheduling algorithms.The results indicate that DCMORL outperforms the above algorithms.As far as we know,it is the first time to apply RL to a deadline constrained workflow scheduling problem.
