Room usage optimization in timetabling: A case study at Universidade de Lisboa

Alexandre Lemos, Francisco S. Melo, Pedro T. Monteiro and Inês Lynce

Operations Research Perspectives, 2019, vol. 6, issue C

Abstract: This paper discusses the problem of room usage optimization for university timetables: given a timetable, we want to optimize the room occupation by determining the events allocated to each room, while ensuring that the rooms have enough capacity to “seat” all people participating in those events. This paper contributes with two approaches to the problem of optimizing the timetable scheduled for each room. The first approach consists of a two-stage Integer Linear Programming (ILP) which applies a lexicographic optimization wherein the goal of the first stage is to maximize the number of students seated and that of the second stage is to optimize the room occupation. This is provably optimal, in both optimization criteria. However, it is computationally demanding, requiring significant computation time for large problems. To address this issue, we propose a second approach, consisting of a greedy algorithm. The algorithm assigns lectures to rooms greedily, according to a specific cost function that seeks to maximize the number of students seated. We show that the proposed cost function guarantees that the greedy algorithm performs within 63% of the total number of students. We apply both algorithms in a case study involving real data from Instituto Superior Técnico (IST), the engineering school from Universidade de Lisboa. Our results confirm that the greedy algorithm is two orders of magnitude faster than ILP when considering large data sets. Comparing the performance of the two methods we observe that the performance of the greedy algorithm, when compared to the ILP-based approach, is within 2% for the number of seated students and 34% for the room occupation. The GRASP algorithm is a good extension of the greedy algorithm, which is able to improve in 12% the quality of the solution (in terms of compactness) without adding significant CPU time. Overall, the two proposed approaches provide significant gains for both optimization criteria when compared to the current hand-made solutions.

Keywords: University timetabling; Room usage optimization; Integer linear programming; Greedy algorithms (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S2214716018301696
Full text for ScienceDirect subscribers only

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:eee:oprepe:v:6:y:2019:i:c:s2214716018301696

DOI: 10.1016/j.orp.2018.100092

Access Statistics for this article

Operations Research Perspectives is currently edited by Rubén Ruiz Garcia

More articles in Operations Research Perspectives from Elsevier
Bibliographic data for series maintained by Catherine Liu ().