2014, 4(3): 269-285. doi: 10.3934/naco.2014.4.269

Computational models for timetabling problem

1. 

School of Informatics and Applied Mathematics, Universiti Malaysia Terengganu, Malaysia

2. 

Western Australian Centre of Excellence in Industrial Optimisation (WACEIO), Department of Mathematics and Statistics, Curtin University, Australia

Received  August 2014 Revised  September 2014 Published  September 2014

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.
Citation: Nur Aidya Hanum Aizam, Louis Caccetta. Computational models for timetabling problem. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 269-285. doi: 10.3934/naco.2014.4.269
References:
[1]

, International timetabling competition,, 2007, (2009).   Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[4]

P. Avella and I. Vasil'Ev, A computational study of a cutting plane algorithm for university course timetabling,, J. Sched., 8 (2005), 497.  doi: 10.1007/s10951-005-4780-1.  Google Scholar

[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), 1153 (1996), 22.   Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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), 2007 (2008), 409.   Google Scholar

[9]

E. K. Burke and S. Petrovic, Recent research directions in automated timetabling,, European J. Oper. Res., 140 (2002), 266.   Google Scholar

[10]

D. Costa, A tabu search algorithm for computing an operational timetable,, European J. Oper. Res., 76 (1994), 98.   Google Scholar

[11]

S. Daskalaki and T. Birbas, Efficient solutions for a university timetabling problem through integer programming,, European J. Oper. Res., 160 (2005), 106.   Google Scholar

[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.  doi: 10.1016/S0377-2217(03)00103-6.  Google Scholar

[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, (2007).   Google Scholar

[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), 3616 (2005), 109.   Google Scholar

[15]

N. L. Lawrie, An integer linear programming model of a school timetabling problem,, The Computer Journal, 12 (1969), 307.   Google Scholar

[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á), 3867 (2007), 3.   Google Scholar

[17]

T. A. Redl, University timetabling via graph coloring: An alternative approach,, Congr. Numer., 187 (2007).   Google Scholar

[18]

A. Schaerf, A survey of automated timetabling,, Artificial Intelligence Review, 13 (1999), 87.   Google Scholar

[19]

K. Schimmelpfeng and S. Helber, Application of a real-world university-course timetabling model solved by integer programming,, OR Spectrum, 29 (2007), 783.   Google Scholar

[20]

G. Schmidt and T. Ströhlein, Timetable construction-an annotated bibliography,, The Computer Journal, 23 (1980), 307.  doi: 10.1093/comjnl/23.4.307.  Google Scholar

[21]

C. Valouxis and E. Housos, Constraint programming approach for school timetabling,, Comput. Oper. Res., 30 (2003), 1555.   Google Scholar

[22]

A. Wren, Scheduling, timetabling and rostering - a special relationship,, in Practice and Theory of Automated Timetabling (eds. E. Burke and P. Ross), 1153 (1996), 46.   Google Scholar

show all references

References:
[1]

, International timetabling competition,, 2007, (2009).   Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[4]

P. Avella and I. Vasil'Ev, A computational study of a cutting plane algorithm for university course timetabling,, J. Sched., 8 (2005), 497.  doi: 10.1007/s10951-005-4780-1.  Google Scholar

[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), 1153 (1996), 22.   Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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), 2007 (2008), 409.   Google Scholar

[9]

E. K. Burke and S. Petrovic, Recent research directions in automated timetabling,, European J. Oper. Res., 140 (2002), 266.   Google Scholar

[10]

D. Costa, A tabu search algorithm for computing an operational timetable,, European J. Oper. Res., 76 (1994), 98.   Google Scholar

[11]

S. Daskalaki and T. Birbas, Efficient solutions for a university timetabling problem through integer programming,, European J. Oper. Res., 160 (2005), 106.   Google Scholar

[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.  doi: 10.1016/S0377-2217(03)00103-6.  Google Scholar

[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, (2007).   Google Scholar

[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), 3616 (2005), 109.   Google Scholar

[15]

N. L. Lawrie, An integer linear programming model of a school timetabling problem,, The Computer Journal, 12 (1969), 307.   Google Scholar

[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á), 3867 (2007), 3.   Google Scholar

[17]

T. A. Redl, University timetabling via graph coloring: An alternative approach,, Congr. Numer., 187 (2007).   Google Scholar

[18]

A. Schaerf, A survey of automated timetabling,, Artificial Intelligence Review, 13 (1999), 87.   Google Scholar

[19]

K. Schimmelpfeng and S. Helber, Application of a real-world university-course timetabling model solved by integer programming,, OR Spectrum, 29 (2007), 783.   Google Scholar

[20]

G. Schmidt and T. Ströhlein, Timetable construction-an annotated bibliography,, The Computer Journal, 23 (1980), 307.  doi: 10.1093/comjnl/23.4.307.  Google Scholar

[21]

C. Valouxis and E. Housos, Constraint programming approach for school timetabling,, Comput. Oper. Res., 30 (2003), 1555.   Google Scholar

[22]

A. Wren, Scheduling, timetabling and rostering - a special relationship,, in Practice and Theory of Automated Timetabling (eds. E. Burke and P. Ross), 1153 (1996), 46.   Google Scholar

[1]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251

[2]

Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253

[3]

Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384

[4]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020453

[5]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[6]

Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075

[7]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[8]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

[9]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351

[10]

Zhilei Liang, Jiangyu Shuai. Existence of strong solution for the Cauchy problem of fully compressible Navier-Stokes equations in two dimensions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020348

[11]

Mehdi Badsi. Collisional sheath solutions of a bi-species Vlasov-Poisson-Boltzmann boundary value problem. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020052

[12]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

[13]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

 Impact Factor: 

Metrics

  • PDF downloads (89)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]