10.3. The Timetabling Problem
Problem 3: In a
school, there are m teachers and n classes
. Given that teacher
is required to teach class
for
periods. Schedule a complete timetable in the
minimum possible number of periods.
We have, at least, the assumption that in any one period each teacher can teach at most one class, and each class can be taught by at most one teacher.
The corresponding
graph model: we represent the teaching requirements by a bipartite graph G
with bipartition , where
and vertices
are joined by edges.
In this model a teaching schedule for one period corresponds to a matching in the bipartite graph and, conversely, each matching corresponds to a possible assignement of teachers to classes for one period.
Therefore, our problem is to partition the edges of G into as few matching as possible or, equivalently, to properly colour the edges of G with as few colurs as possible.
Since G is
bipartite, we know, that .
Case A.:
If no teacher teaches for more than p periods, and if no class is taught for more than p periods, the teaching requirements can be scheduled in a p-period timetable.
Since we need to solve a matching problem, there is a good algorithm for constructing such a timetable.
Case B :
if only a limited number of classrooms are available then how many periods are needed to schedule a complete timetable?
Suppose that altogether there are l lessons to be given, and that they have been scheduled in a p-period timetable.
Since this
timetable requires an average of lessons to be given in each period, so at
least
rooms will be needed in some period.
It turns out that one
always arrange l lessons in a p-period timetable so that at most rooms
are occupied in any one period.
This is the consequence of the following lemma:
Lemma 10.8.: Let M and N be disjoint
matchings of G with . Then
there are disjoint matchings
of G such that
and
.
Proof.
Consider the graph . Then each component of H is either an even
cycle with edges alternately in M and N, or else a path with
edges alternately in M and N. Since
, some path
component P of H must start and end with edges of M. (See
Theorem 9.3.)
Let , and set
Then M' and N' are matchings of G that satisfy the conditions of the lemma.
Theorem 10.9.: If G is bipartite, and if , then
there exist p disjoint matchings
of G such that
and for 1 ≤ i ≤ p
Proof.
First we note that
the last inequalities say that any two matchings differ in size
by at most one.
Let G be a
bipartite graph. Then the edges of G can be partitioned into matchings.
Therefore, for any , there exist p disjoint matchings
(with
) such that
By repeatedly applying Lemma 10.8 to
pairs of these matchings that differ in size by more than one, we eventually
obtain p disjoint matchings of G satisfying
and
, as
required.
Let us consider the following example: suppose there are four teachers and five classes, and the teaching requirement matrix is given.


One possible 4-period timetable may be given as the following:

We can represent this timetable by a decomposition into matchings of the edge set of the bipartite graph G coresponding to P.

From the timetable we see that four classes are taught in period 1, and so, four rooms are needed.
However, and so, by Theorem 10.9, a 4-period time-table can be arranged
so that in each period either 2
or 3
classes are taught.
Let be the matching
with the blue lines and
the matching
with the green lines.
Now, we can find a 4-period 3-room
timetable by considering .

has two components, each consisting of a path
of length three. Both paths start and end with blue edges and so, by
interchanging the matchings on one of the two paths, we shall reduce the blue
matching to one of three edges, and the same time increase the green matching
to one of three edges.

This gives the revised timetable where only three rooms are needed at any time:

We note, that in practice, most problems on timetabling are complicated by certain preassignements (that is, conditions specifying the periods during which some of teachers and classes must meet).