Skip to content
Ramon Fontelles
All projects

MSc thesis · Optimization2024Completed

Improving a Grey Wolf Optimizer for job shop scheduling

My MSc thesis in AI: three changes to a hybrid Grey Wolf Optimizer that keep the search from stalling. On 22 standard benchmark instances, the mean gap to the best-known makespan fell from 5.55% to 2.43%.

Role
Author, MSc thesis in AI
Institution
Polytechnic University of Madrid
Date
February 2024
Stack
Python, NumPy, Pandas, Jupyter, Matplotlib, Plotly
Benchmarks
Lawrence and Fisher–Thompson sets
  • Python
  • NumPy
  • Pandas
  • Metaheuristics
  • Grey Wolf Optimizer
  • Variable Neighborhood Search
  • Job shop scheduling
  • Statistical testing
Two-part diagram of the Grey Wolf Optimizer. Left: a candidate wolf measures its distances to the alpha, beta and delta wolves to estimate where the prey is. Right: wolves around the prey, with the coefficient A marking whether a wolf closes in (|A| < 1) or moves away (|A| > 1).
The original, continuous GWO: each wolf estimates where the prey is from the three leaders (α, β, δ) and moves towards it. For scheduling, that move becomes a crossover.
Problem
Job shop scheduling: order every job's operations on shared machines so that the last one finishes as early as possible.
Starting point
A hybrid Grey Wolf Optimizer: a population of candidate schedules that recombines with its three best members and refines them with local search.
What I added
A per-machine swap mutation, duplicate control and a local search that accepts ties: three ways to keep the search from stalling.
Mean RPD across 22 benchmark instances
2.43%
Baseline: 5.55%. Lower is better.
Instances where the best-known makespan was matched
9 / 22
Baseline: 5 / 22
Instances where the best schedule got worse
0 / 22
14 better, 8 tied

Computed from the thesis results table: baseline (5-mix) against final configuration (MIX-v2). RPD is the percentage above the best-known solution. Mean RPD is the average of the 22 per-instance values.

The order of operations alone can double the finish time

A job shop runs a set of jobs on a set of machines. Each job is a fixed sequence of operations, and each operation needs a specific machine for a known time. A machine handles one operation at a time, an operation cannot be interrupted, and a job's operations must run in order.

The only decision is the order in which each machine processes its operations. The objective is the makespan: the moment the last operation finishes. The toy instance below has three jobs and three machines. Changing nothing but the order takes the makespan from 17 time units to 8.

  • J1M1 2→M2 3→M3 2
  • J2M2 3→M3 2→M1 2
  • J3M3 3→M1 2→M2 2

Same order on every machine: J1, J2, J3

M1
J1J2J3
M2
J1J2J3
M3
J1J2J3
024681012141617
makespan 17

J2 cannot start until t = 5 and J3 until t = 10: each waits for the jobs ranked ahead of it.

Best order: M1 J1, J3, J2 · M2 J2, J1, J3 · M3 J3, J2, J1

M1
J1J3J2
M2
J2J1J3
M3
J3J2J1
024681012141617
makespan 8

M2 never idles, so 8 is also the lower bound: its total load.

Toy instance for illustration (3 jobs × 3 machines), not a benchmark.

A pack of candidate schedules that follows its three best

Even that toy has 216 combinations of machine orders: 152 are impossible because jobs end up waiting on each other in a circle, and only one reaches 8. The count grows factorially with the number of jobs, so realistic instances are handled with metaheuristics, which trade the guarantee of an optimum for good schedules in bounded time.

The Grey Wolf Optimizer (GWO) is a population metaheuristic modeled on a hunting pack. Each wolf is a search agent holding one candidate schedule. The three best are the leaders (alpha, beta and delta), and the rest of the pack is pulled towards them.

The original GWO moves wolves through continuous space, and a schedule is an ordering, not a point. The hybrid version I started from turns "move towards the leaders" into crossover: new schedules inherit parts of the leaders' operation sequences, and a Variable Neighborhood Search (VNS) then refines them.

My thesis, Enhancement of Multi-Agent Grey Wolf Optimizer for Job Shop Scheduling, set out to lower the makespan by improving the balance between exploring new schedules and refining good ones.

One iteration: rank, recombine, refine, mutate, deduplicate

The pack starts as 200 schedules built with initialization rules. Each iteration runs the five stages below, and the number of iterations scales with the size of the instance. Items marked New are my additions.

  1. 01

    Rank

    Sort the pack by makespan

    • Alpha, beta and delta: the three best schedules

  2. 02

    Recombine

    Crossover with alpha, beta and delta

    • POX, keeping the best child
    • PPX as the cheaper alternative

  3. 03

    Refine

    Variable Neighborhood Search

    • Local search over several neighborhoods
    • New: also accepts moves that keep the makespan equal (vns-v2)

  4. 04

    Mutate

    Adaptive mutation

    • Swap, insert and inverse moves
    • New: swap within one machine's sequence (swp_mqn)

  5. 05

    Deduplicate

    Duplicate control

    • New: detect clone schedules
    • New: replace them or mutate them lightly

Both crossovers were tested; the trade-off is in the lessons below. The loop repeats until the iteration budget is spent.

Three changes to keep the pack from stalling

A population search tends to stall in three ways: its moves are too coarse to polish a good schedule, the pack fills up with copies of the same schedule, or local search stops at the first plateau. Each change targets one of them.

