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 T1,...,Tm and n classes C1,...,Cn. The set of classes is partitioned into p disjoint subsets G1,...,Gp 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 Gl, 1 ≤ l ≤ p. Such lectures will be called group-lectures. The number alj of one hour group-lectures which teacher Tj must deliver to group Gl and the number bij of one hour class-teaching which Tj must give to class Ci are given. Is there a timetable of t hours (or length t), so that each class Ci and each group Gl 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=(alj) and B=(bij) and show that under a natural assumption on A and B this algorithm finds a timetable within 7/6 of the optimum length.
