Optimization Online


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

Landir Saviniec (landir.saviniec***at***gmail.com)
Ademir Aparecido Constantino (ademir.uem***at***gmail.com)
Wesley Romão (wesley.uem***at***gmail.com)
Haroldo Gambini Santos (haroldo***at***iceb.ufop.br)

Abstract: 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.

Keywords: High School Timetabling Problem, Iterated Local Search, Neighborhood Operators.

Category 1: Combinatorial Optimization (Meta Heuristics )

Category 2: Applications -- OR and Management Sciences (Scheduling )

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

Download: [PDF]

Entry Submitted: 04/17/2013
Entry Accepted: 04/19/2013
Entry Last Modified: 09/19/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society