Minimal Perturbation Problem in Course Timetabling

MÜLLER, Tomáš a Hana RUDOVÁ. Minimal Perturbation Problem in Course Timetabling. In PATAT 2004 - Proceedings of the 5th international conference on the Practice And Theory of Automated Timetabling. Pittsburgh, 2004, s. 283-303, 20 s. ISBN 0-88748-413-1.

Základní údaje

Originální název

Minimal Perturbation Problem in Course Timetabling

Název česky

Problém minimálních změn v univerzitním rozvrhování

Autoři

MÜLLER, Tomáš a Hana RUDOVÁ

Vydání

Pittsburgh, PATAT 2004 - Proceedings of the 5th international conference on the Practice And Theory of Automated Timetabling, od s. 283-303, 20 s. 2004

---

Další údaje

Typ výsledku

Stať ve sborníku

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Organizační jednotka

Fakulta informatiky

ISBN

0-88748-413-1

UT WoS

000234857300008

Klíčová slova anglicky

dynamic problems; search algorithms; timetabling; constraint satisfaction; over-constrained problems

Štítky

constraint satisfaction, dynamic problems, over-constrained problems, search algorithms, timetabling

---

Anotace

V originále

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.

Česky

Řada reálných problémů má dynamický chrakter, dochází ke změnám definice problému po té, co bylo nalezeno řešení původního problému. Problém minimálních změn uvažuje tyto změny společně s původním řešením jako nový problém, jehož řešení musí být co nejbližší původnímu. Práce navrhuje nový iterativní dopředný prohledávací algoritmus pro řešení problému minimálních změn. Výrazné zlepšení kvality řešení je dosaženo prostředníctvím nové konfliktní statistiky. Navržené metody byly aplikovány pro řešení rozsáhlého rozvrhovacího problému na Purdue University, a to jak pro řešení původního problému tak i nového problému se vstupními změnami.