Mixed Integer Linear Programming Models for University Timetabling
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 operatio...
| Main Authors: | , |
|---|---|
| Format: | Journal Article |
| Published: |
Chiang Mai University, Faculty of Science
2012
|
| Online Access: | http://hdl.handle.net/20.500.11937/27976 |
| _version_ | 1848752412197650432 |
|---|---|
| author | Caccetta, Louis Aizam, Nur Aidya |
| author_facet | Caccetta, Louis Aizam, Nur Aidya |
| author_sort | Caccetta, Louis |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T08:08:12Z |
| format | Journal Article |
| id | curtin-20.500.11937-27976 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T08:08:12Z |
| publishDate | 2012 |
| publisher | Chiang Mai University, Faculty of Science |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-279762017-01-30T13:02:21Z Mixed Integer Linear Programming Models for University Timetabling Caccetta, Louis Aizam, Nur Aidya 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. 2012 Journal Article http://hdl.handle.net/20.500.11937/27976 Chiang Mai University, Faculty of Science restricted |
| spellingShingle | Caccetta, Louis Aizam, Nur Aidya Mixed Integer Linear Programming Models for University Timetabling |
| title | Mixed Integer Linear Programming Models for University Timetabling |
| title_full | Mixed Integer Linear Programming Models for University Timetabling |
| title_fullStr | Mixed Integer Linear Programming Models for University Timetabling |
| title_full_unstemmed | Mixed Integer Linear Programming Models for University Timetabling |
| title_short | Mixed Integer Linear Programming Models for University Timetabling |
| title_sort | mixed integer linear programming models for university timetabling |
| url | http://hdl.handle.net/20.500.11937/27976 |