A Mixed-Integer Linear Programming approach for university timetabling problem with the multi-section courses: an application for Hacettepe University Department of Business Administration

Abstract

University course timetabling is an NP-Complete problem type which becomes even more difficult due to the specific requirements of each university. In this study, it was aimed to solve a university course timetabling problem by using integer programming and to develop assignment models that can be easily adapted to similar problems. The models that we developed for the solution are based on the integer programming model of Daskalaki et al. [1]. In addition, the models were developed taking into account the fact that there was an availability of multi-section courses, the minimum overlap of elective courses, and the ability to divide courses into sessions in terms of effective use of the capacity. In this framework, two different models (model 1 and model 2) were developed. Whereas model 1 assumes that all courses are processed as a single session (If a course has 3 time periods per week, then it is taught as a single session), model 2 assumes courses can be assigned by divided into multiple sessions (If a course has 3 time periods per week, then it can be divided into 1+1+1 or 2+1 sessions.). In model 2, a structure in which the model itself could determine how to split the courses in the framework of predetermined options was developed. Both models were formulated in such a way as to maximize the satisfaction of the lecturers. Finally, a larger scale problem was derived from the first problem and the performance of these two models were compared for both problems. The results showed that the optimal solution was obtained within the specified constraints, and the solution time significantly increased with an increase in the size of the problem.