Conference Papers

A Shuffled Complex Evolution Based Algorithm for Examination Timetabling – Benchmarks and a New Problem Focusing Two Epochs

Abstract:
In this work we present a memetic algorithm for solving examination timetabling problems. Two problems are analysed and solved. The first one is the well-studied single-epoch problem. The second problem studied is an extension of the standard problem where two examination epochs are considered, with different durations. The proposed memetic algorithm inherits the population structure of the Shuffled Complex Evolution algorithm, where the population is organized into sets called complexes. These complexes are evolved independently and then shuffled in order to generate the next generation complexes. In order to explore new solutions, a crossover between two complex’s solutions is done. Then, a random solution selected from the top best solutions is improved, by applying a local search step where the Great Deluge algorithm is employed. Experimental evaluation was carried out on the public uncapacitated Toronto benchmarks (single epoch) and on the ISEL-DEETC department examination benchmark (two epochs). Experimental results show that the proposed algorithm is efficient and competitive on the Toronto benchmarks with other algorithms from the literature. Relating the ISEL-DEETC benchmark, the algorithm attains a lower cost when compared with the manual solution.
Impact factor:
URL:
http://dx.doi.org/10.5220/0005164801120124

In Proceedings of the International Conference on Evolutionary Computation Theory and Applications (ECTA-2014), pp. 112-124. SciTePress (2014),