TY - GEN

T1 - Some complexity aspects of secondary school timetabling problems

AU - Eikelder, ten, H.M.M.

AU - Willemen, R.J.

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

U2 - 10.1007/3-540-44629-X_2

DO - 10.1007/3-540-44629-X_2

M3 - Conference contribution

SN - 3-540-42421-0

T3 - Lecture Notes in Computer Science

SP - 18

EP - 27

BT - Practice and Theory of Automated Timetabling (Proceedings 3rd International Conference, PATAT 2000, Konstanz, Germany, August 16-18, 2001)

A2 - Burke, E.

A2 - Erben, W.

PB - Springer

CY - Berlin

ER -