Late acceptance heuristics for university’s course timetabling problem: The Case of Mwenge University College of Education

Date

2012

Journal Title

Journal ISSN

Volume Title

Publisher

University of Dar es Salaam,

Abstract

The university course timetabling problem consists of allocating a number of courses to u limited Net of resources such as rooms* timeslots, set of lecturers and group of students in such a way as to satisfy predefined constraint*, The constraints can be divided into two groups: hard and soft, A timetable has to satisfy all hard constraints in order to be feasible and it should satisfy as much as possible all the soft constraints in order to be of good quality. The university timetabling problem is in class of NP-hard problems. This means that the amount of time and work required for solving this type of problems increases exponentially with the problem size. This makes these problems more difficult and time consuming. No optimal algorithm is currently known for such problems within reasonable time. Therefore, heuristic optimization techniques are used to solve them and produce near optimal feasible solutions instead of exact solutions. This study concerns with the survey on timetabling problems that was done at Mwenge University College of Education (MWUCE) in Tanzania. This problem is interesting because of the complexity of the course timetabling problems but most importantly due to the fact that nobody has ever done research on timetabling at MWUCE. Currently, timetable at MWUCE is developed manually which makes it difficult to fix all timetabling collisions. The late acceptance heuristics has been described and implemented using real data from MWUCE. This is one of recent techniques and it works by delaying acceptance of good solutions in anticipation of better results. The results obtained were tested and comparative analysis done with Simulated Annealing. It has been found that this heuristic technique give better efficient approach for solving the type of problem

Description

Available in print form, East Africana Collection, Dr. Wilbert Chagula Library, Class mark (THS EAF T57.84.M57)

Keywords

timetabling, courses, soft constraints, NP-hard problems

Citation

Marwa, Y M M (2012), Late acceptance heuristics for university’s course timetabling problem: The Case of Mwenge University College of Education, Master dissertation, University of Dar es Salaam. Dar es Salaam