Multi-Objective Task Scheduling in Cloud Computing using Proximal Policy Optimization: Balancing Execution Time, Cost, and Energy

Iklaas Sultan

Abstract


Task scheduling in cloud computing is an NP-hard combinatorial problem in which incoming tasks must be assigned to heterogeneous servers under conflicting objectives. Classical heuristics such as First-Come-First-Served (FCFS), Round-Robin (RR), and priority-based scheduling optimize a single criterion and adapt poorly to dynamic workloads, while metaheuristics such as genetic algorithms (GA) require offline knowledge of the full workload. This paper formulates online multi-objective cloud task scheduling as a Markov decision process and proposes a scheduler based on Proximal Policy Optimization (PPO), a state-of-the-art deep reinforcement learning (DRL) algorithm. In experiments on synthetic workloads, the proposed scheduler reduces mean task response time by 59.1%, 51.5%, and 67.0% relative to FCFS, RR, and Priority, respectively, and by 20.7% relative to an offline GA, while improving the overall multi-objective cost by 11.6–22.0% over rule-based baselines; these differences are statistically significant with large effect sizes (Wilcoxon signed-rank, ???? < 2 × 10−4). A Pareto analysis of the reward weights shows that the learned policies form a controllable trade-off front that no classical baseline Pareto-dominates, although no single policy is best on every individual metric, and a load-intensity study shows the advantage widens under heavy load. The complete implementation is released for reproducibility.

Keywords


cloud computing; deep reinforcement learning; energy efficiency; multi-objective optimization; proximal policy optimization; task scheduling

Full Text:

PDF

References


Arunarani, A., Manjula, D., and Sugumaran, V. (2019). Task Scheduling Techniques in Cloud Computing: A Literature Survey. Future Generation Computer Systems, 91:407–415.

Barroso, L. A. and Hölzle, U. (2007). The Case for Energy-Proportional Computing. Computer, 40(12):33–37.

Beloglazov, A., Abawajy, J., and Buyya, R. (2012). Energy-Aware Resource Allocation Heuristics for Efficient Management of Data Centers for Cloud Computing. Future Generation Computer Systems, 28(5):755–768.

Braun, T. D., Siegel, H. J., Beck, N., Bölöni, L. L., Maheswaran, M., Reuther, A. I., Robertson, J. P., Theys, M. D., Yao, B., Hensgen, D., and Freund, R. F. (2001). A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks Onto Heterogeneous Distributed Computing Systems. Journal of Parallel and Distributed Computing, 61(6):810–837.

Buyya, R., Yeo, C. S., Venugopal, S., Broberg, J., and Brandic, I. (2009). Cloud Computing and Emerging IT Platforms: Vision, Hype, and Reality for Delivering Computing as the 5th Utility. Future Generation Computer Systems, 25(6):599–616.

Calheiros, R. N., Ranjan, R., Beloglazov, A., De Rose, C. A. F., and Buyya, R. (2011). CloudSim: a Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms. Software: Practice and Experience, 41(1):23–50.

Cheng, M., Li, J., and Nazarian, S. (2018). DRL-Cloud: Deep Reinforcement Learning-based Resource Provisioning and Task Scheduling for Cloud Service Providers. In Proceedings of the 23rd Asia and South Pacific Design Automation Conference (ASP-DAC), pages 129–134.

Holland, J. H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press, Cambridge, MA.

Houssein, E. H., Gad, A. G., Wazery, Y. M., and Suganthan, P. N. (2021). Task Scheduling in Cloud Computing based on Meta-Heuristics: Review, Taxonomy, Open Challenges, and Future Trends. Swarm and Evolutionary Computation, 62:100841.

Kennedy, J. and Eberhart, R. (1995). Particle Swarm Optimization. In Proceedings of the IEEE Interna-tional Conference on Neural Networks, Volume 4, pages 1942–1948.

Kingma, D. P. and Ba, J. (2015). Adam: A Method for Stochastic Optimization. In Proceedings of the 3rd International Conference on Learning Representations (ICLR). arXiv:1412.6980.

