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

Nuno Leite, Fernando Melício, Agostinho C. Rosa

2014

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.

Paper Citation

in Harvard Style

Leite N., Melício F. and Rosa A. (2014). A Shuffled Complex Evolution Based Algorithm for Examination Timetabling - Benchmarks and a New Problem Focusing Two Epochs . In Proceedings of the International Conference on Evolutionary Computation Theory and Applications - Volume 1: ECTA, (IJCCI 2014) ISBN 978-989-758-052-9, pages 112-124. DOI: 10.5220/0005164801120124

in Bibtex Style

@conference{ecta14,
author={Nuno Leite and Fernando Melício and Agostinho C. Rosa},
title={A Shuffled Complex Evolution Based Algorithm for Examination Timetabling - Benchmarks and a New Problem Focusing Two Epochs},
booktitle={Proceedings of the International Conference on Evolutionary Computation Theory and Applications - Volume 1: ECTA, (IJCCI 2014)},
year={2014},
pages={112-124},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005164801120124},
isbn={978-989-758-052-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Evolutionary Computation Theory and Applications - Volume 1: ECTA, (IJCCI 2014)
TI - A Shuffled Complex Evolution Based Algorithm for Examination Timetabling - Benchmarks and a New Problem Focusing Two Epochs
SN - 978-989-758-052-9
AU - Leite N.
AU - Melício F.
AU - Rosa A.
PY - 2014
SP - 112
EP - 124
DO - 10.5220/0005164801120124