×

An integer programming approach to curriculum-based examination timetabling. (English) Zbl 1381.90036

Summary: The examination timetabling problem (ETTP) consists in the assignment of specific dates to the exams of a set of courses assuming that the course enrollments are known. This problem is also known as post-enrollment ETTP. In this paper, we describe and solve a variant of the ETTP which has two particularities: (1) it does not assume the course enrollments as known and uses the curriculum of the degree program to evaluate potential conflicts in the exam schedules, and (2) it considers the exams and classrooms of multiple degree programs simultaneously. We refer to this variant of the ETTP as curriculum-based examination timetabling problem (CB-ETTP), a problem faced by many universities worldwide, being the Universidad Diego Portales (UDP) in Santiago of Chile one of them. To the best of our knowledge, this problem has not been described as such in the ETTP literature. We propose an approach to solve the CB-ETTP consisting of four sequential stages. The first stage groups courses into clusters and generates classroom configurations called room patterns. The second stage assigns time slots and room patterns to course clusters. Then, the third stage assigns time slots and room patterns to individual courses. Finally, the fourth stage generates a definitive exam schedule assigning specific rooms to each course exam. We evaluate the performance of the proposed approach by applying it to real-world instances generated based on data provided by the Faculty of Engineering at the UDP. The results show a reduction in the number of conflicts and rescheduling with respect to the current exam scheduling practice used by this university.

MSC:

90B35 Deterministic scheduling theory in operations research
90C10 Integer programming

Software:

