D 2005

Minimal Perturbation Problem in Course Timetabling

MULLER, Tomáš, Hana RUDOVÁ a Roman BARTÁK

Zá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.

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. 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
Název: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy