A constructive approach to examination timetabling based on adaptive decomposition and ordering. (English) Zbl 1301.90022
Summary: In this study, we investigate an adaptive decomposition and ordering strategy that automatically divides examinations into difficult and easy sets for constructing an examination timetable. The examinations in the difficult set are considered to be hard to place and hence are listed before the ones in the easy set in the construction process. Moreover, the examinations within each set are ordered using different strategies based on graph colouring heuristics. Initially, the examinations are placed into the easy set. During the construction process, examinations that cannot be scheduled are identified as the ones causing infeasibility and are moved forward in the difficult set to ensure earlier assignment in subsequent attempts. On the other hand, the examinations that can be scheduled remain in the easy set. Within the easy set, a new subset called the boundary set is introduced to accommodate shuffling strategies to change the given ordering of examinations. The proposed approach, which incorporates different ordering and shuffling strategies, is explored on the Carter benchmark problems. The empirical results show that the performance of our algorithm is broadly comparable to existing constructive approaches.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Abdul Rahman, S.; Bargiela, A.; Burke, E. K.; McCollum, B.; Özcan, E., Construction of examination timetables based on ordering heuristics, 727-732 (2009) |
| [2] | Abdul Rahman, S.; Bargiela, A.; Burke, E. K.; McCollum, B.; Özcan, E., A constructive approach for examination timetabling based on adaptive decomposition and ordering, 353-372 (2010) |
| [3] | Abdullah, S., Ahmadi, S., Burke, E. K., & Dror, M. (2007). Investigating Ahuja-Orlin’s large neighbourhood search approach for examination timetabling. OR-Spektrum, 29(2), 351-372. · Zbl 1170.90383 · doi:10.1007/s00291-006-0034-7 |
| [4] | Asmuni, H., Burke, E. K., Garibaldi, J. M., McCollum, B., & Parkes, A. J. (2009). An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables. Computers & Operations Research, 36(4), 981-1001. · Zbl 1162.90440 · doi:10.1016/j.cor.2007.12.007 |
| [5] | Balakrishnan, N., Lucena, A., & Wong, R. T. (1992). Scheduling examinations to reduce second order conflicts. Computers & Operations Research, 19, 353-361. · Zbl 0825.90530 · doi:10.1016/0305-0548(92)90066-E |
| [6] | Bilgin, B.; Özcan, E.; Korkmaz, E. E.; Burke, E. K. (ed.); Rudova, H. (ed.), An experimental study on hyper-heuristics and exam scheduling, No. 3867, 394-412 (2007), Berlin · doi:10.1007/978-3-540-77345-0_25 |
| [7] | Boizumault, P., Delon, Y., & Peridy, L. (1996). Constraint logic programming for examination timetabling. The Journal of Logic Programming, 26(2), 217-233. · Zbl 0871.68056 · doi:10.1016/0743-1066(95)00100-X |
| [8] | Burke, E. K., & Newall, J. P. (1999). A multistage evolutionary algorithm for the timetable problem. IEEE Transactions on Evolutionary Computation, 3(1), 63-74. · doi:10.1109/4235.752921 |
| [9] | Burke, E. K.; Newall, J. P., Enhancing timetable solutions with local search methods, No. 2740, 195-206 (2003), Berlin · doi:10.1007/978-3-540-45157-0_13 |
| [10] | Burke, E. K., & Newall, J. P. (2004). Solving examination timetabling problems through adaptation of heuristic orderings. Annals of Operations Research, 129, 107-134. · Zbl 1056.90141 · doi:10.1023/B:ANOR.0000030684.30824.08 |
| [11] | Burke, E. K.; Elliman, D. G.; Weare, R., A hybrid genetic algorithm for highly constrained timetabling problems, San Francisco, CA, USA, Pittsburgh, USA |
| [12] | Burke, E. K.; Hart, E.; Kendall, G.; Newall, J.; Ross, P.; Schulenburg, S.; Glover, F. (ed.); Kochenberger, G. (ed.), Hyper-heuristics: an emerging direction in modern search technology, 457-474 (2003), Dordrecht · Zbl 1102.90377 |
| [13] | Burke, E. K., Bykov, Y., Newall, J. P., & Petrovic, S. (2004a). A time-predefined local search approach to exam timetabling problem. IIE Transactions, 36(6), 509-528. · doi:10.1080/07408170490438410 |
| [14] | Burke, E. K.; Kingston, J.; Werra, D.; Gross, J. (ed.); Yellen, J. (ed.), Applications to timetabling, 445-474 (2004), London |
| [15] | Burke, E. K., Petrovic, S., & Qu, R. (2006). Case based heuristic selection for timetabling problems. Journal of Scheduling, 9(2), 115-132. · Zbl 1154.90423 · doi:10.1007/s10951-006-6775-y |
| [16] | Burke, E. K., Eckersley, A. J., McCollum, B., Petrovic, S., & Qu, R. (2010a). Hybrid variable neighbourhood approaches to university exam timetabling. European Journal of Operational Research, 206(1), 46-53. · Zbl 1188.90090 · doi:10.1016/j.ejor.2010.01.044 |
| [17] | Burke, E. K., Kendall, G., Misir, M., & Özcan, E. (2010b). Monte Carlo hyper-heuristics for examination timetabling. Annals of Operations Research. doi:10.1007/s10479-010-0782-2. · Zbl 1251.90394 |
| [18] | Burke, E. K., Pham, N., Qu, R., & Yellen, J. (2010c). Linear combinations of heuristics for examination timetabling. Annals of Operations Research. doi:10.1007/s10479-011-0854-y. · Zbl 1251.90119 |
| [19] | Caramia, M., Dell’Olmo, P., & Italiano, G. F. (2008). Novel local search based approaches to university examination timetabling. INFORMS Journal on Computing, 20, 86-99. · Zbl 1243.90222 · doi:10.1287/ijoc.1070.0220 |
| [20] | Carter, M. W. (1986). A survey of practical applications of examination timetabling algorithms. Operational Research, 34(2), 193-202. · doi:10.1287/opre.34.2.193 |
| [21] | Carter, M. W.; Laporte, G., Recent developments in practical examination timetabling, 3-21 (1996), London |
| [22] | Carter, M. W., Laporte, G., & Lee, S. (1996). Examination timetabling: algorithmic strategies and applications. The Journal of the Operational Research Society, 47(3), 373-383. · doi:10.1057/jors.1996.37 |
| [23] | Casey, S.; Thompson, J., Grasping the examination scheduling problem, No. 2740, 234-244 (2003), Berlin · doi:10.1007/978-3-540-45157-0_15 |
| [24] | Corr, P.; McCollum, B.; McGreevy, M.; McMullan, P., A new neural network based construction heuristic for the examination timetabling problem, No. 4193, 392-401 (2006), Berlin · doi:10.1007/11844297_40 |
| [25] | David, P.; Burke, E. K. (ed.); Carter, M. W. (ed.), A constraint-based approach for examination timetabling using local repair techniques, No. 1408, 169-186 (1998), Berlin · doi:10.1007/BFb0055888 |
| [26] | Gaspero, L.; Schaerf, A., Tabu search techniques for examination timetabling, 104-117 (2001), Berlin · Zbl 0982.68784 · doi:10.1007/3-540-44629-X_7 |
| [27] | Eley, M.; Burke, E. K. (ed.); Rudova, H. (ed.), Ant algorithms for the exam timetabling problem, No. 3867, 364-382 (2007), Berlin · doi:10.1007/978-3-540-77345-0_23 |
| [28] | Ersoy, E.; Özcan, E.; Sima Uyar, A.; Baptiste, P. (ed.); Kendall, G. (ed.); Kordon, A. M. (ed.); Sourd, F. (ed.), Memetic algorithms and hyperhill-climbers, 159-166 (2007), Berlin |
| [29] | Joslin, D. E., & Clements, D. P. (1999). “Squeaky wheel” optimization. The Journal of Artificial Intelligence Research, 10, 353-357. · Zbl 0918.90120 |
| [30] | Merlot, L. T. G.; Boland, N.; Hughes, B. D.; Stuckey, P. J.; Burke, E. K. (ed.); Erben, W. (ed.), A hybrid algorithm for the examination timetabling problem, No. 2740, 207-231 (2003), Berlin · doi:10.1007/978-3-540-45157-0_14 |
| [31] | Mumford, C. L. (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 |
| [32] | Özcan, E.; Ersoy, E., Final exam scheduler—FES, No. 2, 1356-1363 (2005) · doi:10.1109/CEC.2005.1554848 |
| [33] | Özcan, E., Bilgin, B., & Korkmaz, E. E. (2008). A comprehensive analysis of hyper-heuristics. Intelligent Data Analysis, 12(1), 3-23. |
| [34] | Özcan, E.; Bykov, Y.; Birben, M.; Burke, E. K., Examination timetabling using late acceptance hyper-heuristics, Trondheim, Norway, New York · doi:10.1109/CEC.2009.4983054 |
| [35] | Özcan, E., Misir, M., Ochoa, G., & Burke, E. K. (2010). A reinforcement learning—great-deluge hyper-heuristic for examination timetabling. International Journal of Applied Metaheuristic Computing, 1(1), 39-59. · doi:10.4018/jamc.2010102603 |
| [36] | Paquete, L.; Stuetzle, T., Empirical analysis of tabu search for the lexicographic optimization of the examination timetabling problem, Gent, Belgium |
| [37] | Petrovic, S.; Burke, E., University timetabling (2004), London |
| [38] | Petrovic, S.; Bykov, Y.; Burke, E. K. (ed.); Causmaecker, P. (ed.), A multiobjective optimisation technique for exam timetabling based on trajectories, No. 2740, 179-192 (2003), Berlin |
| [39] | 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(2), 482-491. · Zbl 1159.90528 · doi:10.1016/j.ejor.2008.07.023 |
| [40] | Qu, R.; Burke, E. K., Adaptive decomposition and construction for examination timetabling problems, Paris, France |
| [41] | Qu, R., Burke, E. K., Mccollum, B., Merlot, L. T., & Lee, S. Y. (2009). 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 |
| [42] | 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 |
| [43] | Ülker, Ö.; Özcan, E.; Korkmaz, E. E., Linear linkage encoding in grouping problems: applications on graph coloring and timetabling, No. 3867, 347-363 (2007), Berlin |
| [44] | White, G. M.; Xie, B. S.; Burke, E. K. (ed.); Erben, W. (ed.), Examination timetables and tabu search with longer-term memory, No. 2079, 85-103 (2001), Berlin · Zbl 0982.68630 · doi:10.1007/3-540-44629-X_6 |
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.
