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

24 Citations (Scopus)
3 Downloads (Pure)

Abstract

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
PublisherSpringer
Pages18-27
ISBN (Print)3-540-42421-0
DOIs
Publication statusPublished - 2001

Publication series

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

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

Cite this