When Is the Classroom Assignment Problem Hard?

Michael W. Carter and Craig A. Tovey
Additional contact information
Michael W. Carter: University of Toronto, Toronto, Ontario, Canada
Craig A. Tovey: Georgia Institute of Technology, Atlanta, Georgia

Operations Research, 1992, vol. 40, issue 1-supplement-1, S28-S39

Abstract: The classroom assignment (or hotel room or interval scheduling) problem is to assign classes, which meet at different time intervals, to rooms. Two classes may not meet simultaneously in the same room, nor may a class meet in two different rooms. Thousands of colleges and secondary schools face this problem every semester. There has been some confusion as to how hard this problem is. Many colleges claim that it is easy, while others complain that it is next to impossible. In the literature, some authors claim or conjecture polynomial time algorithms, while others develop heuristic approaches. The goal of this paper is to resolve the confusion by identifying cases where the problem will be easy and others where it will be hard. We focus on the kinds of cases that schedulers are apt to encounter in practice.

Keywords: education systems; operation: classroom assignment; course timetabling; mathematics: computational complexity; production/scheduling: applications (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.1.S28 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:40:y:1992:i:1-supplement-1:p:s28-s39

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().