Solving the High School Timetabling Problem to optimality by using ILS algorithms
Landir Saviniec (landir.saviniecgmail.com)
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.
Entry Submitted: 04/17/2013
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|