LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Burke, Edmund; Qu, Rong; Soghier, Amr (2014)
Publisher: Springer
Languages: English
Types: Article
Subjects:
This paper presents a hyper-heuristic approach which hybridises low-level heuristic moves to improve timetables. Exams which cause a soft-constraint violation in the timetable are ordered and rescheduled to produce a better timetable. It is observed that both the order in which exams are rescheduled and the heuristic moves used to reschedule the exams and improve the timetable affect the quality of the solution produced. After testing different combinations in a hybrid hyper-heuristic approach, the Kempe chain move heuristic and time-slot swapping heuristic proved to be the best heuristic moves to use in a hybridisation. Similarly, it was shown that ordering the exams using Saturation Degree and breaking any ties using Largest Weighted Degree produce the best results. Based on these observations, a methodology is developed to adaptively hybridise the Kempe chain move and timeslot swapping heuristics in two stages. In the first stage, random heuristic sequences are generated and automatically analysed. The heuristics repeated in the best sequences are fixed while the rest are kept empty. In the second stage, sequences are generated by randomly assigning heuristics to the empty positions in an attempt to find the best heuristic sequence. Finally, the generated sequences are applied to the problem. The approach is tested on the Toronto benchmark and the exam timetabling track of the second International Timetabling Competition, to evaluate its generality. The hyper-heuristic with low-level improvement heuristics approach was found to generalise well over the two different datasets and performed comparably to the state of the art approaches.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • 1. S. Abdullah, H. Turabieh, and B. McCollum. A hybridization of electromagnetic-like mechanism and great deluge for examination timetabling problems. In Proceedings of the 6th International Workshop on Hybrid Metaheuristics (HM2009), volume 5818 of Lecture Notes in Computer Science, pages 60-72. Springer, 2009.
    • 2. H. Asmuni, E.K. Burke, J. Garibaldi, and B. McCollum. Fuzzy multiple ordering criteria for examination timetabling. In E.K. Burke and M. Trick, editors, Selected Papers from the 5th International Conference on the Practice and Theory of Automated Timetabling, volume 3616 of Lecture Notes in Computer Science, pages 334-353. Springer, 2004.
    • 3. H. Asmuni, E.K. Burke, J. Garibaldi, B. McCollum, and A.J. Parkes. An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables. Computers and Operations Research, 36(4):981-1001, 2009.
    • 4. M. Atsuta, K. Nonobe, and T. Ibaraki. Itc2007 track 1: An approach using general csp solver. In Practice and Theory of Automated Timetabling (PATAT 2008), pages 19-22, August 2008.
    • 5. B. Biligan, E. Ozcan, and Korkmaz E.E. An experimental study on hyper-heuristics and exam timetabling. In E. Burke and H. Rudova, editors, Practice and Theory of Automated Timetabling VI: Selected Papers from the 6th International Conference PATAT 2006, volume 3867 of Lecture Notes in Computer Science, pages 394-412, 2007.
    • 6. E.K. Burke and Y. Bykov. A late acceptance strategy in hill-climbing for examination timetabling problems. In Proceedings of the conference on the Practice and Theory of Automated Timetabling(PATAT), 2008.
    • 7. E.K. Burke, A. Eckersley, B. McCollum, S. Petrovic, and R. Qu. Hybrid variable neighbourhood approaches to university exam timetabling. European Journal of Operational Research (EJOR), 206:46- 53, 2010.
    • 8. E.K. Burke, G. Kendall, J. Newall, E. Hart, P. Ross, and S. Schulenburg. Hyper-heuristics: An emerging direction in modern search technology. In F. Glover and G. Kochenberger, editors, Handbook of MetaHeuristics, pages 457-474. Kluwer, 2003.
    • 9. E.K. Burke, B. McCollum, A. Meisels, S. Petrovic, and R. Qu. A graph-based hyper-heuristic for educational timetabling problems. European Journal of Operational Research, 176:177-192, 2007.
    • 10. E.K. Burke, R. Qu, and A. Soghier. Adaptive tie breaking and hybridisation in a graph-based hyperheuristic for exam timetabling problems. under review at European Journal of Operational Research, 2009.
    • 11. M. Caramia, P. Dell Olmo, and G.F. Italiano. Novel local-search-based approaches to university examination timetabling. Informs Journal of Computing, 20(1):86-99, 2008.
    • 12. M.W. Carter, G. Laporte, and S.Y. Lee. Examination timetabling: Algorithmic strategies and applications. Journal of Operational Research Society, 74:373-383, 1996.
    • 13. G. De Smet. Itc2007 - examination track. In Practice and Theory of Automated Timetabling (PATAT 2008), pages 19-22, August 2008.
    • 14. E. Ersoy, E. Ozcan, and Uyar S. Memetic algorithms and hill-climbers. In P. Baptiste, G. Kendall, A.M. Kordon, and F. Sourd, editors, Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications Conference(MISTA2007), pages 159-166, 2007.
    • 15. C. Gogos, P. Alefragis, and E. Housos. A multi-staged algorithmic process for the solution of the examination timetabling problem. In Practice and Theory of Automated Timetabling (PATAT 2008), pages 19-22, 2008.
    • 16. G. Kendall and N. Mohd Hussin. An investigation of a tabu search based hyper-heuristic for examination timetabling. In G. Kendall, E. Burke, S. Petrovic, and M. Gendreau, editors, Selected Papers from MISTA 2005, pages 309-328. Springer, 2005.
    • 17. B. McCollum, P. McMullan, A. J. Parkes, E. K. Burke, and S. Abdullah. An extended great deluge approach to the examination timetabling problem. In Proceedings of the 4th Multidisciplinary International Scheduling: Theory and Applications 2009 (MISTA 2009), pp. 424-434, 10-12 August , Dublin, Ireland, 2009.
    • 18. B. McCollum, A. Schaerf, B. Paechter, P. McMullan, R. Lewis, L. Di Gaspero, A. J. Parkes, R. Qu, and E. K. Burke. Setting the research agenda in automated timetabling: The second international timetabling competition. INFORMS Journal of Computing, doi: 10.1287/ijoc.1090.0320, 2008.
    • 19. T. Muller. Itc 2007 solver description: A hybrid approach. In Practice and Theory of Automated Timetabling (PATAT 2008), pages 19-22, August 2008.
    • 20. N. Pillay. A developmental approach to the examination timetabling problem. In Practice and Theory of Automated Timetabling (PATAT 2008), pages 19-22, August 2008.
    • 21. N. Pillay. Evolving hyper-heuristics for a highly constrained examination timetabling problem. In Proceedings of the 8th International Conference on the Practice and Theory of Automated Timetabling (PATAT'10), pages 336-346, 2010.
    • 22. N. Pillay and W. Banzhaf. A genetic programming approach to the generation of hyper-heuristic systems for the uncapicitated examination timetabling problem. In Neves et al., editor, Progress in Artificial Intelligence, volume 4874 of Lecture Notes in Artificial Intelligence, pages 223-234, 2007.
    • 23. N. Pillay and W. Banzhaf. A study of heuristic combinations for hyper-heuristic systems for the uncapicitated examination timetabling problem. European Journal of Operational Research, 197:482-491, 2009.
    • 24. R. Qu and E.K. Burke. Hybridisations within a graph-based hyper-heuristic framework for university timetabling problems. Journal of Operational Research Society, 60:1273-1285, 2009.
    • 25. R. Qu, E.K. Burke, and B. McCollum. Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems. European Journal of Operational Research, 198(2):392-404, 2009.
    • 26. R. Qu, E.K. Burke, B. McCollum, L.T.G. Merlot, and S.Y. Lee. A survey of search methodologies and automated approaches for examination timetabling. Journal of Scheduling, 12(1):55-89, 2009.
    • 27. J.M. Thompson and K.A. Dowsland. Variants of simulated annealing for the examination timetabling problem. Annuals of Operations Research, 63:105-128, 1996.
    • 28. Y. Yang and S. Petrovic. A novel similarity measure for heuristic selection in examination timetabling. In Practice and Theory of Automated Timetabling: Selected papers from the 5th International Conference .Lecture Notes in Computer Science, volume 3616, pages 377-396, 2005.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article