×

A harmony search algorithm for university course timetabling. (English) Zbl 1251.90310

Summary: One of the main challenges for university administration is building a timetable for course sessions. This is not just about building a timetable that works, but building one that is as good as possible. In general, course timetabling is the process of assigning given courses to given rooms and timeslots under specific constraints. Harmony search algorithm is a new metaheuristic population-based algorithm, mimicking the musical improvisation process where a group of musicians play the pitches of their musical instruments together seeking a pleasing harmony. The major thrust of this algorithm lies in its ability to integrate the key components of population-based methods and local search-based methods in a simple optimization model. In this paper, a harmony search and a modified harmony search algorithm are applied to university course timetabling against standard benchmarks. The results show that the proposed methods are capable of providing viable solutions in comparison to previous works.

MSC:

90C27 Combinatorial optimization
90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming

Software:

Hyperheuristics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdullah, S., Burke, E. K., & McColum, B. (2005). An investigation of variable neighbourhood search for university course timetabling. In G. Kendall, L. Lei, M. Pinedo (Eds.), Proceedings of the 2nd multidisciplinary international conference on scheduling: theory and applications (MISTA) (pp. 413–427). New York, USA, 18–21 July 2005.
[2] Abdullah, S., Burke, E. K., & McCollum, B. (2007a). A hybrid evolutionary approach to the university course timetabling problem. In CEC 2007. IEEE congress on evolutionary computation 2007 (pp. 1764–1768). Singapore.
[3] Abdullah, S., Burke, E. K., & McCollum, B. (2007b). Using a randomised iterative improvement algorithm with composite neighbourhood structures for the university course timetabling problem. In Metaheuristic (pp. 153–169). · Zbl 1172.90393
[4] Arani, T., & Lofti, J. A. (1989). A three phased approach to final exam scheduling. IIE Transactions, 21(4), 86–96. · doi:10.1080/07408178908966211
[5] Asmuni, H., Burke, E. K., & Garibaldi, J. M. (2005). Fuzzy multiple heuristic ordering for course timetabling. In Proceedings of the 5th United Kingdom workshop on computational intelligence (UKCI05) (pp. 302–309).
[6] Blum, C., & Roli, A. (2003). Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Computing Surveys, 35(3), 268–308. · doi:10.1145/937503.937505
[7] Brélaz, D. (1979). New methods to color the vertices of a graph. Communications of the ACM, 22(4), 251–256. · Zbl 0394.05022 · doi:10.1145/359094.359101
[8] Burke, E. K., & Landa-Silva, J. D. (2005). The design of memetic algorithms for scheduling and timetabling problems. In Studies in fuzziness and soft computing: Vol. 166. Recent advances in memetic algorithms (pp. 289–311). Berlin: Springer.
[9] Burke, E. K., & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2), 266–280. · Zbl 1001.90030 · doi:10.1016/S0377-2217(02)00069-3
[10] Burke, E. K., Jackson, K., Kingston, J. H., & Weare, R. (1997). Automated university timetabling: The state of the art. The Computer Journal, 40(9), 565–571. · doi:10.1093/comjnl/40.9.565
[11] Burke, E. K., Kendall, G., & Soubeiga, E. (2003a). A tabu-search hyperheuristic for timetabling and rostering. Journal of Heuristics, 9(6), 451–470. · doi:10.1023/B:HEUR.0000012446.94732.b6
[12] Burke, E. K., Bykov, Y., Newall, J. P., & Petrovic, S. (2003b). A time-predefined approach to course timetabling. Yugoslav Journal of Operations Research, 13, 139–151. · Zbl 1055.90039 · doi:10.2298/YJOR0302139B
[13] Burke, E. K., de Werra, D., & Kingston, J. (2004). Applications to timetabling. In J. L. Gross, & J. Yellen (Eds.), Handbook of graph theory (pp. 445–474). London: CRC Press.
[14] Burke, E. K., McCollum, B., Meisels, A., Petrovic, S., & Qu, R. (2007). A graph-based hyper-heuristic for educational timetabling problems. European Journal of Operational Research, 176(1), 177–192. · Zbl 1137.90602 · doi:10.1016/j.ejor.2005.08.012
[15] Carter, M. W., & Laporte, G. (1997). Recent developments in practical course timetabling. In B. E. K., & M. C. (Eds.), Lecture notes in computer science: Vol. 1408. The practice and theory of automated timetabling (pp. 3–19). Berlin: Springer.
[16] Carter, M. W., Laporte, G., & Lee, S.Y. (1996). Examination timetabling: algorithmic strategies and applications. Journal of the Operational Research Society, 74, 373–383.
[17] Chiarandini, M., Birattari, M., Socha, K., & Rossi-Doria, O. (2006). An effective hybrid algorithm for university course timetabling. Journal of Scheduling, 9(5), 403–432. · Zbl 1154.90428 · doi:10.1007/s10951-006-8495-8
[18] Fesanghary, M., Mahdavi, M., Minary-Jolandan, M., & Alizadeh, Y. (2008). Hybridizing harmony search algorithm with sequential quadratic programming for engineering optimization problems. Computer Methods in Applied Mechanics and Engineering, 197(33–40), 3080–3091. · Zbl 1194.74243 · doi:10.1016/j.cma.2008.02.006
[19] Geem, Z. W. (2006). Optimal cost design of water distribution networks using harmony search. Engineering Optimization, 38(3), 259–280. · doi:10.1080/03052150500467430
[20] Geem, Z. W. (2007a). Harmony search algorithm for solving sudoku. In B. Apolloni, R. J. Howlett, & L. Jain (Eds.), Lecture notes in computer science (Lecture notes in artificial intelligence): Vol. 4692. KES 2007, Part I (pp. 371–378). Heidelberg: Springer.
[21] Geem, Z. W. (2007b). Optimal scheduling of multiple dam system using harmony search algorithm. In F. Sandoval, A. G. Prieto, J. Cabestany, & M. Graa (Eds.), Lecture notes in computer science: Vol. 4507. IWANN 2007 (pp. 316–323). Heidelberg: Springer.
[22] Geem, Z. W., & Choi, J. Y. (2007). Music composition using harmony search algorithm. In M. Giacobini (Ed.), Lecture notes in computer science: Vol. 4448. EvoWorkshops 2007 (pp. 593–600). Heidelberg: Springer.
[23] Geem, Z. W., Kim, J. H., & Loganathan, G. V. (2001). A new heuristic optimization algorithm: harmony search. Simulation, 76(2), 60–68. · doi:10.1177/003754970107600201
[24] Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Reading: Addison-Wesley. · Zbl 0721.68056
[25] Ingram, G., & Zhang, T. (2009). Overview of applications and developments in the harmony search algorithm. In Z. W. Geem (Ed.), Music-inspired harmony search algorithm (pp. 15–37). Berlin/Heidelberg: Springer.
[26] Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. In Proceedings IEEE international conference on neural networks (pp. 1942–1948).
[27] Kostuch, P. (2005). The university course timetabling problem with a three-phase approach. In E. K. Burke, & M. A. Trick (Eds.), Lecture notes in computer science: Vol. 3616. Practice and theory of automated timetabling (pp. 109–125). Berlin: Springer.
[28] Landa-Silva, D., & Obit, J. H. (2008). Great deluge with non-linear decay rate for solving course timetabling problems. In Proceedings of the 4th international IEEE conference on intelligent systems (IS 2008) (pp. 8.11–8.18). New York: IEEE Press.
[29] Landa-Silva, D., & Obit, J. H. (2009). Evolutionary non-linear great deluge for university course timetabling. In E. Corchado, X. Wu, E. Oja, E. Hristozov, & T. Jedlovcnik (Eds.), Lecture notes in computer science (Lecture notes in artificial intelligence): Vol. 5572. Proceeding of 4th international conference on hybrid artificial intelligence systems, HAIS 2009 (pp. 269–276). Berlin/Heidelberg: Springer.
[30] Lee, K. S., & Geem, Z. W. (2004). A new structural optimization method based on the harmony search algorithm. Computers and Structures, 82(9–10), 781–798. · doi:10.1016/j.compstruc.2004.01.002
[31] Lee, K. S., & Geem, Z. W. (2005). A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice. Computer Methods in Applied Mechanics and Engineering, 194(36–38), 3902–3933. · Zbl 1096.74042 · doi:10.1016/j.cma.2004.09.007
[32] Lee, K., Geem, Z. W., Lee, Sh., & Bae, Kw. (2005). The harmony search heuristic algorithm for discrete structural optimization. Engineering Optimization, 37(7), 663–684. · doi:10.1080/03052150500211895
[33] Lewis, R. (2008). A survey of metaheuristic-based techniques for university timetabling problems. OR Spectrum, 30, 167–190. · Zbl 1133.90341 · doi:10.1007/s00291-007-0097-0
[34] Lewis, R., & Paechter, B. (2004). New crossover operators for timetabling with evolutionary algorithms. In A. Lofti (Ed.), The fifth international conference on recent advances in soft computing RASC2004 (pp. 189–194). Nottingham, England.
[35] Lewis, R., & Paechter, B. (2005). Application of the grouping genetic algorithm to university course timetabling. In G. Raidl, & J. Gottlieb (Eds.), Evolutionary computation in combinatorial optimization (EvoCop) (pp. 144–153). Berlin: Springer. · Zbl 1119.68440
[36] 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. Tech. rep., Cardiff University, Cardiff Business School, Accounting and Finance Section.
[37] Malim, M. R., Khader, A. T., & Mustafa, A. (2006). Artificial immune algorithms for university timetabling. In E. K. Burke, H. Rudova (Eds.), Proceedings of the 6th international conference on practice and theory of automated timetabling (pp. 234–245). Brno, Czech Republic.
[38] McCollum, B. (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). Berlin: Springer.
[39] McCollum, B., Schaerf, A., Paechter, B., McMullan, P., Lewis, R., Parkes, A., Di Gaspero, L., Qu, R., & Burke, E. K. (2009). Setting the research agenda in automated timetabling: the second international timetabling competition. Informs Journal on Computing, DOI: 10.1287/ijoc.1090.0320 . · Zbl 1243.90007
[40] McMullan, P. (2007). An extended implementation of the great deluge algorithm for course timetabling. In ICCS ’07: Proceedings of the 7th international conference on computational science, Part I (pp. 538–545). Berlin/Heidelberg: Springer.
[41] Obit, J., Landa-Silva, D., Ouelhadj, D., & Sevaux, M. (2009). Non-linear great deluge with learning mechanism for solving the course timetabling problem. In Proceedings of the 8th metaheuristics international conference (MIC 2009).
[42] Qu, R., Burke, E. K., McCollum, B., Merlot, L. T. G., & 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
[43] Socha, K., Knowles, J.. & Samples, M. (2002). A max-min ant system for the university course timetabling problem. In Springer lecture notes in computer science: Vol. 2463. Proceedings of the 3rd international workshop on ant algorithms, ANTS 2002 (pp. 1–13). Berlin: Springer.
[44] Tuga, M., Berretta, R., & Mendes, A. (2007). A hybrid simulated annealing with kempe chain neighborhood for the university timetabling problem. In 6th IEEE/ACIS international conference on computer and information science (ICIS 2007), icis (pp. 400–405).
[45] Turabieh, H., Abdullah, S., & McCollum, B. (2009). Electromagnetism-like mechanism with force decay rate great deluge for the course timetabling problem. In Proceeding rough sets and knowledge technology (RSKT 2009).
[46] Wolpert, D. H., & Macready, W. G. (1997). No free lunch theorems for optimization. IEEE Transaction on Evolutionary Computation, 1(1), 67–82. · doi:10.1109/4235.585893
[47] Yang, X. S. (2009). Harmony search as a metaheuristic algorithm. In Z. W. Geem (Ed.), Music-inspired harmony search algorithm (pp. 1–14). Berlin/Heidelberg: Springer.
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.