A GRASP strategy for a more constrained school timetabling problem

DOI10.1504/IJOR.2010.030801MaRDI QIDQ961453zbMATH OpenOpenAlexFDO

Authors Arnaldo Vieira Moura, Rafael Augusto Scaraficci

Publication date 30 March 2010

Published in International Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1504/ijor.2010.030801

zbMATH Keywords

Brazilcombinatorial optimisationGRASPgreedy randomized adaptive search procedurelocal searchmetaheuristicspath-relinkingschedulingschool timetabling problemSTP

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Review text

Summary: This work treats a more constrained School Timetabling Problem (STP). It consists of scheduling a set of lectures and teachers in a prefixed period of time, satisfying a set of operational requirements. We applied a Greedy Randomized Adaptive Search Procedure (GRASP) heuristic, combined with a path-relinking improvement. During execution of the GRASP heuristic, the local search procedure interleaves two types of movements. In addition, the path-relinking strategy was itself enhanced by a local search procedure. The algorithms were tested with real instances and proved to be good approaches to solve this problem. Although some restrictions are specific to Brazilian educational institutions, the same ideas can inspire similar approaches for solving the STP in other situations.

Recommendations

• School timetabling problem
• Constructing Good Solutions for the Spanish School Timetabling Problem
• Constraint programming approach for school timetabling.
• Towards constraint-based school timetabling
• A Tabu search heuristic with efficient diversification strategies for the class/teacher timetabling problem

Cited in

(9)

• Integer programming techniques for educational timetabling
• A stochastic local search algorithm with adaptive acceptance for high-school timetabling
• Investigation of data regularization and optimization of timetables by Lithuanian high schools example
• Late acceptance hill-climbing for high school timetabling
• Operational research in education
• Mathematical models and algorithms for a high school timetabling problem
• A survey of school timetabling research
• School timetabling problem
• An assignment problem and its application in education domain: a review and potential path

This page was built for publication: A GRASP strategy for a more constrained school timetabling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q961453)