Solving the High School Timetabling Problem to optimality by using ILS algorithms

  • Ademir Aparecido Constantino
  • Haroldo Gambini Santos
  • Wesley Romão
  • Landir Saviniec
    • Categories Meta Heuristics, Scheduling Tags , , Short URL: https://optimization-online.org/?p=12381

    The high school timetabling is a classical problem and has many combinatorial variations. It is NP-Complete and since the use of exact methods for this problem is restricted, heuristics are usually employed. This paper applies three Iterated Local Search (ILS) algorithms which includes two newly proposed neighborhood operators to heuristically solve a benchmark of the problem from literature. This benchmark has seven instances and the three largest ones are open. The results obtained by our algorithms have shown that these methods are effective and efficient to solve the problem, as they were capable to find optimal solutions for all instances and it helps to prove (using pre-computed lower bounds) the optimality for the open instances.

    Citation

    Research Group in Engineering Algorithm, Department of Informatics, State University of Maringá, Maringá, Brazil, April 2013.

    Article

    Download

    View Solving the High School Timetabling Problem to optimality by using ILS algorithms