Developing a course timetable system for academic departments using genetic algorithm

الملخص EN

Preparing course timetables for universities is a search problem with many constraints.

Exhaustive search techniques in theory can be used to develop course timetables for academic departments, but unfortunately these techniques are computation intensive, since the search space is very large and therefore are impractical.

In this paper, Genetic Algorithms (GA’s) are utilized to build an automated course timetable system.

The system is designed for any academic department.

The proposed timetabling system requires minimal effort from the administration staff to prepare the course timetable.

Moreover, the prepared course timetable considers faculties’ desires, students' needs and available resources, such as classrooms and laboratories with optimal utilization.

The proposed timetabling process was divided into three stages.

The first stage is the data collection stage.

In this stage, the administrative staff; usually the head of the department, is responsible for preparing the required data, such as the names of the faculty personnel and their desires of courses and laboratories ordered with some priority scheme.

Number and type of theoretical and practical courses are also fed to the system based on some statistics about student numbers and previous course timetable history.

The system is also fed with number of lecture rooms allocated for the department and number of labs with information about theoretical courses they are able to serve.

In the second stage, the program generates an initial set of suggested schedules (chromosomes).

Each chromosome represents a solution to the problem, but usually is not satisfactory.

Finally, the proposed timetabling system starts the search for a good solution that satisfies best interests of the department according to a cost function.

GA is applied in search for a satisfactory course timetable based on a pre-defined criterion.

The system has been developed and tested utilizing benchmarked datasets developed by an international timetabling competition (ITC2007) and for the Computer Engineering Department at Yarmouk University.

In both cases, the algorithm showed very satisfactory results.