A multi-objective reinforcement learning algorithm for deadline constrained scientific workflow scheduling in clouds
Yao QIN1,2, Hua WANG3(), Shanwen YI1, Xiaole LI4(), Linbo ZHAI5
1. 1School of Computer Science and Technology, Shandong University, Jinan 250101, China 2. 2Shanghai Police College, Shanghai 200137, China 3. 3School of Software, Shandong University, Jinan 250101, China 4. 4School of Information Science and Engineering, Linyi University, Linyi 276005, China 5. 5School of Information Science and Engineering, Shandong Normal University, Jinan 250014, China
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.
P K Senyo, E Addae, R Boateng. Cloud computing research: a review of research themes, frameworks, methods and future research directions. International Journal of Information Management, 2018, 38(1): 128–139 https://doi.org/10.1016/j.ijinfomgt.2017.07.007
2
A S G Andrae, T Edler. On global electricity usage of communication technology: trends to 2030. Challenges, 2015, 6(1): 117–157 https://doi.org/10.3390/challe6010117
3
J Hamilton. 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
N Khattar, J Sidhu, J Singh. 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 https://doi.org/10.1007/s11227-019-02764-2
5
Y Wang, H Liu, W Zheng, Y Xia, Y Li, P Chen, K Guo, H Xie. Multiobjective workflow scheduling with deep-Q-network-based multi-agent reinforcement learning. IEEE Access, 2019, 7: 39974–39982 https://doi.org/10.1109/ACCESS.2019.2902846
6
I Das, J E Dennis. 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 https://doi.org/10.1007/BF01197559
7
K Van Moffaert, M M Drugan, A Nowé. Scalarized multi-objective reinforcement learning: novel design techniques. In: Proceedings of IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning. 2013, 191–199 https://doi.org/10.1109/ADPRL.2013.6615007
8
S Abrishami, M Naghibzadeh, D H Epema. Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds. Future Generation Computer Systems, 2013, 29(1): 158–169 https://doi.org/10.1016/j.future.2012.05.004
9
Y Qin, H Wang, S Yi, X Li, L Zhai. An energy-aware scheduling algorithm for budget-constrained scientific workflows based on multiobjective reinforcement learning. The Journal of Supercomputing, 2020, 76: 455–480 https://doi.org/10.1007/s11227-019-03033-y
10
E Zitzler, L Thiele, M Laumanns, C M Fonseca, V G Da Fonseca. Performance assessment of multiobjective optimizers: an analysis and review. TIK-Report, 2002 https://doi.org/10.1109/TEVC.2003.810758
11
Y Qin, H Wang, S Yi, X Li, L Zhai. Virtual machine placement based on multi-objective reinforcement learning. Applied Intelligence, 2020 https://doi.org/10.1007/s10489-020-01633-3
12
R S Sutton, A G Barto. Reinforcement Learning: An Introduction. MIT Press, 2018
13
C J C H Watkins. Learning from delayed rewards. Doctoral Thesis, University of Cambridge, 1989
14
J N Tsitsiklis. Asynchronous stochastic approximation and Q-learning. Machine Learning, 1994, 16(3): 185–202 https://doi.org/10.1007/BF00993306
15
M A Wiering, E D De Jong. 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 https://doi.org/10.1109/ADPRL.2007.368183
16
K Van Moffaert, A Nowé. Multi-objective reinforcement learning using sets of pareto dominating policies. The Journal of Machine Learning Research, 2014, 15(1): 3483–3512
17
P Vamplew, J Yearwood, R Dazeley, A Berry. 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 https://doi.org/10.1007/978-3-540-89378-3_37
18
T Voβ, N Beume, G Rudolph, C Igel. 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 https://doi.org/10.1109/CEC.2008.4631208
19
J Yu, R Buyya, C K Tham. 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
S Abrishami, M Naghibzadeh, D H J Epema. Cost-driven scheduling of grid workflows using partial critical paths. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(8): 1400–1414 https://doi.org/10.1109/TPDS.2011.303
21
Z Li, J Ge, H Hu, W Song, H Hu, B Luo. Cost and energy aware scheduling algorithm for scientific workflows with deadline constraint in clouds. IEEE Transactions on Services Computing, 2015, 11(4): 713–726 https://doi.org/10.1109/TSC.2015.2466545
22
A Verma, S Kaushal. A hybrid multi-objective particle swarm optimization for scientific workflow scheduling. Parallel Computing, 2017, 62: 1–19 https://doi.org/10.1016/j.parco.2017.01.002
23
C A C Coello, G T Pulido, M S Lechuga. Handling multiple objectives with particle swarm optimization. IEEE Transactions on Evolutionary Computation, 2004, 8(3): 256–279 https://doi.org/10.1109/TEVC.2004.826067
24
R A Haidri, C P Katti, P C Saxena. 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 https://doi.org/10.1002/cpe.5006
25
K Deb, A Pratap, S Agarwal, T Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182–197 https://doi.org/10.1109/4235.996017
26
J Wang, A Taal, P Martin, Y Hu, H Zhou, J Pang, d C Laat, Z Zhao. Planning virtual infrastructures for time critical applications with multiple deadline constraints. Future Generation Computer Systems, 2017, 75: 365–375 https://doi.org/10.1016/j.future.2017.02.001
27
D Zhu, R Melhem, B R Childers. 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 https://doi.org/10.1109/TPDS.2003.1214320
28
Y C Lee, A Y Zomaya. Energy conscious scheduling for distributed computing systems under different operating conditions. IEEE Transactions on Parallel and Distributed Systems, 2010, 22(8): 1374–1381 https://doi.org/10.1109/TPDS.2010.208
29
M Atkinson, S Gesing, J Montagnat, I Taylor. Scientific workflows: past, present and future. Future Generation Computer Systems, 2017, 75: 216–227 https://doi.org/10.1016/j.future.2017.05.041
30
H Topcuoglu, S Hariri, M Y Wu. Performance-effective and lowcomplexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260–274 https://doi.org/10.1109/71.993206
31
S Bharathi, A Chervenak, E Deelman, G Mehta, M H Su, K Vahi. Characterization of scientific workflows. In: Proceedings of the 3rd Workshop on Workflows in Support of Large-scale Science. 2008, 1–10 https://doi.org/10.1109/WORKS.2008.4723958
32
R N Calheiros, R Ranjan, A Beloglazov, C A De Rose, R Buyya. 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 https://doi.org/10.1002/spe.995
33
N Herbst, A Bauer, S Kounev, G Oikonomou, E V Eyk, G Kousiouris, A Evangelinou, R Krebs, T Brecht, C L Abad, et al.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 https://doi.org/10.1145/3236332
34
F S Melo. Convergence of Q-learning: a simple proof. Institute of Systems and Robotics, Technical Report, 2001, 1–4
