Robust university course timetabling problem subject to single and multiple disruptions

Ayla Gülcü and Can Akkan

European Journal of Operational Research, 2020, vol. 283, issue 2, 630-646

Abstract: University course timetables are often finalized in stages, in between which, changes in the data make the earlier version infeasible. As each version is announced to the community, it is desirable to have a robust initial timetable, i.e. one that can be repaired with limited number of changes and yielding a new solution whose quality is degraded as little as possible. We define two versions of the robust timetabling problem, first one assuming that only one lecture is disrupted (its scheduled period ceasing to be feasible) and the second one assuming multiple lectures are disrupted. The objective of the algorithms is to identify a good Pareto front defined by the solution quality (penalty associated with soft-constraint violations) and the robustness measure. Two versions of a multi-objective simulated annealing (MOSA) algorithm is developed (MOSA-SD and MOSA-SAA, for single and multiple disruptions, respectively), with the difference being in the way robustness of a solution is estimated within the MOSA algorithm. Extensive computational experiments done using the International Timetabling Competition ITC-2007 data set confirm that MOSA-SD outperforms a genetic algorithm from the literature, and MOSA-SAA outperforms MOSA-SD when there are multiple disruptions. For MOSA-SAA an innovative solution network to structure feasible solutions for a set of disruption scenarios has been developed to efficiently perform sample average approximation (SAA) calculations, which can be adopted for other stochastic combinatorial optimization problems.

Keywords: Timetabling; Robustness; Bi-criteria optimization; Simulated Annealing; Stochastic combinatorial optimization (search for similar items in EconPapers)
Date: 2020
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/S037722171930935X
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:ejores:v:283:y:2020:i:2:p:630-646

DOI: 10.1016/j.ejor.2019.11.024

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().