Using Integer Programming to Solve Scheduling Problems
Abstract
The problem of timetabling final examinations is one which is
faced by most educational institutions, with the problem becoming
particularly acute in institutions of higher education. The
situation may be formulated as a 0-1 integer programming problem,
but considering the size of the problem running this algorithm to
optimality takes a long time. The procedure described is a
multi-phased scheduling model that first finds a basic feasible
solution to the 0-1 integer programming problem assigning a set
of examinations to a fixed number of examination periods so that
no student is required to take more than one examination at a time.
Then a heuristic approach is used to further optimize the result
to include secondary constraints such as no student can have more
than 2 examinations within a 24 hour period and faculty preferences.
A computer program to implement the procedure was developed
and was found to produce a better timetable than the manual
procedure as well as a considerable saving in clerical effort.
Table of Contents
Complete List of References
- [AT1]
Arani, Taghi and Lotfi, Vahid.
A Three Phased Approach to Final Exam Scheduling.
IIE Transactions, 21(1): 86 — 96, 1989.
- [AZ1]
Azimi, Z. N.
Hybrid Heuristics for Examination Timetabling Problem.
Applied Mathematics and Computation, 163(2): 705 — 733, 2005.
- [CM1]
Carter, Michael W., Laporte, Gilbert and Lee, Sau Yan.
Examination Timetabling: Algorithmic Strategies and Applications.
The Journal of the Operational Research Society, 47(3): 373 — 383, 1996.
- [CM2]
Carter, Michael W.
A Survey of Practical Applications of Examination Timetabling Algorithms.
Operations Research, 34(2): 193 — 202, 1986.
- [CR1]
Cerveny, Robert and Lotfi, Vahid.
A Final-Exam-Scheduling Package.
The Operational Research Society, 42(3): 205 — 216, 1991.
- [DK1]
Dowsland, Kathryn A. and Thompson, Jonathan M.
A robust simulated annealing based examination timetabling system.
Computers & Operations Research, 25(7,8): 637 — 649, 1998.
- [EJ1]
Evans, James R.
Optimization algorithms for networks and graphs.
New York: M. Dekker, 1992.
- [JD1]
Johnson, David.
Timetabling University Examinations.
The Journal of the Operational Research Society, 41(1): 39 — 47, 1990.
- [LG1]
Laporte, Gilbert and Desroches, Sylvain.
Examination Timetabling by Computer.
Computers & Operations Research, 11(4): 351 — 361, 1984.
- [NE1]
Nering, Evar D.
Linear programs and related problems.
Boston: Academic Press, 1993.
- [SJ1]
Scott, J. L.
A Heuristic Algorithm for Examination Timetabling.
New Zealand Operations Research, 8(2): 103 — 108, 1980.
