Parallel local search algorithms for high school timetabling problems

摘要

Highlights?We design parallel metaheuristics for high school timetabling problems.?Several different metaheuristics are used as agents.?Features such as cooperation, intensification and diversification are analyzed.?Strong elitism and exchange of information among threads improve the search.?Our best algorithm outperforms existing state-of-the-art algorithms.AbstractHigh school timetabling consists in assigning meetings between classes and teachers, with the goal of minimizing the violation of specific soft requirements. This family of problems has been frequently considered in the literature, but few strategies employing parallelism have been proposed. In this exploratory study, we consider two different parallel frameworks and present a thorough co