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 a previous work of Information Technology students, they have applied the EA to the university course scheduling problem and they have implemented the methodology on a real data from the College of Administrative Sciences and Informatics at Palestine Polytechnic University (PPU). Two major shortages were founded in their project: First, the relatively long execution time that takes the evolutionary algorithm to find the optimal solution. Second, the soft constraints were considered in the implementation, but were not well satisfied. In this project, we have implemented the EA using parallel programming techniques. This permits to execute the program in a cluster of machines, which in turns reduces the execution time. In addition, we have applied some soft constraints concurrently with the hard constraints in order to get better results by making the EA minimizing the soft cost without affecting the hard cost. Results show that, after redrafting the algorithm to be multi-objective, the soft cost will go to zero if we use enough individuals and iterations, at the same time the hard constraints are still satisfied. In addition, after distributing the algorithm on 7 machines with 11 processors the obtained speedup reaches 6 on average.