Abstract
There is a perception that teaching space in universities is a rather scarce resource. However, some studies have revealed that in many institutions it is actually chronically under-used. Often, rooms are occupied only half the time, and even when in use they are often only half full. This is usually measured by the ‘utilization’ which is defined as the percentage of available ‘seat-hours’ that are employed. Within real institutions, studies have shown that this utilization can often take values as low as 20–40%. One consequence of such a low level of utilization is that space managers are under pressure to make more efficient use of the available teaching space. However, better management is hampered because there does not appear to be a good understanding within space management (near-term planning) of why this happens. This is accompanied, within space planning (long-term planning) by a lack of experise on how best to accommodate the expected low utilizations. This motivates our two main goals: (i) To understand the factors that drive down utilizations, (ii) To set up methods to provide better space planning. Here, we provide quantitative evidence that constraints arising from timetabling and location requirements easily have the potential to explain the low utilizations seen in reality. Furthermore, on considering the decision question ‘Can this given set of courses all be allocated in the available teaching space?’ we find that the answer depends on the associated utilization in a way that exhibits threshold behaviour: There is a sharp division between regions in which the answer is ‘almost always yes’ and those of ‘almost always no’. Through analysis and understanding of the space of potential solutions, our work suggests that better use of space within universities will come about through an understanding of the effects of timetabling constraints and when it is statistically likely that it will be possible for a set of courses to be allocated to a particular space. The results presented here provide a firm foundation for university managers to take decisions on how space should be managed and planned for more effectively. Our multi-criteria approach and new methodology together provide new insight into the interaction between the course timetabling problem and the crucial issue of space planning.
Similar content being viewed by others
References
Avella P and Vasil'ev I (2005). A computational study of a cutting plane algorithm for university course timetabling. J Schedul 8: 497–514.
Bardadym VA (1996). Computer-aided school and university timetabling: The new wave. In: Burke E.K. and Trick M.A. (eds). Selected Papers from the First International Conference on the Theory and Practice of Automated Timetabling (PATAT 95): Lecture Notes in Computer Science Vol. 1153. Springer-Verlag: New York, pp. 22–45.
Beyrouthy C, Burke EK, Landa-Silva D, McCollum B, McMullan P and Parkes AJ (2006a). The teaching space allocation problem with splitting. In: Burke EK and Rudova H (eds). Proceedings of the Sixth International Conference on the Practice and Theory of Automated Timetabling (PATAT 2006). To appear in selected proceedings in Lecture Notes in Computer Science. Springer-Verlag: New York..
Beyrouthy C, Burke EK, Landa-Silva D, McCollum B, McMullan P and Parkes AJ . (2006b). Understanding the role of UFOs within space exploitation. In: Burke EK and Rudova H (eds). Proceedings of the Sixth International Conference on the Practice and Theory of Automated Timetabling (PATAT 2006). Masaryk University: Czech Republic, pp 359–362..
Bollobas B (1985). Random Graphs. Academic Press: London, England.
Bosch R and Trick M (2005). Integer programming. In: Burke E.K. and Kendall G. (eds). Search Methodologies: Introductory Tutorial in Optimization and Decision Support Techniques. Springer-Verlag: New York, pp. 69–95 Chapter 3.
Burke EK and Petrovic S (2002). Recent research directions in automated timetabling. Eur J Opl Res 140: 180–266.
Burke EK, Bykov Y, Newall J and Petrovic S (2003). A time-predefined approach to course timetabling. Yugoslav J Opns Res 13: 139–151.
Carter MW and Laporte G (1998). Recent developments in practical course timetabling. In: Burke E.K. and Ross P. (eds). Selected Papers from the Second International Conference on Practice and Theory of Automated Timetabling (PATAT 97): Lecture Notes in Computer Science Vol. 1408. Springer-Verlag: New York, pp. 3–19.
Carter MW and Tovey CA (1992). When is the classroom assignment problem hard? Opns Res 40: 28–39.
Cheeseman P, Kanefsky B and Taylor WM (1991). Where the really hard problems are. In: Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, IJCAI-91. San Mateo, Kaufmann, CA, Morgan: Los Altos, CA, pp. 331–337.
Chiarandini M, Birattari M, Socha K and Rossi-Doria O (2006). An effective hybrid algorithm for university course timetabling. J Scheduling 9: 403–432.
Cordeau J-F, Jaumard B and Morales R (March 2003) Efficient timetabling solution with tabu search. http://www.idsia.ch/Files/ttcomp2002/jaumard.pdf, accessed July 2007.
Cormen TH, Leiserson CE, Rivest RL and Stein C (2001). Introduction to Algorithms, 2nd edn. MIT Press, Cambridge, MA and McGraw-Hill: New York.
de Werra D (1985). An introduction to timetabling. Eur J Opl Res 19: 151–162.
Deb K (2005). Multi-objective optimization. In: Burke E.K. and Kendall G. (eds). Search Methodologies Introductory: Tutorial in Optimization and Decision Support Techniques. Springer: New York, pp. 273–316 Chapter 10.
Di Gaspero L and Schaerf A (2004). A multineighbourhood local search solver for the timetabling competition TTComp-2002. In: Selected papers from the Fifth International Conference for the Practice and Theory of Automated Timetabling (PATAT 2004). Lecture Notes in Computer Science, Springer-Verlag: New York, pp 262–275..
Dueck G (1993). New optimization heuristics: The great deluge algorithm and the record-to-record travel. J Comput Phys 104: 89–92.
Fizzano P and Swanson S (2000). Scheduling classes on a college campus. Comput Optim Appl 16: 279–294.
Gandibleux X, Morita H and Katoh N (2001). The supported solutions used as a genetic information in a population heuristics. In: Zitzler E., Deb K., Thiele L., Coello C.A.C. and Corne D. (eds). Proceedings of the 1st International Conference on Evolutionary Multi-criterion Optimization (EMO 2001): Lecture Notes in Computer Science Vol. 1993. Springer: London, pp. 429–442.
HEFCE (1999). Estates management statistics project. Technical Report 99/18, Higher Education Funding Council for England, http://www.hefce.ac.uk/pubs/hefce/1999/99_18.htm accessed July 2007.
Huberman BA and Hogg T (1987). Phase transitions in artificial intelligence systems. Artif Intell 33: 155–171.
Kirkpatrick S, Gelatt CD and Vecchi MP (1983). Optimization by simulated annealing. Science 220: 671–680.
Kostuch P (2004). The university course timetabling problem with a three-phase approach. In: Burke E.K. and Trick M.A. (eds). Selected Papers from the Fifth International Conference on Practice and Theory of Automated Timetabling (PATAT 2004): Lecture Notes in Computer Science. Springer-Verlag: New York, pp. 109–125.
Landa-Silva JD (November 2003) Metaheuristics and multiobjective approaches for space allocation. PhD thesis, School of Computer Science and Information technology, University of Nottingham..
McCollum B and McMullan P (2004). The cornerstone of effective management and planning of space. Technical report, Realtime Solutions Ltd, Belfast. http://www.realtimesolutions-uk.com/SpaceManagment.doc, accessed July 2007.
McCollum B and Roche T (2004). Scenarios for allocation of space. Technical report, Realtime Solutions Ltd, Belfast.
Metaheuristics Network (2003). International timetable competition 2002. http://www.idsia.ch/Files/ttcomp2002/, Organised by the Meta-heuristics network, http://www.metaheuristics.net/ and PATAT 2002 http://www.asap.cs.nott.ac.uk/patat/patat02/patat02.shtml, accessed 2 July 2007.
Mitchell DG, Selman B and Levesque HJ (1992). Hard and easy distributions for SAT problems. In: Rosenbloom P. and Szolovits P. (eds). Proceedings of the Tenth National Conference on Artificial Intelligence. AAAI Press: MenloPark, California, pp. 459–465.
Nemhauser GL and Wolsey LA (1988). Integer Programming and Combinatorial Optimization. John Wiley & Sons: New York, NY.
Parkes AJ (2002). Scaling properties of pure random walk on random 3-sat. In: CP '02: Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming: Lecture Notes In Computer Science Vol. 2470. Springer-Verlag: New York, pp. 708–713.
Petrovic S and Burke E (2004). University timetabling. In: Leung J.Y.-T. (ed). Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman Hall/CRC Press: Boca Raton, FL, Chapter 45.
Ritzman L, Bradford J and Jacobs R (1979). A multiple objective approach to space planning for academic facilities. Mngt Sci 25: 895–906.
Ross P and Corne D (1996). The phase transition niche for evolutionary algorithms in timetabling. In: Burke E.K. and Trick M.A. (eds). Selected Papers from the First International Conference on the Theory and Practice of Automated Timetabling (PATAT 95): Lecture Notes in Computer Science Vol. 1153. Springer-Verlag: New York, pp. 309–324.
Rossi-Doria O, Samples M, Birattari M, Chiarandini M, Dorigo M, Gambardella L, Knowles J, Manfrin M, Mastrolilli M, Paechter B, Paquete L and Stützle T (2003). A comparison of the performance of different metaheuristics on the timetabling problem. In: Burke E.K. and Causmaecker P. (eds). Selected Papers from the Fourth International Conference on Practice and Theory of Automated Timetabling (PATAT 2002): Lecture Notes in Computer Science Vol. 2740. Springer-Verlag: New York, pp. 329–351.
Schaerf A (1999). A Survey of automated timetabling. Artif Intell Rev 13: 87–127.
Steuer RE (1986). Multiple Criteria Optimization: Theory, Computation and Application. John Wiley: New York.
Tuyttens D, Teghem J, Fortemps P and Nieuwenhuyze KV (2000). Performance of the MOSA method for the bicriteria assignment problem. J Heuristics 6: 295–310.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Beyrouthy, C., Burke, E., Landa-Silva, D. et al. Towards improving the utilization of university teaching space. J Oper Res Soc 60, 130–143 (2009). https://doi.org/10.1057/palgrave.jors.2602523
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/palgrave.jors.2602523