A generalized class-teacher model for some timetabling problems

We consider a theoretical model which extends the basic "class-teacher model" of timetabling and which corresponds to some situations which occur frequently in the basic training programs of universities and schools. We are given m teachers T-1,..., T-m and n classes C-1,...,C-n. The set of classes is partitioned into p disjoint subsets G(1),...,G(p) in such a way that in addition to the lectures given by one teacher to one class, there are some lectures given by one teacher to the students of all classes in group G(i), 1 less than or equal to l less than or equal to p. Such lectures will be called group-lectures. The number a,, of one hour group-lectures which teacher T-j must deliver to group G(1) and the number b(ij) of one hour class-teaching which T-j must give to class C-i are given. Is there a timetable of t hours (or length t), so that each class C-i and each group G(1) receive all their lectures, but no student is scheduled to be taught by more than one teacher in each hour, and no teacher must teach to more than one group or class in each hour? We show that this problem is NP-complete and find some sufficient conditions for the existence of a timetable of length t. We also describe an algorithm for constructing a timetable corresponding to the requirement matrices A = (a(ij)) and B = (b(ij)) and show that under a natural assumption on A and B this algorithm finds a timetable within 7/6 of the optimum length. (C) 2002 Elsevier Science B.V. All rights reserved.