Three ways to build a university timetable — particle swarm optimisation, a genetic algorithm, and the hyperheuristic that runs one after the other — implemented so you can tell whether the hybrid actually earns its keep.
If you came to use it, start at Install. If you came to learn how metaheuristics are honestly compared, start at The problem and read straight through.
Thirty seeds per method. The hybrid matches the genetic algorithm's median while spending about
twice the objective evaluations — a negative result the original single-run report could not have
produced. Reproduce with python scripts/make_figures.py.
Written in 2017 for the undergraduate course Proyecto Integrador at Universidad de
Antioquia by John Edisson Tapias Zarrazola and Carlos A. Peña Montenegro. The original
report (Spanish) is in docs/; the original scripts are one git checkout away.
pip install git+https://github.com/Kemquiros/timetabling-metaheuristicsNo runtime dependencies. Python 3.11 or newer.
from timetabling import CourseCode, Instance, SwarmConfig, pso
instance = Instance(
groups=4,
slots=4,
teachers=8,
catalogue={1: CourseCode(teacher=1, subject=2), 2: CourseCode(teacher=1, subject=4)},
)
result = pso.optimise(instance, SwarmConfig(iterations=60), seed=42)
print(result.best_fitness, result.evaluations) # penalty, and what it cost to get thereA timetable assigns one course to each (group, time slot) pair. With 4 groups and 4 slots
that is 16 decisions; with 18 available courses the space holds 18¹⁶ ≈ 1.2 × 10²⁰ timetables.
Enumerating that is not slow — it is impossible. This is the regime metaheuristics exist for: no gradient, no structure to exploit, and far too many candidates to visit. You are not going to find the optimum. You are going to find a good one, and be honest about how much you paid.
Every point in the space is a syntactically valid timetable. The difficulty is not building a legal encoding; it is that most legal timetables are bad. Quality is measured by three penalties, summed, lower being better:
| Term | What it punishes | Why it matters |
|---|---|---|
group_clashes |
the same course twice for one group | this is what makes a timetable wrong, not merely awkward |
idle_teachers |
leaving teachers on the roster unused | a timetable that overworks two people and idles six is unusable in practice |
load_imbalance |
leaning on a handful of courses | spreads demand across the catalogue |
A modelling choice worth arguing with. The three terms are summed unweighted, so one scheduling clash counts exactly as much as one unit of imbalance. That is almost certainly wrong — a clash is a hard failure, imbalance is a preference — but it is preserved from the 2017 formulation so results stay comparable. If you extend this, weighting the terms is the first experiment to run, and the README should be updated with what you find.
The intuition. Scatter particles across the space. Each remembers the best place it has been; each also knows the best place its neighbours have been. Every step, a particle is pulled toward both, and keeps some of its previous velocity:
The part that is easy to get wrong. A timetable is discrete — course codes are integers. But a swarm restricted to integers cannot accumulate velocity: every step rounds away the momentum, and the method collapses into random search wearing a costume.
So the positions here are continuous, and rounded onto course codes only at the moment of evaluation. The swarm flies through a continuous shadow of a discrete problem. That indirection is the whole trick, and it is why PSO works on combinatorial problems at all.
Why constriction = 0.72984. With SwarmConfig object instead of as loose arguments, and why the config raises if
The intuition. Keep a population. Repeatedly: pick good parents, mix them, mutate a little, replace the population. Good sub-timetables spread; bad ones die out.
Two design choices, and their reasons:
- Uniform crossover, not single-point. Single-point crossover assumes neighbouring genes belong together. Here a gene is a (group, slot) pair — a contiguous slice carries no more meaning than a scattered one, so cutting at one point buys nothing.
- Tournament selection, not fitness-proportionate. The objective is an unbounded penalty, not a probability. Proportionate selection would need a transformation whose scale silently controls the selection pressure — a hidden hyperparameter. Tournaments only need the ordering.
Elitism carries the best individuals through untouched, which is what makes the history monotone: the incumbent can never get worse. The test suite asserts exactly that.
Run the swarm; hand its best timetable to the genetic algorithm as a seed. The swarm explores the continuous relaxation and finds promising basins fast; the GA then works in the discrete space, where crossover can recombine partial timetables the swarm has no way to express.
Here is the part most reports get wrong. A hybrid that runs 60 swarm iterations and 60 generations has spent roughly twice the objective evaluations of either component alone. If you compare "hybrid at 60 iterations" against "PSO at 60 iterations" and the hybrid wins, you have learned nothing: you gave it twice the budget.
That is why every result here carries evaluations:
result.evaluations # objective evaluations spent — the real currency
result.iterations # loop count — NOT comparable across methodsCompare at equal evaluations, never at equal iterations. If the hybrid still wins, the
combination is doing real work. This single field is the difference between an experiment and an
advertisement.
Left: the hybrid's first phase is the swarm run — same seed, same particles — so the two curves coincide until the genetic stage begins, which is why PSO is drawn as a wide translucent underlay. Right: the same runs charged for what they spent.
Over thirty seeds on the 2017 instance:
| Method | Median penalty | Best | Worst | Relative cost |
|---|---|---|---|---|
| PSO | 2.143 | 0.600 | 3.333 | 1× |
| GA | 0.333 | 0.143 | 2.143 | ≈1× |
| PSO → GA | 0.333 | 0.000 | 1.600 | ≈2× |
The hybrid matches the genetic algorithm's median while spending roughly twice the evaluations. It reaches a perfect timetable on its best seed, which the GA alone never does, and its worst case is better — so it buys reliability, not average quality.
That is a modest, honest claim. It is also the opposite of what a single run compared at equal
iterations would have suggested, and it is the reason this repository reports evaluations at
all.
result.best # the timetable
result.best_fitness # total penalty; 0 would be perfect
result.evaluations # what it cost
result.history # best-so-far after each iterationPlot history for all three methods on the same axes, with evaluations on the x-axis rather
than iterations. That plot is the actual finding of this project, and it looks very different
from the same plot drawn against iterations.
The original runs are preserved in legacy/experiments/ with their
parameters and convergence plots, and the report is in docs/ (Spanish).
Treat them as a record, not as evidence. They were single runs, without seeds, compared at equal iterations rather than equal evaluations — so they cannot settle whether the hybrid beats plain PSO. Reproducing them properly under the protocol above is the obvious next piece of work, and it is stated as open here rather than quietly implied to be settled.
git clone https://github.com/Kemquiros/timetabling-metaheuristics && cd spso-ga
pip install -e ".[dev]"
pytest # 19 tests
ruff check . # lint
mypy # strict type checking
python scripts/make_figures.py # regenerate the figures, and print the seed tableTests assert properties, not outputs: that a seeded run reproduces, that elitism makes the incumbent monotone, that the hybrid is never worse than its own swarm stage, that the evaluation count matches the arithmetic of the loop.
The original coursework is preserved as an annotated git tag rather than a directory, so the repository reads as a tool while the evidence stays one command away:
git checkout coursework-2017| 2017 | Now | Why |
|---|---|---|
Python 2, from __future__ import division, from random import *
|
Python 3.11+, explicit imports | the scripts run on no supported interpreter |
constrain2 summed per-teacher occurrence counts |
counts distinct teachers | the sum always equalled the length of the solution vector, so the term was the same constant for every candidate and applied no selection pressure at all — one of the three constraints was inert |
Instance hard-coded as module-level args and param dicts |
Instance and config dataclasses, validated |
no second instance could be run without editing the source |
| No seeding | explicit seed on every search |
an unseeded metaheuristic result cannot be reproduced by a reader |
| Cost reported as iterations |
evaluations reported alongside |
iterations are not comparable between a swarm and a hybrid |
| Constriction factor and coefficients as loose globals | one SwarmConfig, validated |
|
Original coursework: John Edisson Tapias Zarrazola and Carlos A. Peña Montenegro, Universidad de Antioquia, 2017.
- Clerc & Kennedy (2002), The particle swarm — explosion, stability, and convergence in a multidimensional complex space — where the constriction factor comes from, and why.
- Eiben & Smith, Introduction to Evolutionary Computing — the standard text; chapters 3–6.
- Burke et al. (2013), Hyper-heuristics: a survey of the state of the art — the framing this project's PSO→GA pipeline belongs to.
See CITATION.cff, or:
Tapias Zarrazola, J. E. & Peña Montenegro, C. A. timetabling: particle swarm, genetic and hybrid metaheuristics for university timetabling. Version 1.0.0, 2026. https://github.com/Kemquiros/timetabling-metaheuristics
MIT — see LICENSE.