Hierarchical Deep Reinforcement Learning Approach for Multi-Objective Scheduling With Varying Queue Sizes

Yoni Birman, Ziv Ido, Gilad Katz, Asaf Shabtai

Introduction

Multi-objective task scheduling (MOTS) is a critical challenge in systems where performance must be balanced against accuracy, such as in malware detection or medical diagnostics. Traditional Deep Reinforcement Learning (DRL) approaches often struggle with reward complexity, queue position bias, and fixed input constraints. To address these issues, researchers have developed MERLIN, a hierarchical DRL framework designed for robust multi-objective scheduling across varying queue sizes.

The MERLIN Framework

MERLIN employs a two-tier hierarchical architecture to separate the concerns of task execution and queue management. This decoupling allows the system to handle conflicting goals like "accuracy" and "speed" more effectively than single-agent models.

The hierarchical architecture of MERLIN, featuring an Outer Agent for scheduling and an Internal Agent for task processing.

Internal Agent ($p^i$)

The internal agent focuses on processing a single item. It determines the optimal sequence of sub-processes (e.g., specific malware detectors) to reach a conclusion while minimizing time. Crucially, once trained, the internal agent is frozen. This ensures "procedural fairness," where every item is treated with identical logic regardless of the system's current backlog or queue position.

Outer Agent ($p^o$)

The outer agent serves as the scheduler, observing the state of all items in the queue and selecting the next candidate for the internal agent. To handle queues larger than its training size, MERLIN utilizes a recursive "state-action reduction" process. It partitions large queues into manageable subsets, iteratively selecting the best candidates until the final scheduling decision is made. This allows a model trained on a queue of 10 items to successfully manage queues of 100+ items without retraining.

Experimental Evaluation

The framework was evaluated using a malware detection dataset of 25,000 executable files. This environment is characterized by high uncertainty, as the true processing time for any given file is unknown until analysis is complete. MERLIN was trained on small queues of 10 items and tested on significantly larger queues to assess its scaling capabilities.

Key Results

MERLIN demonstrated superior efficiency compared to standard heuristic baselines. By learning to infer task difficulty through interaction rather than relying on pre-known durations, the agents proved highly robust in real-world scenarios.

Comparison of average file classification times across different scheduling algorithms, showing MERLIN's efficiency.

Key findings include:

  • Efficiency Gains: MERLIN outperformed realistic baselines like First-Come-First-Serve (FCFS) and Smallest-File-First (SFF) by over 22% across all tested queue sizes.
  • Reduced Latency: In fixed-size experiments, MERLIN achieved job completion times that were 27% to 71% shorter than traditional methods.
  • Computational Scalability: Training on small queue sizes (n=10) and scaling up proved far more efficient than training large networks. A model trained for a 20-item queue took seven times longer to reach the same performance level as the 10-item MERLIN model.

Conclusion

MERLIN provides a scalable and fair solution for complex scheduling tasks. While the current implementation focuses on malware detection, its hierarchical structure is applicable to other domains like industrial maintenance or medical testing. Future work will explore the impact of setup costs in physical systems and investigate methods to further approach global optimality in extremely large-scale environments.

Summary updated

Abstract

Multi-objective task scheduling (MOTS) is the task scheduling while optimizing multiple and possibly contradicting constraints. A challenging extension of this problem occurs when every individual task is a multi-objective optimization problem by itself. While deep reinforcement learning (DRL) has been successfully applied to complex sequential problems, its application to the MOTS domain has been stymied by two challenges. The first challenge is the inability of the DRL algorithm to ensure that every item is processed identically regardless of its position in the queue. The second challenge is the need to manage large queues, which results in large neural architectures and long training times. In this study we present MERLIN, a robust, modular and near-optimal DRL-based approach for multi-objective task scheduling. MERLIN applies a hierarchical approach to the MOTS problem by creating one neural network for the processing of individual tasks and another for the scheduling of the overall queue. In addition to being smaller and with shorted training times, the resulting architecture ensures that an item is processed in the same manner regardless of its position in the queue. Additionally, we present a novel approach for efficiently applying DRL-based solutions on very large queues, and demonstrate how we effectively scale MERLIN to process queue sizes that are larger by orders of magnitude than those on which it was trained. Extensive evaluation on multiple queue sizes show that MERLIN outperforms multiple well-known baselines by a large margin (>22%).
BibTeX
@inproceedings{birman2020hierarchical,
  author = {Yoni Birman and Ziv Ido and Gilad Katz and Asaf Shabtai},
  title = {{Hierarchical Deep Reinforcement Learning Approach for Multi-Objective Scheduling With Varying Queue Sizes}},
  booktitle = {IJCNN},
  year = {2020},
  doi = {10.1109/ijcnn52387.2021.9534433},
}
Figure