# American Institute of Mathematical Sciences

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

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-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. [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.
 [1] Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102 [2] 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 and Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431 [3] Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557 [4] Ruiheng Cai, Feng-kuang Chiang. A laser-cutting-centered STEM course for improving engineering problem-solving skills of high school students in China. STEM Education, 2021, 1 (3) : 199-224. doi: 10.3934/steme.2021015 [5] Ankhbayar Chuluunbaatar, Enkhbat Rentsen. Solving a fractional programming problem in a commercial bank. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021153 [6] Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353 [7] Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial and Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529 [8] Ye Tian, Shucherng Fang, Zhibin Deng, Qingwei Jin. Cardinality constrained portfolio selection problem: A completely positive programming approach. Journal of Industrial and Management Optimization, 2016, 12 (3) : 1041-1056. doi: 10.3934/jimo.2016.12.1041 [9] Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial and Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058 [10] Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058 [11] Rhoda P. Agdeppa, Nobuo Yamashita, Masao Fukushima. An implicit programming approach for the road pricing problem with nonadditive route costs. Journal of Industrial and Management Optimization, 2008, 4 (1) : 183-197. doi: 10.3934/jimo.2008.4.183 [12] Bhawna Kohli. Sufficient optimality conditions using convexifactors for optimistic bilevel programming problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3209-3221. doi: 10.3934/jimo.2020114 [13] Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027 [14] Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213 [15] Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial and Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67 [16] Mohamed A. Tawhid, Ahmed F. Ali. A simplex grey wolf optimizer for solving integer programming and minimax problems. Numerical Algebra, Control and Optimization, 2017, 7 (3) : 301-323. doi: 10.3934/naco.2017020 [17] R. Enkhbat, T. V. Gruzdeva, M. V. Barkova. D.C. programming approach for solving an applied ore-processing problem. Journal of Industrial and Management Optimization, 2018, 14 (2) : 613-623. doi: 10.3934/jimo.2017063 [18] Lidan Li, Hongwei Zhang, Liwei Zhang. Inverse quadratic programming problem with $l_1$ norm measure. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2425-2437. doi: 10.3934/jimo.2019061 [19] 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 and Continuous Dynamical Systems - B, 2019, 24 (4) : 1743-1767. doi: 10.3934/dcdsb.2018235 [20] Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial and Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117

Impact Factor: