Skip to main content

2016 | OriginalPaper | Buchkapitel

A Hybrid Shuffled Frog-Leaping Algorithm for the University Examination Timetabling Problem

verfasst von : Nuno Leite, Fernando Melício, Agostinho C. Rosa

Erschienen in: Computational Intelligence

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The problem of examination timetabling is studied in this work. We propose a hybrid solution heuristic based on the Shuffled Frog-Leaping Algorithm (SFLA) for minimising the conflicts in the students’s exams. The hybrid algorithm, named Hybrid SFLA (HSFLA), improves a population of frogs (solutions) by iteratively optimising each memeplex, and then shuffling the memeplexes in order to distribute the best performing frogs by the memeplexes. In each iteration the frogs are improved based on three operators: crossover and mutation operators, and a local search operator based on the Simulated Annealing metaheuristic. For the mutation and local search, we use two well known neighbourhood structures. The performance of the proposed method is evaluated on the 13 instances of the Toronto datasets from the literature. Computational results show that the HSFLA is competitive with state-of-the-art methods, obtaining the best results on average in seven of the 13 instances.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Abdullah, S., Alzaqebah, M.: A hybrid self-adaptive bees algorithm for examination timetabling problems. Appl. Soft Comput. 13(8), 3608–3620 (2013)CrossRef Abdullah, S., Alzaqebah, M.: A hybrid self-adaptive bees algorithm for examination timetabling problems. Appl. Soft Comput. 13(8), 3608–3620 (2013)CrossRef
2.
Zurück zum Zitat Abdullah, S., Turabieh, H.: A hybridization of electromagnetic-like mechanism and great deluge for examination timetabling problems. In: Blesa, C.J., Blum, C., Gaspero, L.D., Roli, A., Sampels, M. (eds.) Hybrid Metaheuristics. Lecture Notes in Computer Science, pp. 60–72. Springer, Berlin (2009)CrossRef Abdullah, S., Turabieh, H.: A hybridization of electromagnetic-like mechanism and great deluge for examination timetabling problems. In: Blesa, C.J., Blum, C., Gaspero, L.D., Roli, A., Sampels, M. (eds.) Hybrid Metaheuristics. Lecture Notes in Computer Science, pp. 60–72. Springer, Berlin (2009)CrossRef
3.
Zurück zum Zitat Abdullah, S., Turabieh, H., McCollum, B.: A tabu-based memetic approach for examination timetabling problems. In: Yu, J., Greco, S., Lingras, P., Wang, G. (eds.) RSKT. Lecture Notes in Computer Science, pp. 574–581. Springer, Berlin (2010) Abdullah, S., Turabieh, H., McCollum, B.: A tabu-based memetic approach for examination timetabling problems. In: Yu, J., Greco, S., Lingras, P., Wang, G. (eds.) RSKT. Lecture Notes in Computer Science, pp. 574–581. Springer, Berlin (2010)
4.
Zurück zum Zitat Amiri, B., Fathian, M., Maroosi, A.: Application of shuffled frog-leaping algorithm on clustering. Int. J. Adv. Manuf. Technol. 45(1–2), 199–209 (2009)CrossRef Amiri, B., Fathian, M., Maroosi, A.: Application of shuffled frog-leaping algorithm on clustering. Int. J. Adv. Manuf. Technol. 45(1–2), 199–209 (2009)CrossRef
5.
Zurück zum Zitat Burke, E., Bykov, Y., Newall, J., Petrovic, S.: A time-predefined local search approach to exam timetabling problems. IIE Trans. 36(6), 509–528 (2004)CrossRef Burke, E., Bykov, Y., Newall, J., Petrovic, S.: A time-predefined local search approach to exam timetabling problems. IIE Trans. 36(6), 509–528 (2004)CrossRef
6.
Zurück zum Zitat Burke, E., Eckersley, A., McCollum, B., Petrovic, S., Qu, R.: Hybrid variable neighbourhood approaches to university exam timetabling. Eur. J. Oper. Res. 206(1), 46–53 (2010)MathSciNetCrossRef Burke, E., Eckersley, A., McCollum, B., Petrovic, S., Qu, R.: Hybrid variable neighbourhood approaches to university exam timetabling. Eur. J. Oper. Res. 206(1), 46–53 (2010)MathSciNetCrossRef
7.
Zurück zum Zitat Burke, E., Newall, J.: Solving examination timetabling problems through adaption of heuristic orderings. Ann. Oper. Res. 129(1–4), 107–134 (2004)MathSciNetCrossRef Burke, E., Newall, J.: Solving examination timetabling problems through adaption of heuristic orderings. Ann. Oper. Res. 129(1–4), 107–134 (2004)MathSciNetCrossRef
8.
Zurück zum Zitat Burke, E.K., Bykov, Y.: Solving exam timetabling problems with the flex-deluge algorithm. In: Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling, pp. 370–372 (2006). ISBN:80–210–3726–1 Burke, E.K., Bykov, Y.: Solving exam timetabling problems with the flex-deluge algorithm. In: Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling, pp. 370–372 (2006). ISBN:80–210–3726–1
9.
Zurück zum Zitat Burke, E.K., Bykov, Y. (2008) A late acceptance strategy in Hill-Climbing for exam timetabling problems. In: PATAT’08 Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling (2008) Burke, E.K., Bykov, Y. (2008) A late acceptance strategy in Hill-Climbing for exam timetabling problems. In: PATAT’08 Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling (2008)
10.
Zurück zum Zitat Burke, E.K.: Enhancing timetable solutions with local search methods. In: Burke, E.K., Causmaecker, P.D. (eds.) PATAT. Lecture Notes in Computer Science, pp. 195–206. Springer, Belin (2002) Burke, E.K.: Enhancing timetable solutions with local search methods. In: Burke, E.K., Causmaecker, P.D. (eds.) PATAT. Lecture Notes in Computer Science, pp. 195–206. Springer, Belin (2002)
11.
Zurück zum Zitat Caramia, M., Dell’Olmo, P., Italiano, G.F.: Novel local-search-based approaches to university examination timetabling. INFORMS J. Comput. 20(1), 86–99 (2008)MathSciNetCrossRef Caramia, M., Dell’Olmo, P., Italiano, G.F.: Novel local-search-based approaches to university examination timetabling. INFORMS J. Comput. 20(1), 86–99 (2008)MathSciNetCrossRef
12.
Zurück zum Zitat Carter, M., Laporte, G.: Recent developments in practical examination timetabling. In: Burke, E., Ross, P. (eds.) Practice and Theory of Automated Timetabling. Lecture Notes in Computer Science, vol. 1153, pp. 1–21. Springer, Berlin (1996)CrossRef Carter, M., Laporte, G.: Recent developments in practical examination timetabling. In: Burke, E., Ross, P. (eds.) Practice and Theory of Automated Timetabling. Lecture Notes in Computer Science, vol. 1153, pp. 1–21. Springer, Berlin (1996)CrossRef
13.
Zurück zum Zitat Carter, M., Laporte, G., Lee, S.Y.: Examination timetabling: algorithmic strategies and applications. J. Oper. Res. Soc. 47(3), 373–383 (1996)CrossRef Carter, M., Laporte, G., Lee, S.Y.: Examination timetabling: algorithmic strategies and applications. J. Oper. Res. Soc. 47(3), 373–383 (1996)CrossRef
14.
Zurück zum Zitat Carter, M.W.: A survey of practical applications of examination timetabling algorithms. Oper. Res. 34(2), 193–202 (1986)MathSciNetCrossRef Carter, M.W.: A survey of practical applications of examination timetabling algorithms. Oper. Res. 34(2), 193–202 (1986)MathSciNetCrossRef
15.
Zurück zum Zitat Demeester, P., Bilgin, B., Causmaecker, P.D., Berghe, G.V.: A hyperheuristic approach to examination timetabling problems: benchmarks and a new problem from practice. J. Sched. 15(1), 83–103 (2012)CrossRef Demeester, P., Bilgin, B., Causmaecker, P.D., Berghe, G.V.: A hyperheuristic approach to examination timetabling problems: benchmarks and a new problem from practice. J. Sched. 15(1), 83–103 (2012)CrossRef
16.
Zurück zum Zitat Eusuff, M., Lansey, K., Pasha, F.: Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization. Eng. Optim. 38(2), 129–154 (2006)MathSciNetCrossRef Eusuff, M., Lansey, K., Pasha, F.: Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization. Eng. Optim. 38(2), 129–154 (2006)MathSciNetCrossRef
17.
Zurück zum Zitat Eusuff, M.M., Lansey, K.E.: Optimization of water distribution network design using the shuffled frog leaping algorithm. J. Water Res. Plan. Manag. 129(3), 210–225 (2003)CrossRef Eusuff, M.M., Lansey, K.E.: Optimization of water distribution network design using the shuffled frog leaping algorithm. J. Water Res. Plan. Manag. 129(3), 210–225 (2003)CrossRef
18.
Zurück zum Zitat Kendall, G., Hussin, N.: An investigation of a tabu-search-based hyper-heuristic for examination timetabling. In: Kendall, G., Burke, E., Petrovic, S., Gendreau, M. (eds.) Multidisciplinary Scheduling: Theory and Applications, pp. 309–328. Springer, New York (2005)CrossRef Kendall, G., Hussin, N.: An investigation of a tabu-search-based hyper-heuristic for examination timetabling. In: Kendall, G., Burke, E., Petrovic, S., Gendreau, M. (eds.) Multidisciplinary Scheduling: Theory and Applications, pp. 309–328. Springer, New York (2005)CrossRef
19.
Zurück zum Zitat Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671–680 (1983)MathSciNetCrossRef Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671–680 (1983)MathSciNetCrossRef
20.
Zurück zum Zitat Leite, N., Melício, F., Rosa, A.: Solving the examination timetabling problem with the shuffled frog-leaping algorithm. In: Proceedings of the 5th International Joint Conference on Computational Intelligence, pp. 175–180 (2013) Leite, N., Melício, F., Rosa, A.: Solving the examination timetabling problem with the shuffled frog-leaping algorithm. In: Proceedings of the 5th International Joint Conference on Computational Intelligence, pp. 175–180 (2013)
21.
Zurück zum Zitat Merlot, L., Boland, N., Hughes, B., Stuckey, P.: A hybrid algorithm for the examination timetabling problem. In: Burke, E., Causmaecker, P. (eds.) Practice and Theory of Automated Timetabling IV. Lecture Notes in Computer Science, vol. 2740, pp. 207–231. Springer, Berlin (2003)CrossRef Merlot, L., Boland, N., Hughes, B., Stuckey, P.: A hybrid algorithm for the examination timetabling problem. In: Burke, E., Causmaecker, P. (eds.) Practice and Theory of Automated Timetabling IV. Lecture Notes in Computer Science, vol. 2740, pp. 207–231. Springer, Berlin (2003)CrossRef
22.
Zurück zum Zitat Petrovic, S., Burke, E.: University timetabling. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chapter 45. Chapman Hall/CRC Press, London (2004) Petrovic, S., Burke, E.: University timetabling. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chapter 45. Chapman Hall/CRC Press, London (2004)
23.
Zurück zum Zitat Qu, R., Burke, E., McCollum, B., Merlot, L.T.G., Lee, S.Y.: A survey of search methodologies and automated system development for examination timetabling. J. Sched. 12, 55–89 (2009)MathSciNetCrossRef Qu, R., Burke, E., McCollum, B., Merlot, L.T.G., Lee, S.Y.: A survey of search methodologies and automated system development for examination timetabling. J. Sched. 12, 55–89 (2009)MathSciNetCrossRef
24.
Zurück zum Zitat Rahimi-Vahed, A., Mirzaei, A.H.: A hybrid multi-objective shuffled frog-leaping algorithm for a mixed-model assembly line sequencing problem. Comput. Ind. Eng. 53(4), 642–666 (2007)CrossRef Rahimi-Vahed, A., Mirzaei, A.H.: A hybrid multi-objective shuffled frog-leaping algorithm for a mixed-model assembly line sequencing problem. Comput. Ind. Eng. 53(4), 642–666 (2007)CrossRef
25.
Zurück zum Zitat Sabar, N.R., Ayob, M., Kendall, G.: Solving examination timetabling problems using honey-bee mating optimization (etp-hbmo). In: Blazewicz, J., Drozdowski, M., Kendall, G., McCollum, B. (eds.) Proceedings of the 4th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2009), 10–12 August 2009, Ireland, Dublin, pp. 399–408 (2009) Sabar, N.R., Ayob, M., Kendall, G.: Solving examination timetabling problems using honey-bee mating optimization (etp-hbmo). In: Blazewicz, J., Drozdowski, M., Kendall, G., McCollum, B. (eds.) Proceedings of the 4th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2009), 10–12 August 2009, Ireland, Dublin, pp. 399–408 (2009)
26.
Zurück zum Zitat Thompson, J.M., Dowsland, K.A.: A robust simulated annealing based examination timetabling system. Comput. OR 25(7–8), 637–648 (1998)CrossRef Thompson, J.M., Dowsland, K.A.: A robust simulated annealing based examination timetabling system. Comput. OR 25(7–8), 637–648 (1998)CrossRef
27.
Zurück zum Zitat Turabieh, H.: A hybrid fish swarm optimisation algorithm for solving examination timetabling problems. LION. Lecture Notes in Computer Science, pp. 539–551. Springer, Berlin (2011) Turabieh, H.: A hybrid fish swarm optimisation algorithm for solving examination timetabling problems. LION. Lecture Notes in Computer Science, pp. 539–551. Springer, Berlin (2011)
28.
Zurück zum Zitat Wang, Y.-M., Pan, Q.-K., Ji, J.-Z.: Discrete shuffled frog leaping algorithm for examination timetabling problem. Comput. Eng. Appl. 45(36), 40 (2009) Wang, Y.-M., Pan, Q.-K., Ji, J.-Z.: Discrete shuffled frog leaping algorithm for examination timetabling problem. Comput. Eng. Appl. 45(36), 40 (2009)
29.
Zurück zum Zitat Xu, Y., Wang, L., Liu, M., Wang, S.-Y.: An effective shuffled frog-leaping algorithm for hybrid flow-shop scheduling with multiprocessor tasks. Int. J. Adv. Manuf. Technol. 1–9 (2013) Xu, Y., Wang, L., Liu, M., Wang, S.-Y.: An effective shuffled frog-leaping algorithm for hybrid flow-shop scheduling with multiprocessor tasks. Int. J. Adv. Manuf. Technol. 1–9 (2013)
30.
Zurück zum Zitat Xue-hui, L., Ye, Y., Xia, L.: Solving TSP with shuffled frog-leaping algorithm. In: Eighth International Conference on Intelligent Systems Design and Applications, 2008, ISDA’08, vol. 3, pp. 228–232 (2008) Xue-hui, L., Ye, Y., Xia, L.: Solving TSP with shuffled frog-leaping algorithm. In: Eighth International Conference on Intelligent Systems Design and Applications, 2008, ISDA’08, vol. 3, pp. 228–232 (2008)
31.
Zurück zum Zitat Yang, Y., Petrovic, S.: A novel similarity measure for heuristic selection in examination timetabling. In: Burke, E., Trick, M. (eds.) Practice and Theory of Automated Timetabling V. Lecture Notes in Computer Science, vol. 3616, pp. 247–269. Springer, Berlin (2005)CrossRef Yang, Y., Petrovic, S.: A novel similarity measure for heuristic selection in examination timetabling. In: Burke, E., Trick, M. (eds.) Practice and Theory of Automated Timetabling V. Lecture Notes in Computer Science, vol. 3616, pp. 247–269. Springer, Berlin (2005)CrossRef
Metadaten
Titel
A Hybrid Shuffled Frog-Leaping Algorithm for the University Examination Timetabling Problem
verfasst von
Nuno Leite
Fernando Melício
Agostinho C. Rosa
Copyright-Jahr
2016
Verlag
Springer International Publishing
DOI
https://doi.org/10.1007/978-3-319-23392-5_10