This repository implements a Reinforcement Learning (RL) based Hyper-Heuristic for solving the Identical Parallel Machine Scheduling Problem (
Instead of designing a single handcrafted heuristic, the system learns how to dynamically select low-level heuristics using reinforcement learning. The RL agent learns a policy over heuristic operators that modify schedules to reduce makespan.
The project integrates:
- Reinforcement Learning (Deep Q-Network)
- Hyper-Heuristics
- Classical scheduling algorithms
- Experimental benchmarking
Built using:
- PyTorch
- Stable-Baselines3
- Gymnasium
- NumPy
- Pandas
- Matplotlib
- TensorBoard
Let's consider the Identical Parallel Machine Scheduling Problem.
Given:
-
$n$ jobs -
$m$ identical machines - processing time
$p_j$ for job$j$
The goal is to assign jobs to machines such that the makespan is minimized.
where
and
This problem is NP-hard for
Theoretical bounds are used to evaluate schedule quality.
Total processing time:
Optimality gap:
Initial schedules are generated using classical scheduling heuristics.
Assign each job to the least loaded machine.
Jobs sorted:
Then scheduled using list scheduling.
Worst-case bound:
Low-level heuristics modify schedules.
Examples:
- Job swap
- Job relocation
- Load balancing
- Machine reassignment
Pseudo-code:
Algorithm ApplyOperator(schedule S, operator op)
if op == SWAP:
choose jobs i,j
swap machines
if op == RELOCATE:
move job i to new machine
if op == BALANCE:
move job from heaviest machine
to lightest machine
return updated schedule
A Hyper-Heuristic (HH) operates at a higher level than standard heuristics. Instead of directly constructing schedules, it selects among heuristics.
Workflow:
flowchart LR
A[Scheduling Instance] --> B[Environment State]
B --> C[RL Agent]
C --> D[Select Heuristic Operator]
D --> E[Modify Schedule]
E --> F[Compute Reward]
F --> B
The RL agent learns a policy over heuristic operators that iteratively improve schedules.
The scheduling improvement process is modeled as a Markov Decision Process (MDP).
State features include:
- machine loads
- load imbalance
- current makespan
- lower bound ratio
- remaining jobs
Example state vector:
Each action corresponds to a low-level heuristic operator.
Reward reflects improvement in makespan:
Positive reward indicates schedule improvement.
The RL agent is trained using a Deep Q-Network (DQN) to approximate the action-value function.
Update rule:
The neural network approximates the Q-function:
where
Where:
-
$s$ -- current state -
$a$ -- selected action (heuristic operator) -
$r$ -- reward obtained after applying the operator -
$\gamma$ -- discount factor -
$\alpha$ -- learning rate -
$\theta$ -- neural network parameters
Custom Gymnasium environment:
src/rl_hh/env/sched_identical_env.py
Implements:
step()
reset()
reward()
termination()
flowchart TD
A[Generate Scheduling Instance]
B[Initialize Environment]
C[Observe State]
D[DQN Agent Selects Action]
E[Apply Heuristic Operator]
F[Update Schedule]
G[Compute Reward]
H[Store Transition]
I[Update Q-Network]
A --> B
B --> C
C --> D
D --> E
E --> F
F --> G
G --> H
H --> I
I --> C
Algorithm RL Hyper-Heuristic
Initialize RL agent
Generate scheduling instance
Construct initial schedule
for episode:
observe state s
select operator a
apply operator
observe reward r
update Q-network
return best schedule
Example schedule:
Machine 1: | J2 | J7 | J9 |
Machine 2: | J1 | J3 |
Machine 3: | J4 | J5 | J8 |
Machine 4: | J6 |
Gantt-style representation:
gantt
title Example Schedule
dateFormat X
axisFormat %L
section Machine 1
J2 :0,5
J7 :5,3
J9 :8,2
section Machine 2
J1 :0,4
J3 :4,4
section Machine 3
J4 :0,2
J5 :2,6
J8 :8,2
Instances generated using distributions.
Half small jobs:
Half large jobs:
Lognormal distribution:
Implemented in:
vendor/identical_scheduling/instances.py
Two baselines are implemented.
Randomly selects operators.
baselines/random_hh.py
Selects the best immediate operator.
baselines/greedy_hh.py
src/
└── rl_hh/
├── env/
├── heuristics/
├── baselines/
├── rl/
├── utils/
└── vendor/
└── identical_scheduling/
experiments/
train_agent.py
evaluate.py
results/
evaluation csv files
plots
tensorboard logs
Create environment:
conda env create -f environment.yml
conda activate hh-env
Install additional packages:
pip install -e .
pip install -r requirements.txt
Train RL agent:
python experiments/train_agent.py
This trains a DQN agent using Stable-Baselines3.
Training artifacts:
results/
models
tensorboard logs
Run evaluation:
python experiments/evaluate.py
Outputs:
- CSV summaries
- operator usage statistics
- evaluation plots
Experiments conducted on multiple instance sizes.
| Jobs | Machines |
|---|---|
| 50 | 5 |
| 120 | 8 |
| 250 | 15 |
| 500 | 25 |
Findings:
- RL hyper-heuristic significantly outperforms the random baseline
- Performance is competitive with the greedy hyper-heuristic
- Learned policies generalize across larger problem sizes
Step 1
python experiments/train_agent.py
Step 2
python experiments/evaluate.py
Step 3
Inspect results:
results/*.csv
results/*.png
Run:
tensorboard --logdir results/tb
Open:
http://localhost:6006
This project demonstrates:
- Reinforcement learning based hyper-heuristics
- Integration with classical scheduling heuristics
- Scalable experimentation pipeline
- Generalization across scheduling scales
Possible extensions:
- Integrate a quantum-enhanced heuristic operator (QAOA-based) into the RL hyper-heuristic operator set.
- multi-objective scheduling
- adaptive operator sets
- meta-learning across distributions
The mathematical formulations and concepts used in this project are based on established work in scheduling theory, hyper-heuristics, and reinforcement learning.
-
Scheduling Theory
Michael Pinedo.
Scheduling: Theory, Algorithms, and Systems.
Springer, 5th Edition, 2016. -
Parallel Machine Scheduling
Ronald L. Graham.
"Bounds on multiprocessing timing anomalies."
SIAM Journal on Applied Mathematics, 17(2), 416-429, 1969. -
Longest Processing Time (LPT) Rule
Ronald L. Graham.
"Bounds for Certain Multiprocessing Anomalies."
Bell System Technical Journal, 45(9), 1563–1581, 1966. -
Hyper-Heuristics
Edmund K. Burke, Michel Gendreau, Matthew Hyde, Graham Kendall, Gabriela Ochoa, Ender Özcan, and Rong Qu.
"Hyper-heuristics: A survey of the state of the art."
Journal of the Operational Research Society, 64(12), 1695–1724, 2013. -
Hyper-Heuristics for Combinatorial Optimization
Edmund K. Burke, Graham Kendall.
Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques.
Springer, 2014. -
Reinforcement Learning Foundations
Richard S. Sutton and Andrew G. Barto.
Reinforcement Learning: An Introduction.
MIT Press, Second Edition, 2018. -
Q-Learning
Christopher J. C. H. Watkins and Peter Dayan.
"Q-learning."
Machine Learning, 8, 279–292, 1992. -
Deep Q-Networks
Volodymyr Mnih et al.
"Human-level control through deep reinforcement learning."
Nature, 518, 529–533, 2015. -
Reinforcement Learning for Combinatorial Optimization
Irwan Bello et al.
"Neural Combinatorial Optimization with Reinforcement Learning."
International Conference on Learning Representations (ICLR), 2017. -
Reinforcement Learning Hyper-Heuristics
Ender Özcan, Mustafa Misir, Gabriela Ochoa, and Edmund Burke.
"A reinforcement learning approach to hyper-heuristics."
European Journal of Operational Research, 2010.