TAILIEUCHUNG - A time-predefined approach to course timetabling

A common weakness of local search metaheuristics, such as Simulated Annealing, in solving combinatorial optimisation problems, is the necessity of setting a certain number of parameters. 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. | Yugoslav Journal of Operations Research 13 (2003), Number 2, 139-151 A TIME-PREDEFINED APPROACH TO COURSE TIMETABLING* Edmund BURKE+, Yuri BYKOV+, James NEWALL‡, Sanja PETROVI]+ +Automated Scheduling and Planning Group School of Computer Science and Information Technology University of Nottingham, Nottingham, UK {ekb,yxb,sxp}@ ‡ EventMAP Limited, Belfast, N. Ireland Communicated by Byron Papathanassiou Abstract: A common weakness of local search metaheuristics, such as Simulated Annealing, in solving combinatorial optimisation 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, . 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 .

• Tự động hoá
• Combinatorial optimisation
• Local search
• Parameter free
• Course timetabling problems
• Straightforward parameters