A New Approach for Resource Scheduling with Deep Reinforcement Learning

Yufei Ye, Xiaoqin Ren, Jin Wang, Lingxiao Xu, Wenxia Guo, Wenqiang Huang, Wenhong TianarXiv 2018 · OpenReview

TL;DR

This paper introduces DeepRM2 and DeepRM_Off, novel deep reinforcement learning (DRL) algorithms for online and offline resource scheduling, respectively. By incorporating imitation learning and a convolutional neural network, these methods achieve faster convergence and improved scheduling efficiency compared to existing DRL and heuristic approaches.

What Problem Does This Paper Address?

Resource scheduling, particularly in environments like cloud computing, is a complex NP-hard problem. Traditional heuristic algorithms, while effective, often require manual adjustments when system conditions change. Machine learning, and specifically reinforcement learning (RL), has emerged as a promising alternative. The paper builds upon prior work like DeepRM, which applied DRL to online resource scheduling, but aims to improve its efficiency and extend its applicability to offline scenarios. The challenge is to develop DRL agents that can learn optimal scheduling policies quickly and effectively, outperforming established methods.

Methods

The core contribution lies in two new DRL algorithms:

  • DeepRM2 (Online Scheduling): This algorithm enhances the original DeepRM by:
  • Imitation Learning Pre-training: Using behavior cloning with the Shortest-Job-First (SJF) heuristic to provide an initial, informed policy for the DRL agent. This speeds up the learning process.
  • Convolutional Neural Network (CNN): Replacing DeepRM's fully connected network with a CNN. This is crucial because the state representation is image-like (visualizing cluster resources and job queues), and CNNs are adept at extracting features from such data.
  • Redefined Cluster Capacity: A minor adjustment to the cluster capacity representation.
  • DeepRM_Off (Offline Scheduling): This algorithm adapts the DeepRM2 approach for offline scheduling, where all jobs are known upfront. Key modifications include:
  • Job Slot Allocation: All jobs are loaded into job slots at the beginning, simplifying the state representation by removing the "backlog" component.

Both algorithms utilize a policy gradient method for training, aiming to optimize cumulative rewards. The state space is represented as an image, and the action space involves selecting a job to schedule or choosing to "move on" (advance the system state). The paper defines rewards based on two objectives: minimizing average job slowdown and minimizing overall job completion time.

Datasets

The paper does not explicitly mention using pre-existing public datasets. Instead, it describes generating synthetic workloads for training and evaluation. For online scheduling, jobs arrive via a Poisson process, and the cluster load is varied from 10% to 190%. For offline scheduling, the workload is the same as online, but all jobs are available at the start. The authors generated jobsets for imitation learning and then used these synthetic workloads for training and evaluating DeepRM2 and DeepRM_Off.

Key Insights and Ideas

  • Imitation Learning as a Warm-up: Pre-training with imitation learning (behavior cloning) significantly accelerates the convergence of DRL agents for scheduling tasks. This is a practical way to leverage existing heuristic knowledge.
  • CNNs for Visual States: Representing scheduling states as images and using CNNs is a natural and effective approach for feature extraction, leading to better performance than simple fully connected networks.
  • Unified Framework for Online/Offline: The paper demonstrates that a DRL framework can be successfully adapted for both online (dynamic job arrivals) and offline (batch job processing) scheduling scenarios with relatively minor modifications.
  • DeepRM2 Outperforms DeepRM: The enhanced DeepRM2 consistently shows better performance than the original DeepRM, highlighting the benefits of the proposed improvements.

Key Results

  • Faster Convergence: DeepRM2 converges significantly faster than DeepRM, with training times per epoch being 37.5% less.
  • Improved Scheduling Efficiency:
    • Average Job Slowdown: DeepRM2 consistently achieves lower average job slowdown across various cluster loads compared to DeepRM and SJF. For example, at 70% load, DeepRM2 trained for slowdown outperforms DeepRM trained for slowdown.
  • Job Completion Time: Similarly, DeepRM2 trained for completion time shows better results than DeepRM trained for completion time.
  • Offline Scheduling: DeepRM_Off demonstrates that DRL can effectively handle offline scheduling, achieving a maximum discounted cumulative reward and minimum average job slowdown after training, outperforming SJF, Tetris, and Random heuristics.
  • General Superiority: Both DeepRM2 and DeepRM_Off, through deep reinforcement learning, significantly outperform traditional heuristic methods like SJF, Tetris, and Random.

Limitations and Future Work

  • Multi-cluster Scheduling: The current work focuses on a single-cluster environment. The authors acknowledge that real-world scenarios often involve multiple clusters and plan to investigate multi-cluster scheduling systems in the future. This is important because resource fragmentation in single clusters can be difficult to manage.
  • Algorithm Exploration: While the paper uses policy gradient methods, the authors express interest in exploring more advanced DRL algorithms like Actor-Critic and DDPG, which might offer further improvements in stability and convergence speed.
  • Theoretical Application: The authors aim to bridge the gap between theoretical results and practical application in actual production environments.

Summary updated

Abstract

With the rapid development of deep learning, deep reinforcement learning (DRL) began to appear in the field of resource scheduling in recent years. Based on the previous research on DRL in the literature, we introduce online resource scheduling algorithm DeepRM2 and the offline resource scheduling algorithm DeepRM_Off. Compared with the state-of-the-art DRL algorithm DeepRM and heuristic algorithms, our proposed algorithms have faster convergence speed and better scheduling efficiency with regarding to average slowdown time, job completion time and rewards.
BibTeX
@misc{ye2018new,
  author = {Yufei Ye and Xiaoqin Ren and Jin Wang and Lingxiao Xu and Wenxia Guo and Wenqiang Huang and Wenhong Tian},
  title = {{A New Approach for Resource Scheduling with Deep Reinforcement Learning}},
  year = {2018},
  eprint = {1806.08122},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1806.08122},
}
Figure