Computational models for timetabling problem

Nur Aidya Hanum  Aizam; Louis  Caccetta

doi:10.3934/naco.2014.4.269

Article Contents

2014, Volume 4, Issue 3: 269-285. Doi: 10.3934/naco.2014.4.269

This issue Previous Article Stochastic programming approach for energy management in electric microgrids Next Article

Computational models for timetabling problem

Nur Aidya Hanum Aizam^1, and
Louis Caccetta^2,

1.
School of Informatics and Applied Mathematics, Universiti Malaysia Terengganu
2.
Western Australian Centre of Excellence in Industrial Optimisation (WACEIO), Department of Mathematics and Statistics, Curtin University

Received: July 31, 2014

Revised: August 31, 2014

Published: August 2014

Abstract Related Papers Cited by

Abstract

The timetabling problem is to find a schedule of activities in space/time that satisfies a prescribed set of operational and resource constraints and which maximizes an objective function that reflects the value of the schedule. Constructing an effective timetable is always a challenging task for any scheduler. Most literature research focuses on specific applications and the resulting models are not easily applied to problems other than those for which they were designed for. In this paper, we construct a general model for university course timetabling. Our model incorporates a total of 17 different types of requirements identified in the literature as well as three new constraint types that we think should be part of the restrictions in a general university based timetabling model. An integer programming (IP) model is presented which incorporates restrictions that need to be satisfied and requests that are included in the objective function. We implement and test our models using the AIMMS mathematical software package. Computational results on a number of case studies are favorable and demonstrate the value of our approach.

Keywords:

Mathematics Subject Classification: Primary: 90C90, 90C10; Secondary: 90B35.

Citation:

Related Papers

Cited by

References

[1]	International timetabling competition,, 2007, (2009).
[2]	N. A. Aizam and C. Liong, Mathematical modelling of university timetabling: A mathematical programming approach, International Journal of Applied Mathematics and Statistics, 37 (2013), 110-122.
[3]	R. Alvarez-Valdes, E. Crespo and J. M. Tamarit, Design and implementation of a course scheduling system using tabu search, European J. Oper. Res., 137 (2002), 512-523.
[4]	P. Avella and I. Vasil'Ev, A computational study of a cutting plane algorithm for university course timetabling, J. Sched., 8 (2005), 497-514.doi: 10.1007/s10951-005-4780-1.
[5]	V. Bardadym, Computer-aided school and university timetabling: The new wave, in Practice and Theory of Automated Timetabling (eds. E. Burke and P. Ross), Lecture Notes in Comput. Sci., 1153 (1996), 22-45.
[6]	O. S. Benli and A. Botsali, An optimization-based decision support system for a university timetabling problem: An integrated constraint and binary integer programming approach, Computers and Industrial Engineering, 1-29.
[7]	E. Burke, K. Jackson, J. H. Kingston and R. Weare, Automated university timetabling: The state of the art, The Computer Journal, 40 (1997), 565-571.
[8]	E. K. Burke, J. Mareček, A. J. Parkes and H. Rudová, Penalising patterns in timetables: Novel integer programming formulations, in Operations Research Proceedings 2007 (eds. J. Kalcsics and S. Nickel), Springer, 2007 (2008), 409-414.
[9]	E. K. Burke and S. Petrovic, Recent research directions in automated timetabling, European J. Oper. Res., 140 (2002), 266-280.
[10]	D. Costa, A tabu search algorithm for computing an operational timetable, European J. Oper. Res., 76 (1994), 98-110.
[11]	S. Daskalaki and T. Birbas, Efficient solutions for a university timetabling problem through integer programming, European J. Oper. Res., 160 (2005), 106-120.
[12]	S. Daskalaki, T. Birbas and E. Housos, An integer programming formulation for a case study in university timetabling, European J. Oper. Res., 153 (2004), 117-135.doi: 10.1016/S0377-2217(03)00103-6.
[13]	L. Di Gaspero, B. McCollum and A. Schaerf, The second international timetabling competition (ITC-2007): Curriculum-based course timetabling (track 3), in Proceedings of the 14th RCRA workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion, Rome, Italy, 2007.
[14]	P. Kostuch, The university course timetabling problem with a three-phase approach, in Practice and Theory of Automated Timetabling V (eds. E. Burke and M. Trick), Lecture Notes in Comput. Sci., 3616 (2005), 109-125.
[15]	N. L. Lawrie, An integer linear programming model of a school timetabling problem, The Computer Journal, 12 (1969), 307-316.
[16]	B. McCollum, A perspective on bridging the gap between theory and practice in university timetabling, in Practice and Theory of Automated Timetabling VI (eds. E. Burke and H. Rudová), Lecture Notes in Comput. Sci., 3867 (2007), 3-23.
[17]	T. A. Redl, University timetabling via graph coloring: An alternative approach, Congr. Numer., 187 (2007), 174.
[18]	A. Schaerf, A survey of automated timetabling, Artificial Intelligence Review, 13 (1999), 87-127.
[19]	K. Schimmelpfeng and S. Helber, Application of a real-world university-course timetabling model solved by integer programming, OR Spectrum, 29 (2007), 783-803.
[20]	G. Schmidt and T. Ströhlein, Timetable construction-an annotated bibliography, The Computer Journal, 23 (1980), 307-316.doi: 10.1093/comjnl/23.4.307.
[21]	C. Valouxis and E. Housos, Constraint programming approach for school timetabling, Comput. Oper. Res., 30 (2003), 1555-1572.
[22]	A. Wren, Scheduling, timetabling and rostering - a special relationship, in Practice and Theory of Automated Timetabling (eds. E. Burke and P. Ross), Lecture Notes in Comput. Sci., 1153 (1996), 46-75.