An overview of curriculum-based course timetabling. (English) Zbl 1319.90026
Summary: In 2007, the Second International Timetabling Competition (ITC-2007) has been organized and a formal definition of the Curriculum-Based Course Timetabling (CB-CTT) problem has been given, by taking into account several real-world constraints and objectives while keeping the problem general. CB-CTT consists of finding the best weekly assignment of university course lectures to rooms and time periods. A feasible schedule must satisfy a set of hard constraints and must also take into account a set of soft constraints, whose violation produces penalty terms to be minimized in the objective function. From ITC-2007, many researchers have developed advanced models and methods to solve CB-CTT. This survey is devoted to review the main works on the topic, with focus on mathematical models, lower bounds, and exact and heuristic algorithms. Besides giving an overview of these approaches, we highlight interesting extensions that could make the study of CB-CTT even more challenging and closer to reality.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C10 | Integer programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90-02 | Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming |
Keywords:
university timetabling; curriculum-based course timetabling; survey; models; exact algorithms; heuristic algorithmsReferences:
| [1] | Abdullah S, Turabieh H (2012) On the use of multi neighbourhood structures within a tabu-based memetic approach to university timetabling problems. Inf Sci 191:146-168 · doi:10.1016/j.ins.2011.12.018 |
| [2] | Abdullah, S.; Burke, EK; McCollum, B.; Doerner, K. (ed.); Gendreau, M. (ed.); Greistorfer, P. (ed.); Gutjahr, W. (ed.); Hartl, R. (ed.); Reimann, M. (ed.), Using a randomised iterative improvement algorithm with composite neighbourhood structures for the university course timetabling problem, No. 39, 153-169 (2007), US · Zbl 1172.90393 |
| [3] | Al-Yakoob S, Sherali H (2007) A mixed-integer programming approach to a class timetabling problem: a case study with gender policies and traffic considerations. Eur J Oper Res 180(3):1028-1044 · Zbl 1121.90049 · doi:10.1016/j.ejor.2006.04.035 |
| [4] | Asín Achá R, Nieuwenhuis R (2014) Curriculum-based course timetabling with SAT and MaxSAT. Ann Oper Res 218(1):71-91 · Zbl 1301.90023 · doi:10.1007/s10479-012-1081-x |
| [5] | Atsuta M, Nonobe K, Ibaraki T (2008) Itc 2007 track 2, an approach using general csp solver. Technical report, www.cs.qub.ac.uk/itc2007 |
| [6] | Avella P, Vasiĺev I (2005) A computational study of a cutting plane algorithm for university course timetabling. J Sched 8(6):497-514 · Zbl 1123.90016 · doi:10.1007/s10951-005-4780-1 |
| [7] | Babaei H, Karimpour J, Hadidi A (2014) A survey of approaches for university course timetabling problem. Comput Ind Eng. doi:10.1016/j.cie.2014.11.010 · Zbl 1301.90023 |
| [8] | Banbara M, Soh T, Tamura N, Inoue K, Schaub T (2013) Answer set programming as a modeling language for course timetabling. Theory Pract Log Program 13(4-5):783-798 · Zbl 1286.68040 · doi:10.1017/S1471068413000495 |
| [9] | Beliën J, Mercy A (2013) Building university course timetables with minimized resulting student flows. In: Proceedings of the 6th multidisciplinary international conference on scheduling: theory and applications (MISTA 2013), Belgium, pp 737-740 |
| [10] | Bellio R, Di Gaspero L, Schaerf A (2012) Design and statistical analysis of a hybrid local search algorithm for course timetabling. J Sched 15(1):49-61 · doi:10.1007/s10951-011-0224-2 |
| [11] | Bellio R, Ceschia S, Di Gaspero L, Schaerf A, Urli T (2013) A simulated annealing approach to the curriculum-based course timetabling problem. In: Proceedings of the 6th multidisciplinary international conference on scheduling: theory and applications (MISTA 2013), Belgium, pp 314-317 · Zbl 1349.90316 |
| [12] | Bellio R, Ceschia S, Di Gaspero L, Schaerf A, Urli T (2014) Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem. arXiv:1409.7186 · Zbl 1349.90316 |
| [13] | Bonutti A, De Cesco F, Di Gaspero L, Schaerf A (2012) Benchmarking curriculum-based course timetabling: formulations, data formats, instances, validation, visualization, and results. Ann Oper Res 194(1):59-70 · Zbl 1251.90117 · doi:10.1007/s10479-010-0707-0 |
| [14] | Bożejko W, Gniewkowski Ł, Wodecki M (2014) Solving timetabling problems on gpu. In: Artificial intelligence and soft computing, Springer, pp 445-455 · Zbl 1243.90007 |
| [15] | Burke E, Petrovic S (2002) Recent research directions in automated timetabling. Eur J Oper Res 140(2):266-280 · Zbl 1001.90030 · doi:10.1016/S0377-2217(02)00069-3 |
| [16] | Burke E, Jackson K, Kingston JH, Weare R (1997) Automated university timetabling: the state of the art. Comput J 40(9):565-571 · doi:10.1093/comjnl/40.9.565 |
| [17] | Burke E, Mareček J, Parkes A, Rudová H (2008) Penalising patterns in timetables: novel integer programming formulations. Oper Res Proc 2007:409-414 · Zbl 1209.90160 |
| [18] | Burke E, Mareček J, Parkes A, Rudová H (2010a) Decomposition, reformulation, and diving in university course timetabling. Comput Oper Res 37(3):582-597 · Zbl 1173.90451 · doi:10.1016/j.cor.2009.02.023 |
| [19] | Burke E, Mareček J, Parkes A, Rudová H (2010b) A supernodal formulation of vertex colouring with applications in course timetabling. Ann Oper Res 179(1):105-130 · Zbl 1207.05046 · doi:10.1007/s10479-010-0716-z |
| [20] | Burke E, Mareček J, Parkes A, Rudová H (2012) A branch-and-cut procedure for the Udine course timetabling problem. Ann Oper Res 194(1):71-87 · Zbl 1251.90276 · doi:10.1007/s10479-010-0828-5 |
| [21] | Cacchiani V, Caprara A, Roberti R, Toth P (2013) A new lower bound for curriculum-based course timetabling. Comput Oper Res 40(10):2466-2477 · Zbl 1348.90245 · doi:10.1016/j.cor.2013.02.010 |
| [22] | Carter, M.; Burke, E. (ed.); Erben, W. (ed.), A comprehensive course timetabling and student scheduling system at the university of waterloo, No. 2079, 64-82 (2001), Berlin · Zbl 0982.68955 · doi:10.1007/3-540-44629-X_5 |
| [23] | Carter, M.; Gass, S. (ed.); Fu, M. (ed.), Timetabling, 1552-1556 (2013), US · doi:10.1007/978-1-4419-1153-7_1047 |
| [24] | Chiarandini M, Birattari M, Socha K, Rossi-Doria O (2006) An effective hybrid algorithm for university course timetabling. J Sched 9(5):403-432 · Zbl 1154.90428 · doi:10.1007/s10951-006-8495-8 |
| [25] | Clark M, Henz M, Love B (2009) Quikfix a repair-based timetable solver. In: Proceedings of the 7th international conference on the practice and theory of automated timetabling (PATAT-2008) |
| [26] | Daskalaki S, Birbas T (2005) Efficient solutions for a university timetabling problem through integer programming. Eur J Oper Res 160(1):106-120 · Zbl 1067.90135 · doi:10.1016/j.ejor.2003.06.023 |
| [27] | Daskalaki S, Birbas T, Housos E (2004) An integer programming formulation for a case study in university timetabling. Eur J Oper Res 153(1):117-135 · Zbl 1053.90078 · doi:10.1016/S0377-2217(03)00103-6 |
| [28] | Gaspero, L.; Schaerf, A.; Burke, E. (ed.); Causmaecker, P. (ed.), Multi-neighbourhood local search with application to course timetabling, No. 2740, 262-275 (2003), Berlin · doi:10.1007/978-3-540-45157-0_17 |
| [29] | Di Gaspero L, Schaerf A (2006) Neighborhood portfolio approach for local search applied to timetabling problems. J Math Model Algorithms 5(1):65-89 · Zbl 1103.90102 · doi:10.1007/s10852-005-9032-z |
| [30] | Di Gaspero L, McCollum B, Schaerf A (2007) The second international timetabling competition (itc-2007): curriculum-based course timetabling (track 3). Technical report, School of Electronics, Electrical Engineering and Computer Science, Queens University, Belfast (UK), ITC-2007. site: http://www.cs.qub.ac.uk/itc2007/ · Zbl 1103.90102 |
| [31] | Geiger MJ (2009) Multi-criteria curriculum-based course timetablinga comparison of a weighted sum and a reference point based approach. In: Ehrgott M, Fonseca CM, Gandibleux X, Hao JK, Sevaux M (eds) In: Proceedings of the 5th international conference on evolutionary multi-criterion optimization, EMO 2009, Springer, Lecture notes in computer science, vol 5467, pp 290-304 · Zbl 1160.68302 |
| [32] | Geiger MJ (2012) Applying the threshold accepting metaheuristic to curriculum based course timetabling. Ann Oper Res 194(1):189-202 · Zbl 1251.90145 · doi:10.1007/s10479-010-0703-4 |
| [33] | Hansen P, Hertz A, Kuplinsky J (1993) Bounded vertex colorings of graphs. Discret Math 111(13):305-312 · Zbl 0782.05032 · doi:10.1016/0012-365X(93)90165-P |
| [34] | Hao JK, Benlic U (2011) Lower bounds for the ITC-2007 curriculum-based course timetabling problem. Eur J Oper Res 212(3):464-472 · doi:10.1016/j.ejor.2011.02.019 |
| [35] | Jain R, Chiu DM, Hawe WR (1984) A quantitative measure of fairness and discrimination for resource allocation in shared computer system. Technical report DEC-TR-301, Eastern Research Laboratory, Digital Equipment Corporation Hudson, MA |
| [36] | Kiefer A, Hartl R, Schnell A (2014) Adaptive large neighborhood search for the curriculum-based course timetabling problem. Technical report UNIVIE-PLIS-2014-001, University of Vienna · Zbl 1368.90072 |
| [37] | Kingston, JH; Uyar, AS (ed.); Ozcan, E. (ed.); Urquhart, N. (ed.), Educational timetabling, No. 505, 91-108 (2013), Berlin · doi:10.1007/978-3-642-39304-4_4 |
| [38] | Kolonias V, Goulas G, Gogos C, Alefragis P, Housos E (2014) Solving the examination timetabling problem in gpus. Algorithms 7(3):295-327 · Zbl 1461.90179 · doi:10.3390/a7030295 |
| [39] | Kostuch, P.; Burke, E. (ed.); Trick, M. (ed.), The university course timetabling problem with a three-phase approach, No. 3616, 109-125 (2005), Berlin · doi:10.1007/11593577_7 |
| [40] | Kristiansen S, Stidsen T (2013) A comprehensive study of educational timetabling—a survey. Technical report, DTU Management Engineering · Zbl 1209.90160 |
| [41] | Lach, G.; Lübbecke, M.; McGeoch, C. (ed.), Optimal university course timetables and the partial transversal polytope, No. 5038, 235-248 (2008), Berlin · doi:10.1007/978-3-540-68552-4_18 |
| [42] | Lach G, Lübbecke M (2012) Curriculum based course timetabling: new solutions to Udine benchmark instances. Ann Oper Res 194(1):255-272 · Zbl 1251.90160 · doi:10.1007/s10479-010-0700-7 |
| [43] | Landa-Silva D, Obit JH (2008) Great deluge with non-linear decay rate for solving course timetabling problems. In: Intelligent systems, 2008. IS’08. In: 4th international IEEE conference, IEEE, vol 1, pp 8-11 · Zbl 1251.90117 |
| [44] | Landa-Silva J, Burke E, Petrovic S (2004) An introduction to multiobjective metaheuristics for scheduling and timetabling. In: Metaheuristics for multiobjective optimisation. Springer, pp 91-129 · Zbl 1139.90420 |
| [45] | Lewis R (2008) A survey of metaheuristic-based techniques for university timetabling problems. OR Spectr 30(1):167-190 · Zbl 1133.90341 · doi:10.1007/s00291-007-0097-0 |
| [46] | Lewis R, Paechter B, Rossi-Doria O (2007) Metaheuristics for university course timetabling. Stud Comput Intell 49(49):237-272 · Zbl 1200.90078 · doi:10.1007/978-3-540-48584-1_9 |
| [47] | Lopes, L.; Smith-Miles, K.; Blum, C. (ed.); Battiti, R. (ed.), Pitfalls in instance generation for udine timetabling, No. 6073, 299-302 (2010), Berlin · doi:10.1007/978-3-642-13800-3_31 |
| [48] | Lopes L, Smith-Miles K (2013) Generating applicable synthetic instances for branch problems. Oper Res 61(3):563-577 · Zbl 1273.90243 · doi:10.1287/opre.2013.1169 |
| [49] | Lü, Z.; Hao, JK; Cotta, C. (ed.); Cowling, P. (ed.), A critical element-guided perturbation strategy for iterated local search, No. 5482, 1-12 (2009), Berlin · doi:10.1007/978-3-642-01009-5_1 |
| [50] | Lü Z, Hao JK (2010) Adaptive tabu search for course timetabling. Eur J Oper Res 200(1):235-244 · Zbl 1190.90166 · doi:10.1016/j.ejor.2008.12.007 |
| [51] | Lü Z, Hao JK, Glover F (2011) Neighborhood analysis: a case study on curriculum-based course timetabling. J Heuristics 17(2):97-118 · doi:10.1007/s10732-010-9128-0 |
| [52] | McCollum, B.; Burke, E. (ed.); Rudov, H. (ed.), A perspective on bridging the gap between theory and practice in university timetabling, No. 3867, 3-23 (2007), Berlin · doi:10.1007/978-3-540-77345-0_1 |
| [53] | McCollum B, Ireland N (2006) University timetabling: bridging the gap between research and practice. In: Proceedings of the 5th international conference on the practice and theory of automated timetabling, pp 15-35 |
| [54] | McCollum B, Schaerf A, Paechter B, McMullan P, Lewis R, Parkes A, Di Gaspero L, Qu R, Burke E (2010) Setting the research agenda in automated timetabling: the second international timetabling competition. INFORMS J Comput 22(1):120-130 · Zbl 1243.90007 · doi:10.1287/ijoc.1090.0320 |
| [55] | Miranda J (2010) eClasSkeduler: a course scheduling system for the executive education unit at the Universidad de Chile. Interfaces 40(3):196-207 · doi:10.1287/inte.1090.0485 |
| [56] | MirHassani S (2006) A computational approach to enhancing course timetabling with integer programming. Appl Math Comput 175(1):814-822 · Zbl 1092.90025 · doi:10.1016/j.amc.2005.07.039 |
| [57] | MirHassani S, Habibi F (2013) Solution approaches to the course timetabling problem. Artif Intel Rev 39(2):133-149 · doi:10.1007/s10462-011-9262-6 |
| [58] | Mühlenthaler M, Wanka R (2014) Fairness in academic course timetabling. Ann Oper Res 1-18 · Zbl 1336.90078 |
| [59] | Müller T (2009) Itc 2007 solver description: a hybrid approach. Ann Oper Res 172(1):429-446 · Zbl 1184.90143 · doi:10.1007/s10479-009-0644-y |
| [60] | Müller T, Murray K (2010) Comprehensive approach to student sectioning. Ann Oper Res 181(1):249-269 · Zbl 1184.90143 |
| [61] | Petrovic S, Burke E (2004) University timetabling. In: Leung JYT (ed) Handbook of scheduling: algorithms, models, and performance analysis, CRC Press, Boca Raton · Zbl 1103.90002 |
| [62] | Phillips AE, Waterer H, Ehrgott M, Ryan DM (2015) Integer programming methods for large-scale practical classroom assignment problems. Comput Oper Res 53:42-53 · Zbl 1348.90300 · doi:10.1016/j.cor.2014.07.012 |
| [63] | Pillay N (2014) A review of hyper-heuristics for educational timetabling. Ann Oper Res 1-36. doi:10.1007/s10479-014-1688-1 · Zbl 1336.90080 |
| [64] | Qualizza, A.; Serafini, P.; Burke, E. (ed.); Trick, M. (ed.), A column generation scheme for faculty timetabling, No. 3616, 161-173 (2005), Berlin · doi:10.1007/11593577_10 |
| [65] | Schaerf A (1999) A survey of automated timetabling. Artif Intel Rev 13(2):87-127 · doi:10.1023/A:1006576209967 |
| [66] | Schimmelpfeng A, Helber S (2007) Application of a real-world university-course timetabling model solved by integer programming. OR Spectr 29(4):783-803 · Zbl 1168.90670 · doi:10.1007/s00291-006-0074-z |
| [67] | Shaker, K.; Abdullah, S.; Alqudsi, A.; Jalab, H.; Lingras, P. (ed.); Wolski, M. (ed.); Cornelis, C. (ed.); Mitra, S. (ed.); Wasilewski, P. (ed.), Hybridizing meta-heuristics approaches for solving university course timetabling problems, No. 8171, 374-384 (2013), Berlin · doi:10.1007/978-3-642-41299-8_36 |
| [68] | Tarawneh HY, Ayob M, Ahmad Z (2013) A hybrid simulated annealing with solutions memory for curriculum-based course timetabling problem. J Appl Sci 13:262-269 · doi:10.3923/jas.2013.262.269 |
| [69] | Van Den Broek J, Hurkens C, Woeginger G (2009) Timetabling problems at the TU Eindhoven. Eur J Oper Res 196(3):877-885 · Zbl 1176.90421 · doi:10.1016/j.ejor.2008.04.038 |
| [70] | Wren, A.; Burke, E. (ed.); Ross, P. (ed.), Scheduling, timetabling and rostering a special relationship?, No. 1153, 46-75 (1996), Berlin · doi:10.1007/3-540-61794-9_51 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
