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).

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

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

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

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

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

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

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

[9]

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

[10]

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

[11]

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

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

[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).

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

[15]

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

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

[17]

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

[18]

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

[19]

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

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

[21]

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

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

show all references

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.

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

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

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

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

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

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

[9]

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

[10]

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

[11]

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

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

[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).

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

[15]

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

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

[17]

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

[18]

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

[19]

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

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

[21]

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

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

[1]

Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial & Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431

[2]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557

[3]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

[4]

Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial & Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529

[5]

Ye Tian, Shucherng Fang, Zhibin Deng, Qingwei Jin. Cardinality constrained portfolio selection problem: A completely positive programming approach. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1041-1056. doi: 10.3934/jimo.2016.12.1041

[6]

Rhoda P. Agdeppa, Nobuo Yamashita, Masao Fukushima. An implicit programming approach for the road pricing problem with nonadditive route costs. Journal of Industrial & Management Optimization, 2008, 4 (1) : 183-197. doi: 10.3934/jimo.2008.4.183

[7]

Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial & Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058

[8]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027

[9]

Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213

[10]

Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial & Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67

[11]

Mohamed A. Tawhid, Ahmed F. Ali. A simplex grey wolf optimizer for solving integer programming and minimax problems. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 301-323. doi: 10.3934/naco.2017020

[12]

R. Enkhbat, T. V. Gruzdeva, M. V. Barkova. D.C. programming approach for solving an applied ore-processing problem. Journal of Industrial & Management Optimization, 2018, 14 (2) : 613-623. doi: 10.3934/jimo.2017063

[13]

Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117

[14]

Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111

[15]

Zutong Wang, Jiansheng Guo, Mingfa Zheng, Youshe Yang. A new approach for uncertain multiobjective programming problem based on $\mathcal{P}_{E}$ principle. Journal of Industrial & Management Optimization, 2015, 11 (1) : 13-26. doi: 10.3934/jimo.2015.11.13

[16]

Vladimir Gaitsgory, Alex Parkinson, Ilya Shvartsman. Linear programming based optimality conditions and approximate solution of a deterministic infinite horizon discounted optimal control problem in discrete time. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1743-1767. doi: 10.3934/dcdsb.2018235

[17]

Lidan Li, Hongwei Zhang, Liwei Zhang. Inverse quadratic programming problem with $ l_1 $ norm measure. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2019061

[18]

René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363

[19]

Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115

[20]

Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]