Review of Generation of Time Table Using Genetic Algorithm Implemented in Java

Abstract

An educational timetabling is a multi-dimensional and highly constrained problem. Making educational timetables manually often involves number of rounds of changes before they can be satisfied. In Fact such a process can be time consumings, and often the quality of the timetables is compromised due to pressure to release the TT on time. Automatic generation of timetables then seems to be an attractive to manual approach. But this approach is with problems. In reality, most timetabling problems are NP-complete and most professors and researchers are interested in developing efficient algorithms for solving the time table problem. In this, a college timetable problem formulation is introduced lowed by recent approaches for solving the problem. After that, a genetic algorithm (GA) is presented to efficiently and effectively solve the problem. The proposed GA has a malleable (flexible) representation that handles all the college timetables at once. It includes repair strategies to always guarantee the creation of a feasible timetable which satisfies constraints that must not be destroyed. The algorithm is implemented and applied to create timetables for the Arab Academy for Science and Technology (AAST) in Egypt and it shows promising results.

Keywords— Genetic Algorithm (GA), Time Table Problem (TTP), Non Polynomial Problem (NP-Problem), Chromosome, Fitness, Mutation, Crossover.