Preparing courses timetable for university is a search problem with many constraints. Traditionally, exhaustive search techniques applied to develop courses timetable for academic departments. These techniques consume long time and therefore impractical. In this paper, this problem was tackled using non-traditional technique, particularly utilizing Genetic Algorithms (GAs). An automated system for preparing courses timetable for different semesters in a typical university department using GA has been developed. The proposed scheduling system requires minimal effort from the administration staff to prepare the courses timetable .Moreover, the prepared courses timetable considers faculties desires, student's needs, and manages the resources available such as classrooms and laboratories with optimal utilization.
The proposed scheduling system was developed based on genetic algorithm. The cost function was defined to optimize the generated schedule toward all scheduling parameters such as faculties desire, students needs and department resources. The proposed scheduling process was divided into three stages. The first stage is a 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 classes and laboratories ordered with some priority scheme, the offered courses, the number of sections for each course, the laboratories, and the lecture rooms and their types. The administrative staff feeds the collected data to the proposed automated scheduling system. 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 optimal. Finally, the proposed scheduling system starts the search for the best solution. This stage applies crossover and mutation approaches of the genetic algorithm expecting that new better chromosomes will be generated. Including the new set of solution, the system will repeat the mutation and crossover until it reaches an acceptable near optimal solution according to pre-defined satisfaction criteria.
Key words: Courses timetable problem, course timetable generation, Genetic Algorithm, Chromosome generation, Parents selection algorithm.
|