Timetable optimisation : an application of integer programming

Abstract

This work includes a deep insight regarding Integer Programming. Since there is no universal algorithm to solve Integer Linear Programming models (ILP models), there exist many different algorithms in order to attempt to solve these models faster and yield better results. Some algorithms, the so-called General Algorithms can be applied to any ILP model. Those studied are mainly the Branch-and-Bound, Gomory's Cutting Plane and the Branch-and-Cut method. Other algorithms which exploit the structure of the ILP model are studied. There are referred to as Special Purpose Algorithms. Variations of these algorithms are also studied. A very useful application regarding Integer Programming is presented. It is about generating an optimal schedule regarding examination timetables. Up to now this schedule has been done manually, which is a very time consuming task involving a great deal of trial and error, and the outcome may not be that satisfactory. An alternative way that is faster and yields satisfactory results is studied. This study is based on the current students belonging to different chosen Faculties and the results apply to June 2003 Assessment session. The generated results are analysed and compared with the current schedule done manually by the Faculty Officer.