Weitere Artikel dieser Ausgabe durch Wischen aufrufen
This paper presents a new single-parameter local search heuristic named step counting hill climbing algorithm (SCHC). It is a very simple method in which the current cost serves as an acceptance bound for a number of consecutive steps. This is the only parameter in the method that should be set up by the user. Furthermore, the counting of steps can be organised in different ways; therefore, the proposed method can generate a large number of variants and also extensions. In this paper, we investigate the behaviour of the three basic variants of SCHC on the university exam timetabling problem. Our experiments demonstrate that the proposed method shares the main properties with the late acceptance hill climbing method, namely its convergence time is proportional to the value of its parameter and a non-linear rescaling of a problem does not affect its search performance. However, our new method has two additional advantages: a more flexible acceptance condition and better overall performance. In this study, we compare the new method with late acceptance hill climbing, simulated annealing and great deluge algorithm. The SCHC has shown the strongest performance on the most of our benchmark problems used.
Abdullah, S., & Alzaqebah, M. (2014). An adaptive artificial bee colony and late acceptance hill-climbing algorithm for examination timetabling. Journal of Scheduling, 17, 249–262. CrossRef
Abuhamdah, A. (2010). Experimental result of late acceptance randomized descent algorithm for solving course timetabling problems. International Journal of Computer Science and Network Security, 10, 192–200.
Boese, K. D., Kahng, A. B., & Muddu, S. (1994). A new adaptive multi-start technique for combinatorial global optimizations. Operations Research Letters, 16, 101–113. CrossRef
Burke E. K., & Bykov, Y. (2008). A late acceptance strategy in hill-climbing for exam timetabling problems: Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling (PATAT2008), Montreal, Canada.
Burke E. K., & Bykov, Y. (2012). The Late Acceptance Hill Climbing heuristic. Technical report CSM-192, Computing Science and Mathematics, University of Stirling, UK.
Burke, E. K., Bykov, Y., Newall, J., & Petrovic, S. (2004). A time-predefined local search approach to exam timetabling problems. IIE Transactions, 36(6), 509–528. CrossRef
Burke, E. K., McColumn, B., Meisels, A., Petrovic, S., & Qu, R. (2007). A graph-based hyper-heuristic for educational timetabling problems. European Journal of Operational Research, 176, 177–192. CrossRef
Burke, E. K., & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140, 266–280.
Bykov Y., & Petrovic, S. (2013). An initial study of a novel Step Counting Hill Climbing heuristic applied to timetabling problems: Proceedings of 6th Multidisciplinary International Scheduling Conference (MISTA 2013), Gent, Belgium.
Carter, M. W., Laporte, G., & Lee, S. (1996). Examination timetabling: algorithmic strategies and applications. Journal of the Operational Research Society, 47, 373–383. CrossRef
Di Gaspero, L., & Schaerf, A. (2001). Tabu search techniques for examination timetabling. Practice and Theory of Automated Timetabling III, Lecture Notes in Computer Science. Berlin: Springer.
Erben, W. (2001). A grouping genetic algorithm for graph colouring and exam timetabling. Practice and Theory of Automated Timetabling III, Lecture Notes in Computer Science. Berlin: Springer.
Goerler, A., Schulte, F., & Voss, S. (2013). An application of late acceptance hill climbing to the traveling purchaser problem. Computational logistics, Lecture Notes in Computer Science. Berlin: Springer.
Gogos, C., Goulas, G., Alefragis, P., Kolonias, V., & Housos, E. (2010). Distributed Scatter Search for the examination timetabling problem. PATAT 2010 Proceedings of the 8th International Conference on the Practice and Theory of Automated Timetabling, Belfast, UK.
Jackson W., Özcan, E., & Drake, J. H. (2013). Late acceptance-based selection hyper-heuristics for cross-domain heuristic search. The 13th UK Workshop on Computational Intelligence, Guildford, UK.
Johnson, D. S., Aragon, C. R., McGeoch, L. A., & Schevon, C. (1989). Optimization by simulated annealing: an experimental evaluation. Part II, graph partitioning. Operations Research, 37(3), 865–892. CrossRef
Johnson, D. S., Aragon, C. R., McGeoch, L. A., & Schevon, C. (1991). Optimization by simulated annealing: an experimental evaluation; Part II, graph coloring and number partitioning. Operations Research, 39(3), 378–406.
McCollum, B., McMullan, P. J., Parkes, A. J., Burke, E. K., & Abdullah, S. (2009). An extended great deluge approach to the examination timetabling problem: Proceedings of the 4th Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA09), Dublin, Ireland, 424–434.
McCollum, B., Schaerf, A., Paechter, B., McMullan, P. J., Lewis, R., Parkes, A. J., et al. (2010). Setting the research agenda in automated timetabling: The second international timetabling competition. INFORMS Journal on Computing, 22, 120–130. CrossRef
Merlot, L., Boland, N., Hughes, B., & Stuckey, P. (2003). A hybrid algorithm for the examination timetabling problem. Practice and Theory of Automated Timetabling IV. Lecture Notes in Computer Science, Berlin: Springer
Muller, T. (2008). ITC2007 solver description: a hybrid approach. Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2008), Montreal, Canada.
Özcan, E., Bykov, Y., Birben, M., & Burke, E. K. (2009). Examination timetabling using late acceptance hyper-heuristics: Proceedings of the 2009 IEEE Congress on Evolutionary Computation (CEC’09), Trondheim, Norway.
Petrovic, S., & Bykov, Y. (2003). A multiobjective optimisation technique for exam timetabling based on trajectories. Practice and Theory of Automated Timetabling IV, Lecture Notes in Computer Science. Berlin: Springer.
Petrovic, S., Patel, V., & Young, Y. (2005). University timetabling with fuzzy constraints. Practice and Theory of Automated Timetabling V, Lecture Notes in Computer Science. Berlin: Springer.
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, 55–89.
Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13, 87–127.
Smith-Miles, K., & Lopes, L. (2012). Measuring instance difficulty for combinatorial optimization problems. Computers and Operations Research, 39, 875–889.
Swan, J., Drake, J., Ozcan, E., Goulding, J., & Woodward, J. (2013). A comparison of acceptance criteria for the Daily Car-Pooling problem. Computer and Information Sciences, III, 477–483. CrossRef
Thompson, J. M., & Dowsland, K. A. (1996). Variants of simulated annealing for the examination timetabling problem. Annals of Operations Research, 63, 105–128. CrossRef
Tierney, K. (2013). Late acceptance hill climbing for the liner shipping fleet repositioning. Proceedings of the 14th EU/ME Workshop, 21–27.
Verstichel, J., & Vanden Berghe, G. (2009). A late acceptance algorithm for the lock scheduling problem. Logistic Management, 2009(5), 457–478. CrossRef
Vancroonenburg, W., & Wauters, T. (2013) Extending the late acceptance metaheuristic for multi-objective optimization. Proceedings of the 6th Multidisciplinary International Scheduling conference: Theory & Applications (MISTA2013). Ghent, Belgium.
Yuan, B., Zhang, C., & Shao, X. (2015). A late acceptance hill-climbing algorithm for balancing two-sided assembly lines with multiple constraints. Journal of Intelligent Manufacturing, 26, 159–168.
- A Step Counting Hill Climbing Algorithm applied to University Examination Timetabling
- Springer US
Neuer Inhalt/© Stellmach, Neuer Inhalt/© Maturus, Pluta Logo/© Pluta, digitale Transformation/© Maksym Yemelyanov | Fotolia