Publication details

Minimal Perturbation Problem in Course Timetabling



Year of publication 2004
Type Article in Proceedings
Conference PATAT 2004 - Proceedings of the 5th international conference on the Practice And Theory of Automated Timetabling
MU Faculty or unit

Faculty of Informatics

Keywords dynamic problems; search algorithms; timetabling; constraint satisfaction; over-constrained 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. The 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 solution of an initial problem. 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. The methods proposed 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.

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

More info