A multi-objective reinforcement learning algorithm for deadline constrained scientific workflow scheduling in clouds

Abstract

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 workflow 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. Workflow 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 calledMPCP. 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 representative 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.

Keywords

workflow scheduling / energy saving / multiobjective reinforcement learning / deadline constrained / cloud computing

References

[1] Senyo P K, Addae E, Boateng R. Cloud computing research: a review of research themes, frameworks, methods and future research directions. International Journal of Information Management, 2018, 38(1): 128–139

[2] Andrae A S G, Edler T. On global electricity usage of communication technology: trends to 2030. Challenges, 2015, 6(1): 117–157

[3] Hamilton J. Cooperative expendable micro-slice servers (cems): low cost, low power servers for internet-scale services. In: Proceedings of Conference on Innovative Data Systems Research. 2009

[4] Khattar N, Sidhu J, Singh J. Toward energy-efficient cloud computing: a survey of dynamic power management and heuristics-based optimization techniques. The Journal of Supercomputing, 2019, 75(8): 4750–4810

[5] Wang Y, Liu H, Zheng W, Xia Y, Li Y, Chen P, Guo K, Xie H. Multiobjective workflow scheduling with deep-Q-network-based multi-agent reinforcement learning. IEEE Access, 2019, 7: 39974–39982

[6] Das I, Dennis J E. A closer look at drawbacks of minimizing weighted sums of objectives for pareto set generation in multicriteria optimization problems. Structural Optimization, 1997, 14(1): 63–69

[7] Van Moffaert K, Drugan M M, Nowé A. Scalarized multi-objective reinforcement learning: novel design techniques. In: Proceedings of IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning. 2013, 191–199

[8] Abrishami S, Naghibzadeh M, Epema D H. Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds. Future Generation Computer Systems, 2013, 29(1): 158–169

[9] Qin Y, Wang H, Yi S, Li X, Zhai L. An energy-aware scheduling algorithm for budget-constrained scientific workflows based on multiobjective reinforcement learning. The Journal of Supercomputing, 2020, 76: 455–480

[10] Zitzler E, Thiele L, Laumanns M, Fonseca C M, Da Fonseca V G. Performance assessment of multiobjective optimizers: an analysis and review. TIK-Report, 2002

[11] Qin Y, Wang H, Yi S, Li X, Zhai L. Virtual machine placement based on multi-objective reinforcement learning. Applied Intelligence, 2020

[12] Sutton R S, Barto A G. Reinforcement Learning: An Introduction. MIT Press, 2018

[13] Watkins C J C H. Learning from delayed rewards. Doctoral Thesis, University of Cambridge, 1989

[14] Tsitsiklis J N. Asynchronous stochastic approximation and Q-learning. Machine Learning, 1994, 16(3): 185–202

[15] Wiering M A, De Jong E D. Computing optimal stationary policies for multi-objective markov decision processes. In: Proceedings of IEEE International Symposium on Approximate Dynamic Programming and Reinforcement Learning. 2007, 158–165

[16] Van Moffaert K, Nowé A. Multi-objective reinforcement learning using sets of pareto dominating policies. The Journal of Machine Learning Research, 2014, 15(1): 3483–3512

[17] Vamplew P, Yearwood J, Dazeley R, Berry A. On the limitations of scalarisation for multi-objective reinforcement learning of pareto fronts. In: Proceedings of Australasian Joint Conference on Artificial Intelligence. 2008, 372–378

[18] Voβ T, Beume N, Rudolph G, Igel C. Scalarization versus indicator-based selection in multi-objective cma evolution strategies. In: Proceedings of IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence). 2008, 3036–3043

[19] Yu J, Buyya R, Tham C K. Cost-based scheduling of scientific workflow applications on utility grids. In: Proceedings of the 1st International Conference on e-Science and Grid Computing. 2005

[20] Abrishami S, Naghibzadeh M, Epema D H J. Cost-driven scheduling of grid workflows using partial critical paths. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(8): 1400–1414

[21] Li Z, Ge J, Hu H, Song W, Hu H, Luo B. Cost and energy aware scheduling algorithm for scientific workflows with deadline constraint in clouds. IEEE Transactions on Services Computing, 2015, 11(4): 713–726

[22] Verma A, Kaushal S. A hybrid multi-objective particle swarm optimization for scientific workflow scheduling. Parallel Computing, 2017, 62: 1–19

[23] Coello C A C, Pulido G T, Lechuga M S. Handling multiple objectives with particle swarm optimization. IEEE Transactions on Evolutionary Computation, 2004, 8(3): 256–279

[24] Haidri R A, Katti C P, Saxena P C. Cost-effective deadline-aware stochastic scheduling strategy for workflow applications on virtual machines in cloud computing. Concurrency and Computation: Practice and Experience, 2019, 31(7): e5006

[25] Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182–197

[26] Wang J, Taal A, Martin P, Hu Y, Zhou H, Pang J, Laat d C, Zhao Z. Planning virtual infrastructures for time critical applications with multiple deadline constraints. Future Generation Computer Systems, 2017, 75: 365–375

[27] Zhu D, Melhem R, Childers B R. Scheduling with dynamic voltage/speed adjustment using slack reclamation in multiprocessor real-time systems. IEEE Transactions on Parallel and Distributed Systems, 2003, 14(7): 686–700

[28] Lee Y C, Zomaya A Y. Energy conscious scheduling for distributed computing systems under different operating conditions. IEEE Transactions on Parallel and Distributed Systems, 2010, 22(8): 1374–1381

[29] Atkinson M, Gesing S, Montagnat J, Taylor I. Scientific workflows: past, present and future. Future Generation Computer Systems, 2017, 75: 216–227

[30] Topcuoglu H, Hariri S, Wu M Y. Performance-effective and lowcomplexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260–274

[31] Bharathi S, Chervenak A, Deelman E, Mehta G, Su M H, Vahi K. Characterization of scientific workflows. In: Proceedings of the 3rd Workshop on Workflows in Support of Large-scale Science. 2008, 1–10

[32] Calheiros R N, Ranjan R, Beloglazov A, De Rose C A, Buyya R. Cloudsim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms. Software: Practice and Experience, 2011, 41(1): 23–50

[33] Herbst N, Bauer A, Kounev S, Oikonomou G, Eyk E V, Kousiouris G, Evangelinou A, Krebs R, Brecht T, Abad C L, Quantifying cloud performance and dependability: taxonomy, metric design, and emerging challenges. ACM Transactions on Modeling and Performance Evaluation of Computing Systems (ToMPECS), 2018, 3(4): 19

[34] Melo F S. Convergence of Q-learning: a simple proof. Institute of Systems and Robotics, Technical Report, 2001, 1–4

RIGHTS & PERMISSIONS

Higher Education Press