Scheduling Classes on a College Campus

We consider the problem of scheduling a set of classes to classrooms with the objective of minimizing the number of classrooms used. The major constraint that we must obey is that no two classes can be assigned to the same classroom at the same time on the same day of the week. We present an algorithm that produces a nearly optimal schedule for an arbitrary set of classes. The algorithm's first stage produces a packing of classes using a combination of a greedy algorithm and a non-bipartite matching and the second stage consists of a bipartite matching.