Minimal Perturbation Problem in Course Timetabling
| Authors | |
|---|---|
| Year of publication | 2005 |
| Type | Article in Proceedings |
| Conference | Practice and Theory of Automated Timetabling V |
| MU Faculty or unit | |
| 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: |