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

Peter de Haan, Ronald Landman, Gerhard Post, Henri Ruizenaar

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

66 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationProceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling (PATAT)
EditorsE.K. Burke, H. Rudová
Place of PublicationBrno, The Czech Republic
PublisherFaculty of Informatics, Masaryk University
Pages423-425
Number of pages3
ISBN (Print)80-210-3726-1
Publication statusPublished - 2006
Event6th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2006 - Brno, Czech Republic
Duration: 30 Aug 20061 Sep 2006
Conference number: 6

Conference

Conference6th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2006
Abbreviated titlePATAT 2006
CountryCzech Republic
CityBrno
Period30/08/061/09/06

Fingerprint Dive into the research topics of 'A Four-phase Approach to a Timetabling Problem in Secondary Schools'. Together they form a unique fingerprint.

Cite this