Bi-criteria simulated annealing for the curriculum-based course timetabling problem with robustness approximation

Can Akkan (), Ayla Gülcü () and Zeki Kuş ()
Additional contact information
Can Akkan: Sabancı University
Ayla Gülcü: Bahçeşehir University
Zeki Kuş: Fatih Sultan Mehmet University

Journal of Scheduling, 2022, vol. 25, issue 4, No 6, 477-501

Abstract: Abstract In the process of developing a university’s weekly course timetable, changes in the data, such as the available time periods of professors or rooms, render the timetable infeasible, requiring the administrators to repair or update the timetable. Since such changes almost always occur, it would be a sensible approach to identify a robust initial timetable, that is, one that can be repaired by making a limited number of changes, while still maintaining a high solution quality. This article formulates the problem as a bi-criteria optimization one, in which robustness is a stochastic objective, and the goal is to identify a good approximation to the Pareto frontier. It is assumed that multiple data changes, or disruptions, of multiple types can occur. The solution approach is a multi-objective simulated annealing (MOSA) algorithm, where a surrogate measure is used to approximate the robustness objective. Inspired by the concept of slack in machine and project scheduling, ten alternative measures of slack and a total of thirty surrogate measures are defined. Preliminary computational experiments are used to narrow the list of promising ones first to eight and then to two measures, which are then tested within a MOSA algorithm. Computational experiments show that one of these measures, when implemented in a multi-start MOSA algorithm, consistently provides the best Pareto frontier.

Keywords: Course timetabling; Simulated annealing; Robustness; Fitness approximation (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00722-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jsched:v:25:y:2022:i:4:d:10.1007_s10951-022-00722-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-022-00722-0

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().