Mixed Integer Linear Programming Models for University Timetabling

Abstract

The construction of an effective and satisfying weekly timetable has always been a key challenge of every university administrator. Mathematically, the problem is to optimise an objective function that reflects the value of the schedule subject to a set of constraints that relate to various operational requirements and a range of resource constraints (lecturers, rooms, etc). The usual objective is to maximise the total preferences or to minimise the total number of students affected by clashes. The problem can be conveniently expressed as a Mixed Integer Linear Programming (MILP) problem. The computational difficulty is due to the integer restrictions on the variables. Various computational models including both heuristics and exact methods have been proposed in the literature. In this paper, we present MILP models which incorporate all hard constraints and the desirable soft constraints. Hard constraints are the types that are not meant to be violated in any situation such as the conflict, sequence and operational constraints. The soft constraints are the ones which can be treated as non-essential but stimulates circumstances that are optional, namely preferences of students and lecturers to time and rooms. Randomly generated data and available literature data are used to test and evaluate our models. AIMMS 3.11 mathematical software is employed as a tool to solve the models with CPLEX 12.1 as the solver. The computational results are favourable.