| |
|
Detailed schedule
Click on a link for more details
Show all the abstracts
Show all the abstracts
Thursday 11:00:00 Timetabling in education and sport
Room 126 - Chair: G. Vanden Berghe
- Educational timetabling, an overview of a mature research domain
Peter Demeester (KaHo Sint-Lieven)
Co-authors: G. Vanden Berghe, P. De Causmaecker
- Educational course timetabling: a case study
Herman Crauwels (campus De Nayer, Hogeschool voor Wetenschap & Kunst)
- A hyper-heuristics approach to solve a real-world and a benchmark examination timetabling problem
Peter Demeester (KaHo Sint-Lieven)
Abstract:
In this abstract we tackle two examination timetabling problems, which we both solve with the same hyper-heuristics approach. In contrast to meta-heuristics, in which the search is executed on the space of solutions, hyper-heuristics operate on a search space of heuristics.
The idea behind hyper-heuristics, is that the selection of low-level heuristics is automated, for example by applying machine learning techniques.
In general, low-level heuristics can be built so that each of them can individually solve one specific part of the problem.
Hyper-heuristics can exploit the particular properties of each low-level heuristics by combining them in a specific order.
A typical hyper-heuristics framework consists of some heuristic selection mechanism and a set of low-level heuristics.
These low-level heuristics can be either perturbative (changing only small parts of the solution) or constructive (constructing a solution).
In our case, the heuristic selection mechanism is `simple random', meaning that a low-level heuristic from a list of perturbative heuristics is randomly selected.
As acceptance criteria we experiment with four meta-heuristics: simulated annealing, great deluge, steepest descent, and late acceptance strategy.
The hyper-heuristics framework is first applied to a real-world examination timetabling problem at the School of Engineering of KaHo Sint-Lieven.
In contrast to the solution obtained by the manual planner, we could reduce the number of weekly time slots from twelve to ten, satisfying all hard and soft constraints.
In order to compare the hyper-heuristic's performance with the state-of-the-art, we also applied it to the data sets of the examination timetabling track of the 2007 International Timetabling Competition (ITC 2007). The goal of the examination track of the ITC 2007 was to provide more realistic data sets that could be used as test beds for algorithms.
The hard and soft constraints of the ITC 2007 examination timetabling track are quite similar to those of KaHo Sint-Lieven, except that at KaHo there is a clean distinction between oral and written exams.
The ITC 2007 problem definition on the other hand incorporates some constraints that are not present in the KaHo Sint-Lieven problem.
For example, it demands that large exams should be scheduled in the beginning of the examination period, and that some of the time slots and rooms should preferably be avoided.
Because of these extra constraints, we introduced additional low-level heuristics, which are particularly constructed to tackle these constraints.
We obtain with this general approach, which was originally developed for tackling a real-world problem, results that are competitive with those obtained during the competition.
- The carry-over effect does not exist in football
Dries Goossens (Katholieke Universiteit Leuven)
Co-authors: F.C.R. Spieksma
Thursday 11:00:00 Transportation management
Room 130 - Chair: F. Semet
Thursday 11:00:00 Networks
Room 138 - Chair: B. Fortz
Thursday 11:00:00 Nonconvex optimization 1
Room 035 - Chair: F. Bach
Thursday 14:00:00 Constraint programming models 1
Room 126 - Chair: Y. Deville
Thursday 14:00:00 Vehicle routing
Room 130 - Chair: S. Limbourg
Thursday 14:00:00 Combinatorial optimization and IP applications
Room 138 - Chair: Q. Louveaux
Thursday 14:00:00 Nonconvex Optimization 2
Room 035 - Chair: R. Sepulchre
Thursday 16:10:00 Constraint programming models 2
Room 126 - Chair: P. Schaus
Thursday 16:10:00 Performance modeling
Room 130 - Chair: G. Janssens
Thursday 16:10:00 Scheduling
Room 138 - Chair: K. Sorensen
Thursday 16:10:00 Planning under uncertainty
Room 035 - Chair: R. Leus
Friday 09:00:00 Metaheuristics
Room 126 - Chair: J. Teghem
Friday 09:25:00 Production and distribution (9:25)
Room 130 - Chair: Y. Arda
Friday 09:00:00 Multiple criteria
Room 138 - Chair: R. Bisdorff
Friday 09:25:00 Stochastic models (9:25)
Room 035 - Chair: L. Esch
Friday 11:00:00 Constraint programming and Supply Chain Management
Room 126 - Chair: Y. Deville
Friday 11:00:00 OR in health management
Room 130 - Chair: P. De Causmaecker
Friday 11:00:00 Rankings and importance indices
Room 138 - Chair: JL. Marichal
Friday 11:00:00 Queueing
Room 035 - Chair: S. Wittevrongel
Friday 15:10:00 Optimization software
Room 126 - Chair: E. Loute
Friday 15:10:00 Integrated operations planning
Room 130 - Chair: B. Raa
Friday 15:10:00 Cycles in graphs
Room 138 - Chair: F. Spieksma
|
|
