A Timetabling Problem in which Clashes are Inevitable

Three models—graph colouring, set partitioning and simulated annealing—are suggested, and the advantages and disadvantages of using each of these to find a satisfactory solution are discussed.

Abstract

AbstractAbstractThis paper is concerned with a university timetabling problem in which some clashes are unavoidable if the weekly lecture requirements are to be scheduled in the available time-slots. The solution needs to satisfy a number of different objectives. Most of these are achieved by imposing a series of constraints, and the problem is reduced to that of minimizing the single objective of student disappointment. Three models—graph colouring, set partitioning and simulated annealing—are suggested, and the advantages and disadvantages of using each of these to find a satisfactory solution are discussed.Keywords: heuristicsmulti-objectivenetworks and graphsoptimizationtimetabling