University Course Scheduling Using Parallel Multi-Objective Evolutionary Algorithms

Abstract

Evolutionary Algorithm (EA) provides a mechanism that can achieve efficient exploration for design spaces. Thus, it constitutes an efficient tool for identifying the best alternatives to implement the solution of a certain problem. In this work, EA is implemented to solve the university course scheduling problem and a real data from Palestine Polytechnic University (PPU) databases is used for testing. Sequential implementation of such a complex problem will suffer a long execution time to find sub-optimal solution. On the other hand, using single objective optimization model soft and hard constraints could not be well satisfied. In this work, we have implemented the EA using parallel programming techniques. This permits the execution of the program in a cluster computer to reduce the execution time. Also, many soft constraints can be considered along with the hard constraints in order to get better solutions. Results show that, after redrafting the algorithm to be multi-objective, soft cost could be reduced to the minimum when using enough individuals and iterations, at the same time, hard constraints are still satisfied. After distributing the algorithm on 7 machines with 11 processors the obtained speedup is around 6 on average and the quality of the obtained solution has improved considerably.