Integer Programming
European Journal of Operational Research 153 (2004) 117–135 www.elsevier.com/locate/dsw An integer programming formulation for a case study in university timetabling
S. Daskalaki b a,*
, T. Birbas b, E. Housos
b
a
Department of Engineering Sciences, University of Patras, GR-26500 Rio Patras, Greece
Department of Electrical and Computer Engineering, University of Patras, GR-26500 Rio Patras, Greece
Abstract
A novel 0–1 integer programming formulation of the university timetabling problem is presented. The model provides constraints for a great number of operational rules and requirements found in most academic institutions.
Treated as an optimization problem, the objective is to minimize a linear cost function. With this objective, it is possible to consider the satisfaction of expressed preferences regarding teaching periods or days of the week or even classrooms for specified courses. Moreover, with suitable definition of the cost coefficients in the objective function it is possible to reduce the solution space and make the problem tractable. The model is solvable by existing software tools with IP solvers, even for large departments. The case of a five-year Engineering Department with a large number of courses and teachers is presented along with its solution as resulted from the presented IP formulation.
Ó 2003 Elsevier B.V. All rights reserved.
Keywords: Timetabling; Integer programming; University timetabling
1. Introduction
The construction of a timetable that satisfies all operational rules and needs in an academic institution, while at the same time fulfills as many of the wishes and requirements of the staff and the students is an important but extremely difficult task for the staff involved. In most institutions this task is left to administrative staff and the current practice is to replicate the timetables of previous years with minor changes to accommodate newly developed situations. However, in recent years, changes occur
S. Daskalaki b a,*
, T. Birbas b, E. Housos
b
a
Department of Engineering Sciences, University of Patras, GR-26500 Rio Patras, Greece
Department of Electrical and Computer Engineering, University of Patras, GR-26500 Rio Patras, Greece
Abstract
A novel 0–1 integer programming formulation of the university timetabling problem is presented. The model provides constraints for a great number of operational rules and requirements found in most academic institutions.
Treated as an optimization problem, the objective is to minimize a linear cost function. With this objective, it is possible to consider the satisfaction of expressed preferences regarding teaching periods or days of the week or even classrooms for specified courses. Moreover, with suitable definition of the cost coefficients in the objective function it is possible to reduce the solution space and make the problem tractable. The model is solvable by existing software tools with IP solvers, even for large departments. The case of a five-year Engineering Department with a large number of courses and teachers is presented along with its solution as resulted from the presented IP formulation.
Ó 2003 Elsevier B.V. All rights reserved.
Keywords: Timetabling; Integer programming; University timetabling
1. Introduction
The construction of a timetable that satisfies all operational rules and needs in an academic institution, while at the same time fulfills as many of the wishes and requirements of the staff and the students is an important but extremely difficult task for the staff involved. In most institutions this task is left to administrative staff and the current practice is to replicate the timetables of previous years with minor changes to accommodate newly developed situations. However, in recent years, changes occur
References: [1] E.A. Akkoyunlu, A linear algorithm for computing the optimum university timetable, The Computer Journal 16 (4) (1973) 347– 350. [2] J. Aubin, J.A. Ferland, A large scale timetabling problem, Computers and Operational Research 18 (1989) 67–77. [3] M.A. Badri, D.L. Davis, D.F. Davis, J. Hollingsworth, A multi-objective course scheduling model: Combining faculty preferences for courses and times, Computers and Operations Research 25 (4) (1998) 303–316. [7] T. Birbas, S. Daskalaki, E. Housos, Timetabling for Greek high schools, Journal of Operational Research Society 48 (1997) 1191– 1200. [9] J.A. Breslaw, A linear programming solution to the faculty assignment problem, Socio-Economic Planning Science 10 (1976) 227– 230. [11] M.W. Carter, G. Laporte, Recent developments in practical course scheduling, in: E. Burke, M. Carter (Eds.), Practice and Theory of Timetabling II, Springer-Verlag, 1998, pp [12] D. Costa, A tabu search algorithm for computing an operational timetable, European Journal of Operational Research 76 (1994) 98–110. [13] S.B. Deris, S. Omatu, H. Ohta, P. Samat, University timetabling by constraint-based reasoning: A case study, Journal of the Operational Research Society 48 (1997) 1178–1190. [14] M. Dimopoulou, P. Miliotis, Implementation of a university course and examination timetabling system, European Journal of Operational Research 130 (2001) 202–213. [15] J.J. Dinkel, J. Mote, M.A. Venkataramanan, An efficient decision support system for academic course scheduling, Operations Research 37 (6) (1989) 853–864. [16] A. Drexl, F. Salewski, Distribution requirements and compactness constraints in school timetabling, European Journal of Operational Research 102 (1997) 193–214. [18] H.A. Eiselt, G. Laporte, Combinatorial optimization problems with soft and hard requirements, Journal of Operational Research Society 38 (9) (1987) 785–795. [19] J. Ferland, S. Roy, Timetabling problem for university as assignment of activities to resources, Computers and Operations Research 12 (2) (1985) 207–218. [20] K. Gosselin, M. Truchon, Allocation of classrooms by linear programming, Journal of Operational Research Society 37 (6) (1986) 561–569. [21] A. Hertz, Find a feasible course schedule using tabu search, Discrete Applied Mathematics 35 (1992) 255–270. [22] T.H. Hultberg, D.M. Cardoso, The teacher assignment problem: A special case of the fixed charge transportation problem, European Journal of Operational Research 101 (1997) 463–473. [23] E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh, Progress in linear programming based branch-and-bound algorithms: An exposition, INFORMS Journal on Computing 12 (2000). [24] L. Kang, G.M. White, A logic approach to the resolution of constraints in timetabling, European Journal of Operational Research 61 (1992) 306–317. [25] N.L. Lawrie, An integer linear programming model of a school timetabling problem, The Computer Journal 12 (1969) 307–316. [26] R.H. McClure, C.E. Wells, A mathematical programming model for faculty course assignment, Decision Science 15 (1984) 409– 420. [28] B. Paechter, A. Cumming, H. Luchian, M. Petriuc, Two solutions to the general timetable problem using evolutionary methods, in: The Proceedings of the IEEE Conference on Evolutionary Computing, 1994. [29] A. Schaerf, A survey of automated timetabling, Artificial Intelligence Review 13 (2) (1999) 87–127. [30] G. Schmidt, T. Strohlein, Timetable construction––An annotated bibliography, The Computer Journal 23 (4) (1979) 307–316. S. Daskalaki et al. / European Journal of Operational Research 153 (2004) 117–135 135 [31] A. Tripathy, School timetabling––A case in large binary integer linear programming, Management Science 30 (12) (1984) 1473– 1489. [32] A. Tripathy, Computerized decision aid for timetabling––A case analysis, Discrete Applied Mathematics 35 (3) (1992) 313–323. [33] D. de Werra, An introduction to timetabling, European Journal of Operational Research 19 (1985) 151–162. [34] D. de Werra, The combinatorics of timetabling, European Journal of Operational Research 96 (1997) 504–513. [35] D.J.A Welsh, M.B. Powell, An upper bound to the chromatic number of a graph and its application to timetabling problem, The Computer Journal 10 (1967) 85–86.