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.

The corresponding bipartite graph is:

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 3classes 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).