2005
Minimal Perturbation Problem in Course Timetabling
MULLER, Tomáš, Hana RUDOVÁ a Roman BARTÁKZákladní údaje
Originální název
Minimal Perturbation Problem in Course Timetabling
Název česky
Problém minimálních změn při rozvrhování předmětu
Autoři
MULLER, Tomáš (203 Česká republika), Hana RUDOVÁ (203 Česká republika, garant) a Roman BARTÁK (203 Česká republika)
Vydání
Heidelberg, Practice and Theory of Automated Timetabling V, od s. 126-146, 21 s. 2005
Nakladatel
Springer-Verlag GmbH
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Spojené státy
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Kód RIV
RIV/00216224:14330/05:00014771
Organizační jednotka
Fakulta informatiky
ISBN
978-3-540-30705-1
UT WoS
000234857300008
Klíčová slova anglicky
scheduling; timetabling; local search; constructive search; dynamic problems
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 28. 3. 2010 20:56, doc. Mgr. Hana Rudová, Ph.D.
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. 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.
Česky
Řada reálných problemu je dynamická a dochází ke změnám problému. Cílem řešení problému minimálních změn je nalézt takové řešení nového problému, aby bylo reflektováno řešení puvodního problému i změny v definici problému. Práce navrhuje nový algoritmus iterativního dopředného prohledávání, který umožňuje významná zlepšení kvality řešení toho problému. Navržené metody byly prověřeny řešením rozsáhlého rozvrhovacího problému na Purdue university.
Návaznosti
MSM0021622419, záměr |
|