Penalising Patterns in Timetables: Novel Integer Programming Formulations
| Authors | |
|---|---|
| Year of publication | 2008 |
| Type | Article in Proceedings |
| Conference | Operations Research Proceedings 2007 |
| MU Faculty or unit | |
| Citation | |
| Web | |
| Field | Informatics |
| Keywords | integer programming; course timetabling; patterns |
| Description | Many complex timetabling problems, such as university course timetabling and employee rostering, have an underpinning graph colouring component, a pattern penalisation component and a number of side constraints. In real-life settings, it might be relatively easy to come up with feasible solutions to instances of graph colouring, which correspond to hard constraints such as ``each student attends all events of courses of his choice and no student can be in two rooms at the same time'' even for hundreds of events and hundreds of distinct enrollments. Much more challenging are requirements such as ``students should not have gaps in their individual daily timetables'', which often make the problem over-constrained. On the example of the Udine Course Timetabling Problem, this paper studies several integer programming formulations of such pattern penalising constraints. |
| Related projects: |