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.
|Title of host publication||Practice and Theory of Automated Timetabling (Proceedings 3rd International Conference, PATAT 2000, Konstanz, Germany, August 16-18, 2001)|
|Editors||E. Burke, W. Erben|
|Place of Publication||Berlin|
|Publication status||Published - 2001|
|Name||Lecture Notes in Computer Science|