Detailed Information on Publication Record
2005
Minimal Perturbation Problem in Course Timetabling
MULLER, Tomáš, Hana RUDOVÁ and Roman BARTÁKBasic information
Original name
Minimal Perturbation Problem in Course Timetabling
Name in Czech
Problém minimálních změn při rozvrhování předmětu
Authors
MULLER, Tomáš (203 Czech Republic), Hana RUDOVÁ (203 Czech Republic, guarantor) and Roman BARTÁK (203 Czech Republic)
Edition
Heidelberg, Practice and Theory of Automated Timetabling V, p. 126-146, 21 pp. 2005
Publisher
Springer-Verlag GmbH
Other information
Language
English
Type of outcome
Stať ve sborníku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
United States of America
Confidentiality degree
není předmětem státního či obchodního tajemství
References:
RIV identification code
RIV/00216224:14330/05:00014771
Organization unit
Faculty of Informatics
ISBN
978-3-540-30705-1
UT WoS
000234857300008
Keywords in English
scheduling; timetabling; local search; constructive search; dynamic problems
Tags
International impact, Reviewed
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.
In Czech
Ř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.
Links
| MSM0021622419, plan (intention) |
|