A Four-phase Approach to a Timetabling Problem in Secondary Schools


Haan de, Peter and Landman, Ronald and Post, Gerhard and Ruizenaar, Henri (2006) A Four-phase Approach to a Timetabling Problem in Secondary Schools. In: 6th International Conference on the Practice and Theory of Automated Timetabling, 30 Aug - 01 Sept 2006, Brno, The Czech Republic.

Abstract:Timetabling problems are present in all types of schools. The research in this area is still very active; of the 19 selected contributions of PATAT 2004 ([1]), 12 are dedicated to Educational Timetabling. These problems can often be modeled by a graph coloring problem. Here the vertices represent the events (lessons, courses, exams) to be scheduled, the (vertex)colors the available timeslots, and the edges express incompatibilities between two events. Typically incompatibilities are caused by the effect that resources related to an event (teachers, students, rooms) can attend at most one event at the same time. Apart from the basic model of graph coloring, extra conditions are common. Typical conditions are (room) capacities, resource (room, teacher) availabilities, and precedence relations among events. The subject of our study is a High School Timetabling Problem as it is common in the Netherlands. Beforehand it is decided which teachers give which lessons. Hence the events are the lessons, and, in principle, the problem can be stated as a graph coloring problem with extra conditions on availability of resources (rooms, teachers). However there is an extra dimension: the quality of the constructed timetable. A feasible solution, though necessary, is absolutely not sufficient: we need to improve the feasible timetable to a schedule that is acceptable to use. The size of the graph involved, and the extra efforts to improve the quality are the main reasons for our 4-phase approach: we try to control the quality by a preprocessing phase, and a post-processing phase. In the preprocessing phase, we cluster events in so-called clusterschemes. These clustered events can be considered as the new events to be scheduled. In the second and third phase a feasible timetable is constructed. In the fourth phase a Tabu Search is used to improve the best schedule found. The developed approach is tested by using data from the Kottenpark, which is one of the locations of 'Het Stedelijk Lyceum' in Enschede, the Netherlands.
Item Type:Conference or Workshop Item
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/66687
Official URL:http://www.asap.cs.nott.ac.uk/patat/patat06/patat06-full-papers.shtml
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 237671