Publication details
Minimal Perturbation Problem in Course Timetabling
| Authors | |
|---|---|
| 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 | |
| Citation | |
| Web | http://www.fi.muni.cz/~hanka/publ/patat04.pdf |
| 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. |