Minimal Perturbation Problem in Course Timetabling

MÜLLER, Tomáš and 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, p. 283-303, 20 pp. ISBN 0-88748-413-1.

Basic information

• Original name: Minimal Perturbation Problem in Course Timetabling
• Name in Czech: Problém minimálních změn v univerzitním rozvrhování
• Authors: MÜLLER, Tomáš and Hana RUDOVÁ.
• Edition: Pittsburgh, PATAT 2004 - Proceedings of the 5th international conference on the Practice And Theory of Automated Timetabling, p. 283-303, 20 pp. 2004.

Other information

• Type of outcome: Proceedings paper
• Confidentiality degree: is not subject to a state or trade secret
• WWW: URL
• Organization unit: Faculty of Informatics
• ISBN: 0-88748-413-1
• UT WoS: 000234857300008
• Keywords in English: dynamic problems; search algorithms; timetabling; constraint satisfaction; over-constrained problems
• Tags: constraint satisfaction, dynamic problems, over-constrained problems, search algorithms, timetabling

Abstract

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.

Abstract (in Czech)

Ř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.