Solving University Timetabling Problems by Distributed Micro-Genetic Algorithm with Local Search

R. Yusof, T.C. San, M. Khalid (Malaysia), and O. Ono (Japan)

Keywords

Distributed MicroGenetic Algorithm, Timetabling Scheduling, MultiConstraints, Optimization.

Abstract

: Timetable scheduling is known to be a computationally NPhard problem. It is both time and resource consuming. There have been many attempts by many researchers to develop a reliable timetable scheduling software, however, many of these software have only been tested or applied on an experimental basis or on a small population of students with minimal constraints. The Faculty of Electrical Engineering of Universiti Teknologi Malaysia, Johor, Malaysia which has a student population of over 4,000 is perhaps among one of the largest electrical engineering faculties in the world. In this Faculty, there are many parallel lectures to cater for the large number of students with a variety of constraints such as multiple sections of different student numbers, multi-disciplinary subjects, limited classrooms and lecturer's constraints. In this paper, an enhanced micro-GA is proposed for timetable scheduling in the Faculty to overcome such perennial problems. The enhanced micro-GA algorithm is referred to as distributed micro-GA which has local search to speed up the scheduling process. Comparisons are made with simple GA methods such that a more optimal solution can be achieved. The results have shown that the proposed algorithm can be successfully implemented at the Faculty meeting a variety of constraints not achievable using manual methods.

Important Links:



Go Back