Mathematical programming formulations for optimization of university course timetabling problem: the case mkwawa University of Collage of Education

This dissertation describes University Course Timetabling Problem (UCTP) used at Mkwawa University College of Education (MUCE). University Course Timetabling is the Problem of scheduling resources such as lectures, courses and rooms to a number of timeslots over a planning horizon, normally a week, while satisfying a number of problem-specific constraints (Mushi A.R,2011). UCTP is one of the classes of Combinatorial Optimization Problems (CoPs) which is NP- Hard; that is a class of Optimization whereby no optimal solution procedure is known to solve in a reasonable time. Currently MUCE timetabling scheduler creates course timetables manually depending on the experience of the scheduler. This has resulted into wastage of time and resources (especially time and spaces). Our major interest is to design techniques for the automatic generation of timetables. In this study, we have developed three models for UCTP at MUCE. The models have been described and implemented using real data from MUCE. The results obtained were tested using GLPK solver and comparative analysis on the performances of the models was carried out basing on the solutions obtained. It is concluded that, reformulations of mathematical programming models can improve performance on exact methods. It has been possible to get optimal solution for the MUCE course timetabling problem through a model which involves a mixture of binary and time-indexed variables.