Publication details

Minimal Perturbation Problem in Course Timetabling

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.

More info