Linear binary integer models for a timetabling problem of The Faculty of Law - University of Copenhagen

Specialeforsvar ved Rebecca Anna Helt

Titel: Linear binary integer models for a timetabling problem of The Faculty of Law - University of Copenhagen

Abstract: This thesis deals with a Curriculum-based University Course Timetabling problem of The Faculty of Law. The problem is formulated as a linear binary integer programming problem and is constructed on the basis of hard and soft constraints. Three formulations of the problem are created. Two are equivalent and the third is a relaxation of the others. Due to the large amount of data provided by The Faculty of Law, the problem is divided into four separate problems, one for each semester. None of the formulations are, however, able to solve the problems with the original data, so the data is reduced in two different ways. The first method makes the problems less flexible by fixing some of the connections between courses, teachers and classrooms and the second method nearly halves the number of time slots in the timetable by defining the time slots to consist of two hours instead of one hour, without loss of flexibility. The formulations that are able to solve the problems are expanded to include two more preferences to retrieve better timetables. These are preferences of avoiding teaching sessions late in the afternoon and of gathering student groups of the same course in the same time slots. Furthermore, an algorithm to create an initial solution has been made, with the purpose of reducing the solution time. Timetables for all four semesters have been made that fulfils the desired rules, but it was not possible to obtain timetables when inflicting the additional preferences

  

Vejleder: Trine Krogh Boomsma
Censor:   Niklas Kohl, CBS