All work

Course-to-Room Allocator

A feasible university timetable, found by local search

Role
Built all 9 soft constraints and both objective functions
Team
6 people
Timeline
Status
Complete
Stack
Python, Simulated Annealing, Hill Climbing, Tabu Search, CSP
Schematic, not the real timetable: sessions placed in a weekly grid of rooms and time slots.

Problem

Every semester a university has to fit its classes into a limited number of rooms and time slots. A timetable can be valid and still be a bad week for students: long walks between rooms, courses that keep changing rooms, small groups in large halls.

The Course-to-Room Allocator builds the assignment for ENSIA automatically and aims to beat the one currently in use.

Context and constraints

The data is real: floor plans and course lists from the ENSIA administration. The approach was also benchmarked on ITC2007, the international timetabling competition dataset.

A timetable only counts if it meets every hard constraint:

  • No room holds more students than it has seats.
  • A session that needs a lab gets the right kind of room.
  • No room is booked twice at the same time.

On top of that sit nine soft constraints that measure how good a valid timetable is. They include student travel between rooms, gaps in a group’s day, keeping a course in the same room through the semester, and not wasting large rooms on small groups.

My role

This was a team of six. I implemented all nine soft constraints and both objective functions, the part of the system that scores a timetable and tells the search which of two candidates is better. I also managed the repository.

Approach

  1. ENSIA data Rooms, floor plans and class lists.
  2. CSP start A first timetable that meets the hard constraints.
  3. Cost Nine soft constraints, two objective functions.
  4. Local search Hill Climbing, Simulated Annealing, Tabu Search.
  5. Timetable Feasible, then compared with the current one.
From ENSIA's data to a timetable.

Constraint satisfaction builds the starting timetable, so the search begins from something valid. Three local-search methods then ran against the same cost so they could be compared fairly. Hill Climbing only accepts improvements. Simulated Annealing also accepts some worse moves early on, which lets it leave a poor local optimum. Tabu Search remembers recent moves so it does not go back to them.

Results

  • The system produced a feasible timetable on ENSIA’s real data.
  • That timetable beat the school’s current assignment on every soft-constraint metric, student travel and schedule gaps included.
  • Simulated Annealing outperformed Hill Climbing and Tabu Search.

What I’d do differently

The penalty terms in the cost were not on the same scale, so they did not weigh against each other the way we intended. I found and fixed that mismatch during the project.

Next steps