Effective local search algorithms for high school timetabling problems

Autor(es)

Saviniec, Landir ^[1] ; Constantino, Ademir Aparecido ^[2]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Inst Ciencias Matemat & Comp, Ave Trabalhador Sao Carlense 400, BR-13566590 Sao Carlos, SP - Brazil

^[2] Univ Estadual Maringa, Dept Informat, Ave Colombo 5790, BR-87020900 Maringa, Parana - Brazil

• Tipo de documento: Artigo Científico
• Fonte: APPLIED SOFT COMPUTING; v. 60, p. 363-373, NOV 2017.
• Citações Web of Science: 4

Resumo

This paper addresses the high school timetabling problem. The problem consists in building weekly timetables for meetings between classes and teachers with the goal of minimizing violations of specific requirements. In the last decades, several mixed-integer programs have been proposed and tested for this family of problems. However, medium and large size instances are still not effectively solved by these programs using state-of-the-art solvers and the scientific community has given special attention to the devising of alternative soft computing algorithms. In this paper, we propose a soft computing approach based on Iterated Local Search and Variable Neighborhood Search metaheuristic frameworks. Our algorithms incorporate new neighborhood structures and local search routines to perform an effective search. We validated the proposed algorithms on variants of the problem using seven public instances and a new dataset with 34 real-world instances including large cases. The results demonstrate that the proposed algorithms outperform the state-of-the-art approaches in both cases, finding the best solutions in 38 out of the 41 tested instances. (C) 2017 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 13/13563-3 - Algoritmos heurísticos para problemas de definição de horários escolares
• Beneficiário: Landir Saviniec
• Modalidade de apoio: Bolsas no Brasil - Doutorado