Research Area:  Cloud Computing

Abstract:

Cloud computing is a computing model that fully utilizes the resources on the Internet to maximize the utilization of resources. Due to a large number of users and tasks, it is important to achieve efficient scheduling of tasks submitted by users. Task scheduling is one of the crucial and challenging non-deterministic polynomial-hard problems in cloud computing. In task scheduling, obtaining shorter makespan is an important objective and is related to the pros and cons of the algorithm. Machine learning algorithms represent a new method for solving this type of problem. In this paper, we propose a novel task scheduling algorithm called QL-HEFT that combines Q-learning with the heterogeneous earliest finish time (HEFT) algorithm to reduce the makespan. The algorithm uses the upward rank (ranku) value of HEFT as the immediate reward in the Q-learning framework. The agent can obtain better learning results to update the Q-table through the self-learning process. The QL-HEFT algorithm is divided into two major phases: a task sorting phase based on Q-learning for obtaining an optimal order and a processor allocation phase using the earliest finish time strategy. Experiments show that QL-HEFT achieves a shorter makespan compared to three other classical scheduling algorithms as well as good performances in terms of the average response time.

Keywords:  

Author(s) Name:  Zhao Tong, Xiaomei Deng, Hongjian Chen, Jing Mei & Hong Liu

Publisher name:  Springer

DOI:  10.1007/s00521-019-04118-8

Volume Information:  volume 32, pages 5553–5570 (2020)

Paper Link:   https://link.springer.com/article/10.1007/s00521-019-04118-8