×

An integer program and a hybrid genetic algorithm for the university timetabling problem. (English) Zbl 1365.90136

Summary: The university timetabling problem (UTP) has been studied by numerous research groups for decades. In addition to addressing hard and soft constraints, we extend the UTP by considering consecutiveness and periodicity constraints of multi-session lectures, which are common in many eastern Asian universities. Because schedulers can decide the consecutiveness and periodicity constraints for the multi-session lectures within a limited ratio, we consider these novel decision variables in our model. We develop a mixed integer linear program for the UTP. For the analysis, we convert the UTP into the three-dimensional container packing problem (3DCPP) and create a hybrid genetic algorithm (HGA), which has been shown to be efficient in solving the 3DCPP. We also develop a tabu search algorithm based on the existing UTP literature and compare the findings with that of our HGA. The results show that our HGA obtains a better solution than the tabu search algorithm in a reasonable amount of time.

MSC:

90B35 Deterministic scheduling theory in operations research
90B90 Case-oriented studies in operations research
90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1007/s10732-010-9154-y · Zbl 06700336 · doi:10.1007/s10732-010-9154-y
[2] DOI: 10.1287/mnsc.37.1.98 · doi:10.1287/mnsc.37.1.98
[3] DOI: 10.1093/comjnl/16.4.347 · Zbl 0271.68029 · doi:10.1093/comjnl/16.4.347
[4] DOI: 10.1007/s10479-010-0769-z · Zbl 1251.90310 · doi:10.1007/s10479-010-0769-z
[5] DOI: 10.1016/j.cie.2014.11.010 · doi:10.1016/j.cie.2014.11.010
[6] DOI: 10.1016/j.cor.2015.07.002 · Zbl 1349.90316 · doi:10.1016/j.cor.2015.07.002
[7] DOI: 10.1016/S0377-2217(00)00055-2 · Zbl 0979.90101 · doi:10.1016/S0377-2217(00)00055-2
[8] DOI: 10.1016/0377-2217(91)90254-S · Zbl 0747.90098 · doi:10.1016/0377-2217(91)90254-S
[9] DOI: 10.1016/0377-2217(94)90009-4 · Zbl 0809.90075 · doi:10.1016/0377-2217(94)90009-4
[10] DOI: 10.1016/j.ejor.2003.06.023 · Zbl 1067.90135 · doi:10.1016/j.ejor.2003.06.023
[11] DOI: 10.1016/S0377-2217(03)00103-6 · Zbl 1053.90078 · doi:10.1016/S0377-2217(03)00103-6
[12] DOI: 10.1016/j.ejor.2008.01.043 · Zbl 1156.90372 · doi:10.1016/j.ejor.2008.01.043
[13] DOI: 10.1016/0377-2217(85)90167-5 · Zbl 0553.90059 · doi:10.1016/0377-2217(85)90167-5
[14] DOI: 10.1057/palgrave.jors.2600469 · Zbl 0895.90115 · doi:10.1057/palgrave.jors.2600469
[15] DOI: 10.1057/jors.1990.143 · doi:10.1057/jors.1990.143
[16] DOI: 10.1016/S0377-2217(96)00209-3 · Zbl 0948.90157 · doi:10.1016/S0377-2217(96)00209-3
[17] W. Erben and J. Keppler, A genetic algorithm solving a weekly course-timetabling problem, in Practice and Theory of Automated Timetabling, E. Burke and P. Ross, eds., Springer, Berlin, 2005, pp. 198–211.
[18] DOI: 10.1007/s10696-013-9181-8 · doi:10.1007/s10696-013-9181-8
[19] Innet S., WSEAS Trans. Adv. Eng. Educ. 12 pp 243– (2007)
[20] DOI: 10.1007/s10951-010-0202-0 · Zbl 06255109 · doi:10.1007/s10951-010-0202-0
[21] DOI: 10.1007/s00500-013-1096-5 · Zbl 06506216 · doi:10.1007/s00500-013-1096-5
[22] DOI: 10.1016/j.amc.2012.07.036 · Zbl 1286.90084 · doi:10.1016/j.amc.2012.07.036
[23] DOI: 10.1016/0377-2217(92)90360-L · Zbl 0757.90033 · doi:10.1016/0377-2217(92)90360-L
[24] Karabulut K., AVDIS 3261 pp 441– (2004)
[25] DOI: 10.1007/s10479-010-0700-7 · Zbl 1251.90160 · doi:10.1007/s10479-010-0700-7
[26] DOI: 10.1093/comjnl/12.4.307 · doi:10.1093/comjnl/12.4.307
[27] DOI: 10.1080/10556781003664739 · Zbl 1225.90054 · doi:10.1080/10556781003664739
[28] DOI: 10.1016/j.ejor.2008.12.007 · Zbl 1190.90166 · doi:10.1016/j.ejor.2008.12.007
[29] DOI: 10.1007/s10100-010-0184-1 · Zbl 1339.90353 · doi:10.1007/s10100-010-0184-1
[30] P. McMullan, An extended implementation of the great deluge algorithm for course timetabling, in Computational Science–ICCS 2007, Y. Shi, G.D. van Albada, J. Dongarra, and P.M.A. Sloot, eds., Springer, Berlin, 2007, pp. 538–545. · Zbl 05293249 · doi:10.1007/978-3-540-72584-8_71
[31] DOI: 10.1016/j.amc.2005.07.039 · Zbl 1092.90025 · doi:10.1016/j.amc.2005.07.039
[32] DOI: 10.1007/s00291-013-0356-1 · Zbl 1305.90355 · doi:10.1007/s00291-013-0356-1
[33] DOI: 10.1016/0377-2217(82)90012-1 · Zbl 0471.90061 · doi:10.1016/0377-2217(82)90012-1
[34] DOI: 10.1007/s10479-008-0449-4 · Zbl 1201.90176 · doi:10.1007/s10479-008-0449-4
[35] O. Rossi-Doria, M. Sampels, M. Birattari, M. Chiarandini, M. Dorigo, L.M. Gambardella, and B. Paechter, A comparison of the performance of different metaheuristics on the timetabling problem, in Practice and Theory of Automated Timetabling IV, E. Burke and P. De Causmaecker, eds., Springer, Berlin, 2003, pp. 329–351. · doi:10.1007/978-3-540-45157-0_22
[36] DOI: 10.1007/s00291-006-0074-z · Zbl 1168.90670 · doi:10.1007/s00291-006-0074-z
[37] K. Socha, J. Knowles, and M. Sampels, A max-min ant system for the university course timetabling problem, in Ant Algorithms, M. Dorigo, G. Di Caro, and M. Sampels, eds., Springer, Berlin, 2002, pp. 1–13. · Zbl 05876650 · doi:10.1007/3-540-45724-0_1
[38] DOI: 10.1016/j.ejor.2014.03.046 · Zbl 1338.90183 · doi:10.1016/j.ejor.2014.03.046
[39] DOI: 10.1287/mnsc.30.12.1473 · Zbl 0554.90058 · doi:10.1287/mnsc.30.12.1473
[40] H. Turabieh, S. Abdullah, and B. Mccollum, Electromagnetism-like mechanism with force decay rate great deluge for the course timetabling problem, in Rough Sets and Knowledge Technology, P. Wen, Y. Li, L. Polkowski, Y. Yao, S. Tsumoto, and G. Wang, eds., Springer, Berlin, 2009, pp. 497–504. · Zbl 05574208 · doi:10.1007/978-3-642-02962-2_63
[41] DOI: 10.1016/j.ejor.2009.09.014 · Zbl 1177.90192 · doi:10.1016/j.ejor.2009.09.014
[42] DOI: 10.1016/j.ejor.2012.04.036 · Zbl 1253.90015 · doi:10.1016/j.ejor.2012.04.036
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.