Minimum penalty perturbation heuristics for curriculum-based timetables subject to multiple disruptions

Akkan, Can and Gülcü, Ayla and Kuş, Zeki (2021) Minimum penalty perturbation heuristics for curriculum-based timetables subject to multiple disruptions. Computers and Operations Research, 132 . ISSN 0305-0548 (Print) 1873-765X (Online)

[thumbnail of Article] PDF (Article)
Akkan_etal_COR_2021.pdf
Restricted to Registered users only

Download (708kB) | Request a copy

Abstract

Course timetables are often rendered infeasible due to unexpected changes in requirements and must be repaired. Given an initial timetable, planners prefer a repaired timetable whose quality is worsened as little as possible while its structural difference is also as little as possible. This paper formulates this problem as one of minimizing the quality degradation subject to an upper limit on the structural difference and presents one simulated annealing algorithm and a set of integer programming-based algorithms to solve it. These algorithms are tested on instances comprised of the ITC-2007 curriculum-based course timetabling test-bed and a set of randomly generated disruption scenarios, where each disruption scenario is based on a set of four disruption types that affect teacher and room availability. The results are analyzed with respect to two main goals, one being repairing a timetable after a single disruption scenario, and the other being the calculation of an estimated robustness of a solution based on a sample of disruption scenarios.
Item Type: Article
Uncontrolled Keywords: course timetabling, perturbation, simulated annealing, integer programming, robustness
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
Divisions: Sabancı Business School
Sabancı Business School > Operations Management and Information Systems
Depositing User: Can Akkan
Date Deposited: 02 Sep 2021 01:19
Last Modified: 02 Sep 2021 01:19
URI: https://research.sabanciuniv.edu/id/eprint/41652

Actions (login required)

View Item
View Item