Hospital timetabling at IHTC 2024
All 30 instances solved, every mandatory patient admitted
Task
Decide when each surgical patient is admitted, to which room and operating theater, and which nurse covers each room in every shift. An instance spans 14 to 28 days, with up to 493 patients, 33 rooms and 65 nurses, and gets ten minutes of computing time.
Hard rules: no mixed genders in a room, compatible rooms only, surgeon and theater time limits, admission windows, room capacity, every mandatory patient admitted, every occupied room covered in every shift. Soft goals, weighted per instance: age mix, nurse skill and workload, continuity of care, open theaters, surgeon transfers, admission delay and optional patients left out.
Approach
01Small instances in one piece
When the instance is small enough, a single MILP decides patients, theaters and nurses together.
02Patients and theaters first
For everything else, a first MILP admits patients and assigns rooms and theaters. One pair of constraints handles gender separation and room capacity together, and an aggregate nurse capacity per shift anticipates the second stage.
03Nurses day by day, then all at once
One small nurse MILP per day, a few seconds each, builds a roster that warm-starts a model over the whole horizon for the time that remains. It trades skill shortfall, excess workload and continuity of care.
04A leaner first stage for the largest instances
On six of the largest instances, theater and surgeon decisions move into a model of their own. The first stage shrinks to a fraction of its rows, admits more patients, and the total cost of those six falls by 8%.
05Local search on top
Starting from the MILP solution: move an unscheduled patient into the slot of a scheduled optional one, or drop an optional patient. Every candidate is priced by per-component deltas over a vectorised state, with restarts until nothing improves.
06Measure every variant
Each run was scored with the official validator, and about twenty pipeline variants were compared across all 30 instances before the final choice.
Result
Solutions for all 30 public instances with every mandatory patient admitted: 5,421 of 6,622 patients in total.
The leaner first stage cut the cost of the six largest instances by 8%; local search then improved 11 of the 30 by a smaller margin.