Graduate Project

A laboratory station timetable problem

Public Deposited

Downloadable Content

Download PDF


Attribute NameValues
  • The general problem of classroom scheduling is well known to be NP-complete. A typical classroom scheduling problem is that of assigning students to a limited number of pieces of laboratory equipment. Frequently several identical pieces of equipment are available only at fixed hours and have limited access due to physical constraints. In instances where resources are scarce it may be necessary to pack students as tightly as possible into a minimum set of hours so that there is total equipment usage, i.e., an exact fit. The problem being considered here is that of assigning pairs of students to two labs per week during a minimum set of available hours such that the assignment achieves an exact fit and maximizes overall compatibility between pairs of students and their outside commitments. The assumptions are that there is an exact fit possible and the problem specification provides the minimum set of available hours along with the constraints on pairing students and hours. It will be shown that in general this assignment problem is NP-complete; however, if certain restrictions are placed on the minimum set of hours available there are polynomial bounded algorithms which have a good chance of finding an acceptable assignment.
Resource Type
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Committee Member
Academic Affiliation
Rights Statement
Peer Reviewed



This work has no parents.