Pattern-based models and a cooperative parallel metaheuristic for high school timetabling problems
Abstract: High school timetabling problems consist in building periodic timetables for class-teacher meetings considering compulsory and non-compulsory requisites. This family of problems has been widely studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the efficient obtention of optimal or near-optimal solutions is still a challenge for many problems of practical size. In this paper, we investigate mixed-integer programming formulations and a parallel metaheuristic based algorithm for solving high school timetabling problems with compactness and balancing requisites. We propose two pattern-based formulations and a solution algorithm that simultaneously exploits column generation and a team of metaheuristics to build and improve solutions. Extensive computational experiments conducted with real-world instances demonstrate that our formulations are competitive with the best existing high school timetabling formulations, while our parallel algorithm presents superior performance than state-of-the-art methods.
Keywords: Class-teacher timetabling, Parallel metaheuristics, Column Generation, Iterated local search.
Category 1: Integer Programming ((Mixed) Integer Linear Programming )
Category 2: Applications -- OR and Management Sciences (Scheduling )
Category 3: Optimization Software and Modeling Systems (Parallel Algorithms )
Citation: Unpublished, Nov/2018
Entry Submitted: 11/04/2018
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|