|
Abstracts
Constributed Talks
A Genetic Algorithm for University Weekly Courses Timetabling
E. Yu, K.S. Sung, Department of Industrial Engineering,
Kangnung National University, Korea
In this paper, we describe a heavily constrained university timetabling problem (TTP),
and our genetic algorithm (GA) to solve it. TTP is known to be a constraint satisfaction
problem (CSP) and it is NP-complete. We give a new way of problem- specific chromosome
representation and operators of GA for TTP. Penalty method is introduced. At the end of
the paper, we discuss the possibility of its extensions.
A Column-Generation Approach for School Timetabling Problems
P. Eveborn, Division of Optimization, M. Roennqvist, Department of Mathematics, Linkoeping University, Linkoeping, Sweden
Timetabling in Swedish upper secondary schools is a complex task due to the many aspects
it has to take in to account. We describe a solution approach based on a set partitioning
formulation, combined with column generation. This model enables qualitative aspects of a
timetable.
A Review of Recent Developments in Practical Course Timetabling
M. Carter, G. Laporte, University of Toronto Mechanical & Industrial
Engineering, Toronto, Ontario, Canada
Course timetabling is a multi-dimensional NP-Complete problem that has generated
hundreds of papers, and thousands of students have attempted to solve it for
their own school. In this paper, we describe the major components of course
timetabling, some of the main types of algorithms that have been used, and provide
a survey of the major commercial packages that are available. We have not performed a
quantitative comparison. We hope that the results will be useful to future
researchers.
|
