Mathematical Programming Formulations for the Examinations Timetable Problem
Loading...
Date
2004-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
African Journal of Science and Technology (AJST)
Abstract
Examinations Timetabling Problem (ETP) is the problem of assigning courses to be
examined and candidates to time periods and examination rooms while satisfying a set of constraints.
Every University has a different set of constraints and structure of examinations. Thus there is no
general ETP model for all Universities around the world [1]. ETP is NP-Hard [2] and therefore no
optimal algorithm is known for this problem which can solve a general problem within reasonable
time. However, exact methods can be used to provide a benchmark for the heuristic methods. There
is no general model for University Timetabling Problems because the problem feature differs from
one University to another. In this paper we focus in the formulation of the ETP for the University of
Dar as salaam. We formulate, test and compare three Integer Programming models. It is concluded
that, although exact methods cannot give a solution to a real-size problem, these models give a
good benchmark for testing the performance of other approaches. This paper also gives a direction
for better exact models for the University of Dar es salaam’s ETP.
INTRODUCTION
The Examination-Timetabling Problem (ETP) essentially
involves the assignment of courses to be examined and
their candidates to time periods and examination rooms
while satisfying a given set of constraints. These
constraints are divided into hard and soft [i], [ii]. Hard
constraints must be satisfied such as avoiding studentexamination
collision and room over-sizing. Soft
constraints may
Description
Keywords
Mathematical Programming, Examinations Timetabling, Combinatorial Optimization