Annals of Operations Research · 2010 · 13 citations · 12 references
ComputingComputer ScienceMathematicsAlgorithmsOptimizationSchedulingAssignment ProblemsConstraint HandlingConstraint SatisfactionInteger ProgrammingResource-constrained SchedulingColumn GenerationColumnsConstraintsScheduling ConstraintsScheduling HeuristicsScheduling ProblemsSoft Constraint SatisfactionTimetabling
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.
12
Selected Topics in Column Generation
Marco E. Lübbecke, Jacques Desrosiers · Operations Research · 2005 · 1.1K citations
ITC2007 solver description: a hybrid approach
Tomáš Müller · Annals of Operations Research · 2009 · 148 citations
Recent developments in practical course timetabling
M. W. Carter, Gilbert Laporte · Lecture notes in computer science · 1998 · 128 citations
Management, Teaching, Scheduling +3