A Bi-criteria Hybrid Genetic Algorithm with Robustness Objective for the Course Timetabling Problem

Abstract

Traditional methods of generating timetables may yield high-quality solutions, but they may not yield robust solutions that may easily be adapted to changing inputs. Incorporating late changes by making minimum modifications on the final timetable is an important need in many practical applications of timetabling. In this study, we focus on a subset of course timetabling problems, the curriculum-based timetabling problem. We first define a robustness measure for the problem, and then try to find a set of good solutions in terms of both penalty and robustness values. We model the problem as a bi-criteria optimization problem and solve it by a hybrid Multi-objective Genetic Algorithm, which makes use of Hill Climbing and Simulated Annealing algorithms in addition to the standard Genetic Algorithm approach. The algorithm is tested on the well known ITC-2007 instances and shown to identify high quality Pareto fronts.