Geodesic
A Time-Predefined Approach to Course Timetabling
Yugoslav journal of operations research, Tome 13 (2003) no. 2, p. 139 .

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

A common weakness of local search metaheuristics, such as Simulated Annealing, in solving combinatorial optimization problems, is the necessity of setting a certain number of parameters. This tends to generate a significant increase in the total amount of time required to solve the problem and often requires a high level of experience from the user. This paper is motivated by the goal of overcoming this drawback by employing "parameter-free" techniques in the context of automatically solving course timetabling problems. We employ local search techniques with "straightforward" parameters, i.e. ones that an inexperienced user can easily understand. In particular, we present an extended variant of the "Great Deluge" algorithm, which requires only two parameters (which can be interpreted as search time and an estimation of the required level of solution quality). These parameters affect the performance of the algorithm so that a longer search provides a better result - as long as we can intelligently stop the approach from converging too early. Hence, a user can choose a balance between processing time and the quality of the solution. The proposed method has been tested on a range of university course timetabling problems and the results were evaluated within an International Timetabling Competition. The effectiveness of the proposed technique has been confirmed by a high level of quality of results. These results represented the third overall average rating among 21 participants and the best solutions on 8 of the 23 test problems.
Classification : 90B36
Keywords: Combinatorial optimization, metaheuristic, local search, timetabling. 
@article{YJOR_2003_13_2_a0,
     author = {Edmund Burke and Yuri Bykov and James Newall and Sanja Petrovi\'c},
     title = {A {Time-Predefined} {Approach} to {Course} {Timetabling}},
     journal = {Yugoslav journal of operations research},
     pages = {139 },
     publisher = {mathdoc},
     volume = {13},
     number = {2},
     year = {2003},
     zbl = {1055.90039},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2003_13_2_a0/}
}
TY  - JOUR
AU  - Edmund Burke
AU  - Yuri Bykov
AU  - James Newall
AU  - Sanja Petrović
TI  - A Time-Predefined Approach to Course Timetabling
JO  - Yugoslav journal of operations research
PY  - 2003
SP  - 139 
VL  - 13
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/YJOR_2003_13_2_a0/
LA  - en
ID  - YJOR_2003_13_2_a0
ER  - 
%0 Journal Article
%A Edmund Burke
%A Yuri Bykov
%A James Newall
%A Sanja Petrović
%T A Time-Predefined Approach to Course Timetabling
%J Yugoslav journal of operations research
%D 2003
%P 139 
%V 13
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/YJOR_2003_13_2_a0/
%G en
%F YJOR_2003_13_2_a0
Edmund Burke; Yuri Bykov; James Newall; Sanja Petrović. A Time-Predefined Approach to Course Timetabling. Yugoslav journal of operations research, Tome 13 (2003) no. 2, p. 139 . http://geodesic.mathdoc.fr/item/YJOR_2003_13_2_a0/