MCS; FIRBS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdullah, S., Ahmadi, S., Burke, E., & Dror, M. (2007a). Investigating Ahuja-Orlin’s large neighbourhood search approach for examination timetabling. OR Spectrum, 29, 351-372. · Zbl 1170.90383 · doi:10.1007/s00291-006-0034-7
[2] Abdullah, S., Ahmadi, S., Burke, E., Dror, M., & McCollum, B. (2007b). A tabu based large neighbourhood search methodolgy for the capacited examination timetabling problem. Journal of Operational Research, 58, 1494-1502. · Zbl 1177.90139 · doi:10.1057/palgrave.jors.2602258
[3] Abdul-Rahman, S., Burke, E., Bargiela, A., McCollum, B., & Özcan, E. (2014). A constructive approach to examination timetabling based on adaptive decomposition and ordering. Annals of Operations Research, 218, 3-21. · Zbl 1301.90022 · doi:10.1007/s10479-011-0999-8
[4] Aboudi, R., & Barcia, P. (1998). Determining cutting stock patterns when defects are present. Annals of Operations Research, 82, 343-354. · Zbl 0910.90232 · doi:10.1023/A:1018975006313
[5] Al-Yakoob, A., Sherali, H., & Al-Jazzaf, M. (2010). A mixed-integer mathematical modeling approach to exam timetabling. Computer Management Science, 7, 19-46. · Zbl 1178.90141 · doi:10.1007/s10287-007-0066-8
[6] Asmuni, H., Burke, E., Garibaldi, J., McCollum, B., & Parkes, A. (2009). An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables. Computer and Operations Research, 36, 981-1001. · Zbl 1162.90440 · doi:10.1016/j.cor.2007.12.007
[7] Ayob, M., Malik, A., Abdullah, S., Razak Hamdam, A., Kendall, G., & Qu, R. (2007). Solving a practical examination timetabling problem: A case study. Lecture Notes in Computer Science, 4707, 611-624. · doi:10.1007/978-3-540-74484-9_53
[8] Azimi, Z. N. (2005). Hybrid heuristics for examination timetabling problem. Applied Mathematics and Computation, 163, 705-733. · Zbl 1116.90413 · doi:10.1016/j.amc.2003.10.061
[9] Bellio, R., Di Gaspero, L., & Schaerf, A. (2012). Design and statistical analysis of a hybrid local search algorithm for course timetabling. Journal of Scheduling, 15, 49-61. · doi:10.1007/s10951-011-0224-2
[10] Beyrouthy, C., Burke, E., McCollum, B., McMullan, P., & Parkes, A. (2010). University space planning and space-type profiles. Journal of Scheduling, 13(4), 363-374. · Zbl 1231.90255 · doi:10.1007/s10951-010-0178-9
[11] Birbas, T., Daskalaki, S., & Housos, E. (2009). School Timetabling for quality student and teacher schedules. Journal of Scheduling, 12, 177-197. · Zbl 1180.90113 · doi:10.1007/s10951-008-0088-2
[12] Bonutti, A., De Cesco, F., Di Gaspero, L., & Schaerf, A. (2012). Benchmarking curriculum-based course timetabling: Formulations, data formats, instances, validation, visualization, and results. Annals of Operations Research, 194, 59-70. · Zbl 1251.90117 · doi:10.1007/s10479-010-0707-0
[13] Burke, E., Bykov, Y., Newall, J., & Petrovic, S. (2004a). A time predefined local search approach to exam timetabling problems. IIE Transactions, 36, 509-528. · doi:10.1080/07408170490438410
[14] Burke, E., Bykov, Y., & Petrovic, S. (2001). A multicriteria approach to examination timetabling. Lectures Notes in Computer Science, 2079, 118-131. · Zbl 0982.68522 · doi:10.1007/3-540-44629-X_8
[15] Burke, E., De Causmaecker, P., Vanden Berghe, G., & Van Landeghem, H. (2004b). The state of the art of nurse rostering. Journal of Scheduling, 7, 441-499. · Zbl 1154.90422 · doi:10.1023/B:JOSH.0000046076.75950.0b
[16] Burke, E., Eckersley, A., McCollum, B., Petrovic, S., & Qu, R. (2010a). Hybrid variable neighbourhood approaches to university exam timetabling. European Journal of Operational Research, 206, 46-53. · Zbl 1188.90090 · doi:10.1016/j.ejor.2010.01.044
[17] Burke, E., Kendall, G., Misir, M., & Özcan, E. (2012). Monte carlo hyper-heuristics for examination timetabling. Annals of Operations Research, 2012, 73-90. · Zbl 1251.90394 · doi:10.1007/s10479-010-0782-2
[18] Burke, E., Li, J., & Qu, R. (2009). A Pareto-based search methodology for multi-objective nurse scheduling. Annals of Operations Research,. doi:10.1007/s10479-009-0590-8. · Zbl 1251.90348 · doi:10.1007/s10479-009-0590-8
[19] Burke, E., Maracek, J., Parkes, A., & Rudová, H. (2010b). Decomposition, reformulation, and diving in university course timetabling. Computers and Operations Research, 37(3), 582-597. · Zbl 1173.90451 · doi:10.1016/j.cor.2009.02.023
[20] Burke, E., Newall, J., & Weare, R. (1996). A memetic algorithm for university Timetabling. Lecture Notes in Computer Science, 1153, 241-250. · doi:10.1007/3-540-61794-9_63
[21] Burke, E., Petrovic, S., & Qu, R. (2006). Case-based heuristic selection for timetabling problems. Journal of Scheduling, 9, 115-132. · Zbl 1154.90423 · doi:10.1007/s10951-006-6775-y
[22] Burke, E., Pham, N., Qu, R., & Yellen, J. (2012b). Linear combination of heuristics for examination timetabling. Annals of Operations Research, 194, 89-109. · Zbl 1251.90119 · doi:10.1007/s10479-011-0854-y
[23] Carter, M., Laporte, G., & Lee, S. (1996). Examination timetabling: Algorithmic strategies and applications. Journal of Operational Research Society, 47(3), 373-383. · doi:10.1057/jors.1996.37
[24] Cheong, C., Tan, K., & Veeravalli, B. (2009). A multi-objective evolutionary algorithm for examination timetabling. Journal of Scheduling, 12, 121-146. · Zbl 1179.90133 · doi:10.1007/s10951-008-0085-5
[25] Daskalaki, S., Birbas, T., & Housos, E. (2004). An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, 153, 117-135. · Zbl 1053.90078 · doi:10.1016/S0377-2217(03)00103-6
[26] De Causmaecker, P., Demeester, P., & Vanden Berghe, G. (2009). A descomposed metaheuristic approach for a real-world university timetabling problem. European Journal of Operational Research, 195, 307-318. · Zbl 1156.90372 · doi:10.1016/j.ejor.2008.01.043
[27] De Leone, R., Festa, P., & Marchitto, E. (2011). A bus driver scheduling problem: A new mathematical model and a GRASP approximate solution. Journal of Heuristics, 17, 441-466. · Zbl 1233.90152 · doi:10.1007/s10732-010-9141-3
[28] De Werra, D. (1985). An introduction to timetabling. European Journal of Operational Research, 19, 151-162. · Zbl 0553.90059 · doi:10.1016/0377-2217(85)90167-5
[29] Demeester, P., Bilgin, B., De Causmaecker, P., & Vanden Berghe, G. (2012). A hyperheuristic approach to examination timetabling problems: Benchmarks and a new roblem from practice. Journal of Scheduling, 15, 83-103. · doi:10.1007/s10951-011-0258-5
[30] Derigs, U., & Friederichs, S. (2013). Air cargo scheduling: Integrated models and solution procedures. OR Spectrum, 35(2), 325-362. · Zbl 1263.90041 · doi:10.1007/s00291-012-0299-y
[31] Dimopoulou, M., & Miliotis, P. (2001). Implementation of a university course and examination timetabling system. European Journal of Operational Research, 130, 202-213. · Zbl 0985.90046 · doi:10.1016/S0377-2217(00)00052-7
[32] Duran, G., Guajardo, M., Miranda, J., Sauré, D., Souyris, S., Weintraub, A., et al. (2007). Scheduling the Chilean soccer league by integer programming. Interfaces, 7(6), 539-552. · doi:10.1287/inte.1070.0318
[33] Eley, M. (2006). Some experiments with ant colony algorithms for the exam timetabling. Lecture Notes in Computer Science, 4150, 492-499. · doi:10.1007/11839088_50
[34] Gendreau, M., Ferland, J., Gendron, B., Hail, N., Jaumard, B., Lapierre, S., et al. (2007). Physician scheduling in emergency rooms. Lecture Notes in Computer Science, 3867, 53-66. · doi:10.1007/978-3-540-77345-0_4
[35] Gogos, G., Alefragis, P., & Housos, E. (2012). An improved multi-staged algorithmic process for the solution of the examination timetabling problem. Annals of Operations Research, 194, 203-221. · Zbl 1251.90149 · doi:10.1007/s10479-010-0712-3
[36] Goossens, D., & Spieksma, F. (2012). Soccer schedules in Europe: An overview. Journal of Scheduling, 15, 641-651. · doi:10.1007/s10951-011-0238-9
[37] Gupta, D., & Denton, B. (2008). Appointment scheduling in health care: Challenges and opportunities. IIE Transactions, 40(9), 800-819. · doi:10.1080/07408170802165880
[38] Jat, S., & Yang, S. (2011). A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling. Journal of Scheduling, 14, 617-637. · doi:10.1007/s10951-010-0202-0
[39] Joshua, J., & Tajudin, A. (2006). Visualizing the examination timetabling data using clustering method and TreeMaps. In Proceedings of the 2nd IMT-GT regional conference on mathematics, statistics and applications.
[40] Joshua, J., Tajudin, A., Bahari, B., & Leow, A. (2010). Exploration of rough sets analysis in real-world examination. Lectures Notes in Computer Science, 6729, 173-182.
[41] Kahar, M., & Kendall, G. (2010). The examination timetabling problem at Universiti Malaysia Pahang: Comparison of a constructive heuristic with an existing software solution. European Journal of Operational Research, 207, 557-565. · Zbl 1205.90186 · doi:10.1016/j.ejor.2010.04.011
[42] Lach, G., & Lübbecke, M. (2012). Curriculum based course timetabling: New solutions to Udine benchmark instances. Annals of Operations Research, 194, 255-272. · Zbl 1251.90160 · doi:10.1007/s10479-010-0700-7
[43] Le Huédé, F., Grabisch, M., Labreuche, C., & Savéant, P. (2006). MCS—A new algorithm for multicriteria optimisation in constraint programming. Annals of Operations Research, 147, 143-174. · Zbl 1188.90241 · doi:10.1007/s10479-006-0064-1
[44] Lewis, R., Paechter, B., & McCollum, B. (2007). Post enrolment based course timetabling: A description of the problem model used for track two of the second international timetabling competition. Cardiff Accounting and Finance Working Papers A2007/3, Cardiff University, Cardiff Business School, Accounting and Finance Section.
[45] Lezaun, M., Pérez, G., & Sáinz de la Maza, E. (2007). Rostering in a rail passenger carrier. Journal of Scheduling, 10, 245-254. · Zbl 1168.90456 · doi:10.1007/s10951-007-0024-x
[46] Lü, Z., & Hao, J. (2010). Adaptive tabu search for course timetabling. European Journal of Operational Research, 200, 235-244. · Zbl 1190.90166 · doi:10.1016/j.ejor.2008.12.007
[47] Lü, Z., Hao, J., & Glover, F. (2011). Neighborhood analysis: A case study on curriculum-based course timetabling. Journal of Heuristics, 17, 97-118. · doi:10.1007/s10732-010-9128-0
[48] Maenhout, B., & Vanhoucke, M. (2010). Branching strategies in a branch-and-price approach for a multiple objective nurse scheduling problem. Journal of Scheduling, 13, 77-93. · Zbl 1185.90085 · doi:10.1007/s10951-009-0108-x
[49] Mansour, N., Isahakian, V., & Ghalayini, I. (2011). Scatter search technique for exam timetabling. Applied Intelligence, 34, 299-310. · doi:10.1007/s10489-009-0196-5
[50] McCollum, B., McMullan, P., Burke, E., Parkes, A., & Qu, R. (2008). The second international timetabling competition: Examination timetabling track. N Ireland: Technical Report Queen’s Belfast University. · Zbl 1243.90007
[51] McCollum, B. (2007). A perspective on bridging the gap between research and practice in university timetabling. Lecture Notes in Computer Science, 3867, 3-23. · doi:10.1007/978-3-540-77345-0_1
[52] McCollum, B., McMullan, P., Parkes, A., Burke, E., & Qu, R. (2012). A new model for automated examination timetabling. Annals of Operations Research, 194, 291-315. · Zbl 1251.90168 · doi:10.1007/s10479-011-0997-x
[53] Medard, C., & Sawhney, N. (2007). Airline crew scheduling from planning to operations. European Journal of Operational Research, 183, 1013-1027. · Zbl 1136.90356 · doi:10.1016/j.ejor.2005.12.046
[54] Merlot, L., Boland, N., Hughes, B., & Stuckey, P. (2003). A hybrid algorithm for the examination timetabling problem. In E. K. Burke & P. De Causmaecker (Eds.) Lecture notes in computer science: Vol 2740 Practice and theory of automated timetabling IV: selected papers from the 4th international conference (pp. 207-231). Berlin: Springer. · Zbl 1173.90451
[55] Miranda, J., Rey, P., & Robles, J. (2012). UdpSkeduler: A web architecture based decision support system for course and classroom scheduling. Decision Support Systems, 52, 505-513. · doi:10.1016/j.dss.2011.10.011
[56] MirHassani, S. (2006). Improving paper spread in examination timetables using integer programming. Applied Mathematics and Computation, 179, 702-706. · Zbl 1102.65069 · doi:10.1016/j.amc.2005.11.125
[57] MirHassani, S., & Habibi, F. (2013). Solution approaches to the course timetabling problem. Artificial Intelligence Review, 39(2), 133-149. · doi:10.1007/s10462-011-9262-6
[58] Munford, C. (2010). A multiobjective framework for heavily constrained examination timetabling problems. Annals of Operations Research, 180(1), 3-31. · Zbl 1202.90141 · doi:10.1007/s10479-008-0490-3
[59] Pais, T., & Maral, P. (2012). Managing the tabu list length using a fuzzy inference system: An application to examination timetabling. Annals of Operations Research, 194, 341-363. · Zbl 1251.90175 · doi:10.1007/s10479-011-0867-6
[60] Patrick, J., Puterman, M., & Queyranne, M. (2008). Dynamic multipriority patient scheduling for a diagnostic resource. Operations Research, 56(6), 1507-1525. · Zbl 1167.90675 · doi:10.1287/opre.1080.0590
[61] Petrovic, S., Yang, Y., & Dror, M. (2007). Case-based selection of initialisation heuristics for metaheuristic examination timetabling. European Journal of Operational Research, 33, 772-785.
[62] Pillay, N., & Banzhaf, W. (2009). A study of heuristic combinations for hyper-heuristic systems for the uncapacitated examination timetabling problem. European Journal of Operational Research, 197, 482-491. · Zbl 1159.90528 · doi:10.1016/j.ejor.2008.07.023
[63] Pillay, N., & Banzhaf, W. (2010). An informed genetic algorithm for the examination timetabling problem. Applied Soft Computing, 10, 457-467. · doi:10.1016/j.asoc.2009.08.011
[64] Qu, R., Burke, E., & McCollum, B. (2009a). Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems. European Journal of Operational Research, 198, 392-404. · Zbl 1163.90775 · doi:10.1016/j.ejor.2008.10.001
[65] Qu, R., Burke, E., McCollum, B., Merlot, L., & Lee, S. (2009b). A survey of search methodologies and automated system development for examination timetabling. Journal of Scheduling, 12(1), 55-89. · Zbl 1279.90071 · doi:10.1007/s10951-008-0077-5
[66] Respicio, A., & Captivo, M. (2005). Metaheuristics: Progress as real problem solvers. Operations Research/Computer Science Interfaces Series, Springer, chap Bi-Objective Sequencing of Cutting Patterns (Vol. 32, pp. 227-241). · Zbl 1116.90413
[67] Rudová, H., Müller, T., & Murray, K. (2011). Complex university course timetabling. Journal of Scheduling, 14, 187-207. · doi:10.1007/s10951-010-0171-3
[68] Sabar, N., Ayov, M., Qu, R., & Kendall, G. (2012b). A graph coloring constructive hyper-heuristic for examination timetabling problems. Applied Intelligence, 37, 1-11. · doi:10.1007/s10489-011-0309-9
[69] Sabar, N., Kendall, Ayov G. M., & Qu, R. (2012a). A honey-bee mating optimization algorithm for educational timetabling problems. European Journal of Operational Research, 216, 533-543. · doi:10.1016/j.ejor.2011.08.006
[70] Sagir, M., & Kamisli, Z. (2010). Exam scheduling: Mathematical modeling and parameter estimation with the analytic network process approach. Mathematical and Computer Modelling, 52, 930-941. · Zbl 1202.90188 · doi:10.1016/j.mcm.2010.05.029
[71] Sarin, S., Wang, Y., & Varadarajan, A. (2010). A university timetabling problem and its solution using Benders’ partitioning—A case study. Journal of Scheduling, 13, 131-141. · Zbl 1184.90097 · doi:10.1007/s10951-009-0157-1
[72] Sauré, A., Patrick, J., Tyldesley, S., & Puterman, M. (2012). Dynamic multi-appointment patient scheduling for radiation therapy. European Journal of Operational Research, 223(2), 573-584. · Zbl 1292.90133 · doi:10.1016/j.ejor.2012.06.046
[73] Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13(2), 87-127. · doi:10.1023/A:1006576209967
[74] Schöbel, A. (2012). Line planning in public transportation: Models and methods. OR Spectrum, 34, 491-510. · Zbl 1244.90048 · doi:10.1007/s00291-011-0251-6
[75] Suliman, S. (2006). Pattern generating procedure for the cutting stock problem. International Journal of Production Economics, 74, 293-301. · doi:10.1016/S0925-5273(01)00134-7
[76] Thomas, J., & Tajudin, A. (2006). Visualizing the examination timetabling data using clustering method and TreeMaps. In Proceedings of the 2nd IMT-GT regional conference on mathematics, statistics and applications. · Zbl 0851.90069
[77] Thomas, J., Tajudin, A., & Belaton, B. (2010). Information visualizing approach on the university examination timetabling problem. Visual Information Communication, 255-264. · Zbl 1042.90568
[78] Thompson, J., & Dowsland, K. (1996). Variants of simulated annealing for the examination timetabling problem. Annals of Operations Research, 63, 105-128. · Zbl 0851.90069 · doi:10.1007/BF02601641
[79] Thompson, J., & Dowsland, K. (1998). A robust simulated annealing based examination timetabling system. Computers and Operations Research, 25, 637-648. · Zbl 1042.90568 · doi:10.1016/S0305-0548(97)00101-9
[80] Turabieh, H., & Addullah, S. (2011). An integrated hybrid approach to the examination timetabling problem. Omega, 39, 598-607. · doi:10.1016/j.omega.2010.12.005
[81] Van den Broek, J., Hurkens, C., & Woeginger, G. (2009). Timetabling problems at the TU Eindhoven. European Journal of Operational Research, 196, 877-885. · Zbl 1176.90421 · doi:10.1016/j.ejor.2008.04.038
[82] Wang, S., Bussieck, M., Guignard, M., Meeraus, A., & O’Brien, F. (2009). Term-end exam scheduling at United States military academy/west point. Journal of Scheduling, 13, 375-391. · Zbl 1231.90221 · doi:10.1007/s10951-009-0153-5
[83] Wren, A. (1996). Scheduling, timetabling and rostering—A special relationship. In E. Burke, P. Ross (Eds), Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science (Vol. 1153, pp. 46-75). · Zbl 1292.90133
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.