Minimal Perturbation Problem in Course Timetabling

MÜLLER, Tomáš a Hana RUDOVÁ. Minimal Perturbation Problem in Course Timetabling. Online. 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. [citováno 2024-04-23]

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í
• WWW: 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

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.

Anotace č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.