Lagrangian relaxation approach to the classroom assignment problem

This paper describes one of the algorithms in a new timetabling and student registration system that was implemented at the University of Waterloo (Ontario, Canada) in May, 1987. We are given a set of class meetings that has already been assigned to specific days and time periods of the week, and a collection of available classrooms on campus. We must determine an acceptable assignment of classes to rooms based on a variety of factors that measure the desirability of a particular assignment. The problem is subdivided into two separate components. Given a function cij that represents the cost of assigning class i to room j, we present a heuristic algorithm based on a Lagrangian relaxation for solving the multiple period assignment problem [MPAP]. We then describe a cost function model that will be shown to reasonably reflect the general preference structure of the faculty and the administration. Computational results on 1400 courses at the University of Waterloo are discussed.