Operadores de vizinhança eficientes para algoritmos de busca local aplicados ao problema de horários em escolas

Abstract

This paper addresses the high school timetabling problem. This is a classical problem and has many combinatorial variations. It is NP-Complete and is usually tackled using heuristic methods. In this work we propose local search algorithms to solve a variant of the problem faced on thirteen brazilian public high schools. The work performs a comparative study among two proposed neighborhood operators and an operator from literature. The proposed algorithms are based on metaherísticas ILS and VNS and incorporates these operators. We have performed computational experiments by applying these algorithms to solve real instances of a database we have taken from these schools. The results have shown that local search algorithms using our operators are more efficient than algorithms using the literature operator. Furthermore, we have observed that ILS and VNS algorithms using combinations of local search heuristics based in our operators have produced the best results and these results are satisfactory to the problem.