A Bi-Criteria Simulated Annealing Algorithm for the Robust University Course Timetabling Problem Subject to Period-Unavailability Disruptions
Can Akkan
Ph.D.
Can Akkan is a professor of operations management and business analytics at Sabancı Business School, Sabancı University. He holds a Ph.D. degree in Operations Research from Cornell University, and a B.S. degree in Industrial Engineering from M.E.T.U. His research interests are mainly in applied combinatorial optimization; mostly on scheduling, timetabling and planning problems. He has publications in journals such as Computers & Operations Research, European Journal of Operational Research, International Journal of Production Research, and Journal of the Operational Research Society.
Abstract
A bi-criteria version of the curriculum-based course timetabling problem of ITC-2007 (International Timetabling Competition) is solved to identify an approximation to the optimal Pareto front. The two criteria are the penalty function as defined in ITC-2007 and a robustness function. Robustness is needed to deal with disruptions that occur in the form of a feasible period that is used by a course becoming infeasible for that course. In such situations, the timetable has to be updated, in essence re-optimized, while ensuring that the changes are not excessive. A timetable is said to be robust if, when disrupted, it can be re-optimized without significantly lowering its quality in terms of the objective function and keeping it relatively stable. We define a robustness function that takes into account both the solution quality and stability concerns. We define the problem with the possibility of multiple disruptions as a multi-objective stochastic combinatorial optimization (MOSCO) problem. We propose a Multi-objective Simulated Annealing (MOSA) algorithm that makes use of a Monte Carlo sampling approach to solve the problem. Performance of the algorithm is tested on the ITC-2007 instances.
Zoom
May 11, 2020 - 18:00
