Minimal Perturbation Problem in Course Timetabling

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

MULLER Tomáš RUDOVÁ Hana BARTÁK Roman

Year of publication 2005
Type Article in Proceedings
Conference Practice and Theory of Automated Timetabling V
MU Faculty or unit

Faculty of Informatics

Citation
Web http://dx.doi.org/10.1007/11593577_8
Field Informatics
Keywords scheduling; timetabling; local search; constructive search; dynamic problems
Description Many real-life problems are dynamic, with changes in the problem definition occurring after a solution to the initial formulation has been reached. A minimal perturbation problem incorporates these changes, along with the initial solution, as a new problem whose solution must be as close as possible to the initial solution. A new iterative forward search algorithm is proposed to solve minimal perturbation problems. Significant improvements to the solution quality are achieved by including new conflict-based statistics in this algorithm. The proposed methods were applied to find a new solution to an existing large scale class timetabling problem at Purdue University, incorporating the initial solution and additional input changes.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.