Iterated local search using an add and delete hyper- heuristic for university course timetabling

Article English OPEN
Soria-Alcaraz, Jorge A. ; Özcan, Ender ; Swan, Jerry ; Kendall, Graham ; Carpio, Martin (2016)

Hyper-heuristics are (meta-)heuristics that operate at a higher level to choose or generate a set of low-level (meta-)heuristics in an attempt of solve difficult optimization problems. Iterated local search (ILS) is a well-known approach for discrete optimization, combining perturbation and hill-climbing within an iterative framework. In this study, we introduce an ILS approach, strengthened by a hyper-heuristic which generates heuristics based on a fixed number of add and delete operations. The performance of the proposed hyper-heuristic is tested across two different problem domains using real world benchmark of course timetabling instances from the second International Timetabling Competition Tracks 2 and 3. The results show that mixing add and delete operations within an ILS framework yields an effective hyper-heuristic approach.
  • References (44)
    44 references, page 1 of 5

    Figure 3: Example of o ered timeslots M onday and W ednesday T uesday and T hursday F riday t1 t2 t9 t3 t4 t10 t5 t6 t11 t7 t8 t12

    [1] E. O zcan, B. Bilgin, E. E. Korkmaz, A comprehensive analysis of hyperheuristics, Intell. Data Anal. 12 (1) (2008) 3{23.

    [2] E. K. Burke, M. Gendreau, M. Hyde, G. Kendall, G. Ochoa, E. Ozcan, R. Qu, Hyper-heuristics: A survey of the state of the art, J Oper Res Soc 64 (12) (2013) 1695{1724.

    [3] P. Cowling, G. Kendall, E. Soubeiga, A hyperheuristic approach to scheduling a sales summit, in: E. Burke, W. Erben (Eds.), Practice and Theory of Automated Timetabling III, Vol. 2079 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2001, pp. 176{190.

    [4] E. K. Burke, M. Hyde, G. Kendall, G. Ochoa, E. Ozcan, J. Woodward, Handbook of Metaheuristics, Vol. 146 of International Series in Operations Research & Management Science, Springer, 2010, Ch. A Classi cation of Hyperheuristic Approaches, pp. 449{468, chapter 15.

    [5] S. Even, A. Itai, A. Shamir, On the complexity of timetable and multicommodity ow problems, SIAM J. Comput. 5 (4) (1976) 691{703.

    [6] T. B. Cooper, J. H. Kingston, The compexity of timetable construction problems, Ph.D. thesis, The University of Sydney (1995).

    [7] R. J. Willemen, School timetable constructrion: Algorithms and complexity, Ph.D. thesis, Institutefor Programming research and Algorithms (2002).

    [8] B. McCollum, A. Schaerf, B. Paechter, P. McMullan, R. Lewis, A. J. Parkes, L. D. Gaspero, R. Qu, E. K. Burke, Setting the research agenda in automated timetabling: The second international timetabling competition, Informs Journal on computing 22 (1) (2010) 120{130.

    [9] R. Lewis, Metaheuristics for university course timetabling, Ph.D. thesis, University of Notthingham. (August 2006).

  • Metrics
    No metrics available
Share - Bookmark