View source for Effective Local Search Algorithms for High School Timetabling Problems

by: '''Saviniec, L. and Constantino, A. A.'''

'''Highlights'''

- We propose Iterated Local Search and Variable Neighborhood Search based algorithms for high school timetabling problems.

- We devise two generic neighborhood operators that can be easily adapted to similar problems.

- The hybridization between these neighborhood operators improves hugely the effectiveness of local search procedures.

- The proposed algorithms outperform state-of-the-art approaches in two datasets tested for two variants of the problem.

- New instances collected from different Brazilian high schools are made available for next studies.

'''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.

'''Keywords'''

Class–teacher timetabling, Iterated Local Search, Variable Neighborhood Search, Minimum Cost Assignment Problem, Conflict graph

Link to material: http://www.sciencedirect.com/science/article/pii/S1568494617303903?via%3Dihub

[[Category: Transportation]]