Liu, N., Li, Z., Xu, J., Xu, Z., Lin, S., Qiu, Q., Tang, J., and Wang, Y. (2017). A Hierarchical Framework of Cloud Resource Allocation and Power Management using Deep Reinforcement Learning. In Proceedings of the 37th IEEE International Conference on Distributed Computing Systems (ICDCS), pages 372–382.

Mao, H., Alizadeh, M., Menache, I., and Kandula, S. (2016). Resource Management with Deep Reinforce-Ment Learning. In Proceedings of the 15th ACM Workshop on Hot Topics in Networks (HotNets), pages 50–56.

Masdari, M., Salehi, F., Jalali, M., and Bidaki, M. (2017). A Survey of PSO-based Scheduling Algorithms in Cloud Computing. Journal of Network and Systems Management, 25(1):122–158.

Mell, P. and Grance, T. (2011). The NIST Definition of Cloud Computing. NIST Special Publication, 800-145.

Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D., and Kavukcuoglu, K. (2016). Asynchronous Methods for Deep Reinforcement Learning. In Proceedings of the 33rd Interna-tional Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1928–1937.

Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., and Hassabis, D. (2015). Human-Level Control through Deep Reinforcement Learning. Nature, 518(7540):529–533.

Raffin, A., Hill, A., Gleave, A., Kanervisto, A., Ernestus, M., and Dormann, N. (2021). Stable-Baselines3: Reliable Reinforcement Learning Implementations. Journal of Machine Learning Research, 22(268):1–8.

Reiss, C., Tumanov, A., Ganger, G. R., Katz, R. H., and Kozuch, M. A. (2012). Heterogeneity and Dynamicity of Clouds at Scale: Google trace analysis. In Proceedings of the Third ACM Symposium on Cloud Computing (SoCC), pages 1–13.

Rjoub, G., Bentahar, J., Abdel Wahab, O., and Saleh Bataineh, A. (2021). Deep and Reinforcement Learning for Automated Task Scheduling in Large-Scale Cloud Computing Systems. Concurrency and Computation: Practice and Experience, 33(23):e5919.

Schulman, J., Moritz, P., Levine, S., Jordan, M., and Abbeel, P. (2016). High-Dimensional Continuous Control using Generalized Advantage Estimation. In Proceedings of the 4th International Conference on Learning Representations (ICLR). arXiv:1506.02438.

Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017). Proximal Policy Optimization Algorithms. arXiv preprint. arXiv:1707.06347.

Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., and Hassabis, D. (2016). Mastering the Game of Go with Deep Neural Networks and Tree Search. Nature, 529(7587):484–489.

Sutton, R. S. and Barto, A. G. (2018). Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 2nd edition.

Tong, Z., Chen, H., Deng, X., Li, K., and Li, K. (2020). A Scheduling Scheme in the Cloud Computing Environment using Deep Q-learning. Information Sciences, 512:1170–1191.

Topcuoglu, H., Hariri, S., and Wu, M.-Y. (2002). Performance-Effective and Low-Complexity Task Schedul-ing for Heterogeneous Computing. IEEE Transactions on Parallel and Distributed Systems, 13(3):260–274.

Towers, M., Kwiatkowski, A., Terry, J., Balis, J. U., De Cola, G., Deleu, T., Goulão, M., Kallinteris, A., Krimmel, M., KG, A., et al. (2024). Gymnasium: A Standard Interface for Reinforcement Learning Environments. arXiv preprint. arXiv:2407.17032.

Ullman, J. D. (1975). NP-Complete Scheduling Problems. Journal of Computer and System Sciences, 10(3):384–393.

Wang, Y., Liu, H., Zheng, W., Xia, Y., Li, Y., Chen, P., Guo, K., and Xie, H. (2019). Multi-Objective Workflow Scheduling with Deep-Q-Network-based Multi-Agent Reinforcement Learning. IEEE Access, 7:39974–39982.

Wilcoxon, F. (1945). Individual Comparisons by Ranking Methods. Biometrics Bulletin, 1(6):80–83.




DOI: https://doi.org/10.32520/stmsi.v15i10.6947

Article Metrics

Abstract view : 0 times
PDF - 0 times

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.