An IP‐based heuristic for the post enrolment course timetabling problem of the ITC2007

An IP‐based heuristic for the post enrolment course timetabling problem of the ITC2007

0.00 Avg rating0 Votes
Article ID: iaor2012866
Volume: 194
Issue: 1
Start Page Number: 439
End Page Number: 454
Publication Date: Apr 2012
Journal: Annals of Operations Research
Authors: ,
Keywords: heuristics: local search, programming: linear, programming: integer, education
Abstract:

Track 2 of the international timetabling competition 2007 was a post enrolment course timetabling problem. A set of events has to be assigned to a timeslot and to a room such that all students are able to attend their requested events while not violating the hard constraints. There are also soft constraints that make the timetable ‘nicer’. We present a deterministic heuristic that assigns events to timeslots based on an LP‐solution constructed with column generation. We get an integer solution by fixing columns one at a time. This heuristic finds a solution that obeys all the hard constraint for 23 of the 24 instances of the competition. The generated solution is improved by selecting a set of events that are reassigned by solving an integer program. This IP minimizes the number of soft constraint violations under the restriction that no hard constraints are violated. Comparing the results of our heuristic with the results of the five finalists of the competition, shows that our approach is competitive.

Reviews

Required fields are marked *. Your email address will not be published.