| Full text | |
| Author(s): |
Total Authors: 2
|
| Affiliation: | [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
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | APPLIED SOFT COMPUTING; v. 60, p. 363-373, NOV 2017. |
| Web of Science Citations: | 4 |
| Abstract | |
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) | |
| FAPESP's process: | 13/13563-3 - Heuristic methods for school timetabling problems |
| Grantee: | Landir Saviniec |
| Support Opportunities: | Scholarships in Brazil - Doctorate |