ComponentBaseline hybrid GWOFinal configurationWhy it helps
MutationAdaptive swap, insert and inverse movesAdds swp_mqn: swaps two operations within one machine's sequenceRefines the local sequence on one machine
DuplicatesNo check: identical schedules can pile upClones are detected, then replaced or lightly mutatedKeeps the pack diverse; crossover between copies produces nothing new
VNS acceptanceOnly moves that lower the makespan (<)Also moves that keep it equal (≤), in vns-v2Lets the search cross plateaus of equal makespan instead of stopping

In the results below, the final configuration is labelled MIX-v2 and the baseline 5-mix.

Every result is a gap to the best-known solution

A stochastic optimizer can look brilliant on one lucky run. I scored every configuration against published best-known solutions and compared configurations with non-parametric tests.

Makespan
The time at which the last operation finishes. The objective; lower is better.
BKS
Best-known solution: the lowest makespan reported for a benchmark instance.
RPD
Relative percentage deviation, 100 × (makespan − BKS) / BKS. 0% means the best-known solution was matched.
Benchmarks
Lawrence (LA) and Fisher–Thompson (FT) instances. The final comparison covers FT06, FT10, FT20, LA01–LA04 and LA16–LA30.
Wilcoxon test
Compares two configurations at a time.
Friedman + Nemenyi
Ranks several configurations at once; the Nemenyi post-hoc test shows which pairs differ.
Setup
200 wolves; the number of iterations scales with the size of each instance.

The mean gap shrank on 21 of 22 instances

Mean RPD per instance, baseline against final configuration. The one exception, FT06, was already at 0% for both.

Mean RPD (%)

The mean gap shrank on 21 of 22 instances
051015FT06FT10FT20LA01LA02LA03LA04LA16LA17LA18LA19LA20LA21LA22LA23LA24LA25LA26LA27LA28LA29LA30

Benchmark instance

The mean gap shrank on 21 of 22 instances
CategoryBaseline (5-mix)Final (MIX-v2)
FT060%0%
FT108.08%4.71%
FT207.97%1.43%
LA010.02%0%
LA021.77%0.78%
LA034.34%2.73%
LA040.8%0.15%
LA165.72%3.56%
LA172.69%0.64%
LA182.65%1.16%
LA194.13%2.81%
LA203.73%2.04%
LA217.56%4.04%
LA2210.32%4.05%
LA231.73%0.1%
LA247.97%4.12%
LA259.53%3.79%
LA265.56%1.44%
LA2710.18%5.55%
LA289.18%2.85%
LA2911.81%7.53%
LA306.34%0%

Source: Thesis results table. MSc in Artificial Intelligence, Polytechnic University of Madrid, 2024.

Best schedules: 14 better, 8 tied, none worse

The best makespan found per instance, next to the mean RPD. ✓ marks a match with the best-known solution: 9 instances for the final configuration, 5 for the baseline.

InstanceBKSBaseline: mean RPD (%)Baseline: bestFinal: mean RPD (%)Final: best
FT06550.0055 ✓0.0055 ✓
FT109308.089374.71936
FT2011657.9711961.431178
LA016660.02666 ✓0.00666 ✓
LA026551.77655 ✓0.78655 ✓
LA035974.346032.73603
LA045900.80590 ✓0.15590 ✓
LA169455.729803.56946
LA177842.697920.64784 ✓
LA188482.658611.16848 ✓
LA198424.138502.81850
LA209023.739072.04907
LA2110467.5610804.041069
LA2292710.329934.05935
LA2310321.731032 ✓0.101032 ✓
LA249357.979664.12951
LA259779.5310333.79983
LA2612185.5612611.441218 ✓
LA27123510.1812975.551264
LA2812169.1812902.851241
LA29115211.8112217.531207
LA3013556.3413750.001355 ✓

Source: thesis results table. Baseline = 5-mix, final = MIX-v2.

Ties in VNS came free; a cheaper crossover did not

What worked

  • Accepting ties in VNS added exploration without degrading final quality.
  • POX with best-child selection produced slightly better final schedules than PPX.

What did not, or not yet

  • PPX needed fewer fitness evaluations but gave up some final quality, so operators have to be judged on quality and compute cost together.
  • Runs still vary: on FT10 the best schedule is 0.65% above the BKS, but the mean RPD is 4.71%.
  • LA29 and LA27 remain the furthest from best-known, at 7.53% and 5.55% mean RPD.

Next: adaptive mutation, tabu memory and more objectives

  • Drive mutation with a measure of population similarity, so the search reacts as soon as the pack starts to converge.
  • Add Tabu Search to filter moves that revisit known schedules and cut redundant evaluations.
  • Try discrete GWO variants (DGWO, BGWO) and multi-objective versions that also weigh energy use or due dates.

Next case study

TempoParking: a live parking directory built with AI agents

Recorded 15-minute SOL window: the Binance ask (blue, left axis, 78.4 to 78.9) plotted against the Polymarket Up bid (orange, right axis, 0 to 0.9) over 900 seconds

Market systems2025–2026Stopped

Polymarket trading systems

Prediction-market research: a dataset builder, a 15-minute bot and a Rust + Python HFT recorder.

Get in touch

Working on something similar? I am happy to compare notes.

Email meContact form