The focus of our work is on the problem of generating a timetable using a parallel evolutionary algorithm. We explore commonly used scheduling methods and determine their suitability for cases with complex constraints, then select a parallelization scheme most suitable for efficient computation. Furthermore, we choose a data representation that best complements genetic operators and the fitness function, which covers a wide range of complex constraints. We implement and parallelize an extensible algorithm for computing solutions to our problem. A method of minimizing the space complexity of the problem by efficiently dividing data between processes is also described. We analyse the properties of our solution through a thorough analysis of run times and memory consumptions coupled with a theoretical analysis of the results.
|
