Some complexity aspects of secondary school timetabling problems

H.M.M. Eikelder, ten, R.J. Willemen

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

25 Citations (Scopus)
3 Downloads (Pure)


We consider timetabling problems of secondary schools, in which the students can choose their own curricula. Besides finding a time slot and classroom assignment, every student must be assigned to a subject group for each subject in his curriculum. This problem is NP-hard for several independent reasons. In this paper we investigate the borderline between "easy" and "hard" subproblems. In particular, we show that the addition of blocks of size two,i.e. two lessons to be taught at consecutive time slots,or the addition of a constraint on the subject group size changes a subproblem from polynomially solvable to NP-hard.
Original languageEnglish
Title of host publicationPractice and Theory of Automated Timetabling (Proceedings 3rd International Conference, PATAT 2000, Konstanz, Germany, August 16-18, 2001)
EditorsE. Burke, W. Erben
Place of PublicationBerlin
ISBN (Print)3-540-42421-0
Publication statusPublished - 2001

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Some complexity aspects of secondary school timetabling problems'. Together they form a unique fingerprint.

Cite this