Complexity of some special types of timetabling problems (Q1600003)

Starting from the simple class-teacher model of timetabling (where timetables correspond to edge colorings of a bipartite multigraph), the authors consider an extension defined as follows: it is assumed that the set of classes is partitioned into groups. In addition to the teachers giving lectures to individual classes, we have a collection of teachers who give all their lectures to groups of classes. The authors show that when there is one such teacher giving lectures to three groups of classes, the problem is NP-complete. It is also examined the case where there are at most two groups of classes and a polynomial procedure based on network flows to find a timetable using at most \(t\) periods, is given.