Article ID: | iaor20042637 |
Country: | United Kingdom |
Volume: | 54 |
Issue: | 11 |
Start Page Number: | 1155 |
End Page Number: | 1166 |
Publication Date: | Nov 2003 |
Journal: | Journal of the Operational Research Society |
Authors: | Tamiz M., Mardle S.J., Mirrazavi S.K. |
Keywords: | education, programming: multiple criteria |
The timetabling problem is generally large, highly constrained and discrete in nature. This makes solution by exact optimisation methods difficult. Therefore, often a heuristic search is deemed acceptable providing a simple (non-optimal) solution. This paper discusses the timetabling problem for a university department, where a large-scale integer goal programming (IGP) formulation is implemented for its efficient optimal solution in two phases. The first phase allocates lectures to rooms and the second allocates start-times to lectures. Owing to the size and complicated nature of the model, an initial analysis procedure is employed to manipulate the data to produce a more manageable model, resulting in considerable reductions in problem size and increase of performance. Both phases are modelled as IGPs. Phase 1 is solved using a state-of-the-art IGP optimization package. However, due to the scale of the model, phase 2 is solved to optimality using a genetic algorithm approach.