Tabu Search Techniques for Large High-School Timetabling Problems

AAAI 1996

TL;DR

This paper presents a Tabu Search (TS) algorithm designed to tackle the complex problem of creating high school timetables. By combining TS with a Randomized Non-Ascendent (RNA) method and adaptive constraint relaxation, the algorithm efficiently generates high-quality timetables that outperform manual methods.

What Problem Does This Paper Address?

Creating a weekly timetable for a high school is a notoriously difficult optimization problem. It involves assigning thousands of lectures to specific time slots and classrooms while satisfying a multitude of constraints. These constraints include ensuring no teacher or class is double-booked, accommodating teacher and class availabilities, and meeting specific pedagogical requirements like having a certain number of lectures per day or ensuring certain lectures are taught consecutively. Manually creating these timetables is a time-consuming and often unsatisfactory process. Previous automated approaches have included simulation, integer programming, graph coloring, simulated annealing, and genetic algorithms, but the authors aim to improve upon these with a refined Tabu Search approach.

Methods

The core of the proposed solution is a Tabu Search (TS) algorithm. TS is a metaheuristic that explores the solution space by iteratively moving from the current solution to a neighbor solution, even if the neighbor is worse, to avoid getting stuck in local optima. To prevent cycling, a "tabu list" keeps track of recently used moves, making them temporarily forbidden.

Key innovations in this paper include:

  • Combined RNA and TS: The algorithm interleaves phases of Randomized Non-Ascendent (RNA) search with Tabu Search. RNA is used to generate initial solutions and to "shake up" the search when TS gets stuck.
  • Atomic and Double Moves: The neighborhood exploration uses "atomic moves" (swapping two lectures for a teacher) and "double moves" (a pair of atomic moves designed to repair infeasibilities created by the first move).
  • Adaptive Relaxation of Constraints: Hard constraints (like no double-booking) are embedded into the objective function with a high penalty weight. This weight is adaptively adjusted during the search. If a constraint is consistently satisfied over a window of moves, its penalty is reduced; if it's consistently violated, the penalty increases. This allows the search to explore infeasible regions when necessary to find better overall solutions.
  • Aspiration Function: A mechanism that allows a tabu move to be accepted if it leads to a solution better than the current best-found solution, overriding the tabu status.

Datasets

The authors experimented with three schools:

  1. A small, artificial "dummy" school created for extensive parameter tuning.
  2. A large real-world school with 20 classes, 44 teachers, and 632 lectures.
  3. A larger real-world school with 38 classes, 61 teachers, and 1098 lectures.

The paper notes the absence of a common definition for the problem and widely-accepted benchmarks, making direct comparison with other algorithms challenging.

Key Insights and Ideas

  • The Power of Hybridization: Combining different search strategies (RNA and TS) and move types (atomic and double) proved more effective than using a single approach.
  • Adaptive Constraint Handling is Crucial: Dynamically adjusting the penalty weights for infeasibilities is key to navigating the complex search space and finding feasible solutions that are also optimal. This is particularly important for "hard" constraints that are difficult to satisfy.
  • Interactive Timetabling Advantage: The algorithm's ability to start from any timetable and allow manual modifications makes it well-suited for interactive timetabling, a practical necessity for school staff.
  • Beyond Constructive Methods: While constructive algorithms might leave a small percentage of lectures unscheduled, this TS approach aims to schedule all lectures, providing a complete timetable.

Key Results

  • For the second school (20 classes, 44 teachers, 632 lectures), an objective value of 54 was achieved in 64 minutes. Further refinement yielded a timetable with an objective value of 28, significantly better than the manually produced timetable's value of 172.
  • For the third school (38 classes, 61 teachers, 1098 lectures), an objective value of 51 was obtained in 272 minutes. This is a substantial improvement over the manually produced timetable's objective value of 279.
  • In all tested cases, the timetables produced by the algorithm were better than hand-made ones.

Limitations and Future Work

  • Lack of Standard Benchmarks: The authors highlight the difficulty in comparing their results directly with other published work due to the absence of standardized datasets and problem definitions.
  • Interactive vs. Batch: While the algorithm supports both interactive and batch modes, the paper focuses more on the batch generation aspect. The interactive capabilities are mentioned as an advantage but not deeply explored in terms of user experience or specific interaction paradigms.
  • Parameter Tuning: The performance of the algorithm is sensitive to parameter settings (e.g., tabu list size, aspiration function, relaxation factors), and tuning these for different schools is necessary.
  • Future Work: The paper suggests that further exploration of different aspiration functions and move types could yield additional improvements. The authors also implicitly point to the need for standardized benchmarks to facilitate more rigorous comparisons within the field.

Summary updated

BibTeX
@inproceedings{1996tabu,
  title = {{Tabu Search Techniques for Large High-School Timetabling Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure