Solving an Uncapacitated Exam Timetabling Problem Instance using a Hybrid NSGA-II

Nuno Leite, Rui Neves, Nuno Horta, Fernando Melício, Agostinho Rosa

2012

Abstract

This paper describes the construction of an university examination timetable using a hybrid multi-objective evolutionary algorithm. The problem instance that is considered is the timetable of the Electrical, Telecommunications and Computer Department at the Lisbon Polytechnic Institute, which comprises three bachelor degree programs and two master degree programs, having about 80 courses offered and 1200 students enrolled. The task of manually construct the exam timetable for this instance is a complex one due essentially to the high number of combined degree courses. This manual process takes, considering a two-person team, about one week long. A hybrid multi-objective evolutionary algorithm, based on the Non-dominated Sorting Genetic Algorithm-II (NSGA-II), is proposed for solving this problem instance, incorporating two distinct objectives: one concerning the minimization of the number of occurrences of students having to take exams in consecutive days, and a second one concerning the minimization of the timetable length. The computational results show that the automatic algorithm achieves better results compared to the manual solution, and in negligible time.

Paper Citation

in Harvard Style

Leite N., Neves R., Horta N., Melício F. and Rosa A. (2012). Solving an Uncapacitated Exam Timetabling Problem Instance using a Hybrid NSGA-II . In Proceedings of the 4th International Joint Conference on Computational Intelligence - Volume 1: ECTA, (IJCCI 2012) ISBN 978-989-8565-33-4, pages 106-115. DOI: 10.5220/0004166001060115

in Bibtex Style

@conference{ecta12,
author={Nuno Leite and Rui Neves and Nuno Horta and Fernando Melício and Agostinho Rosa},
title={Solving an Uncapacitated Exam Timetabling Problem Instance using a Hybrid NSGA-II},
booktitle={Proceedings of the 4th International Joint Conference on Computational Intelligence - Volume 1: ECTA, (IJCCI 2012)},
year={2012},
pages={106-115},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004166001060115},
isbn={978-989-8565-33-4},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 4th International Joint Conference on Computational Intelligence - Volume 1: ECTA, (IJCCI 2012)
TI - Solving an Uncapacitated Exam Timetabling Problem Instance using a Hybrid NSGA-II
SN - 978-989-8565-33-4
AU - Leite N.
AU - Neves R.
AU - Horta N.
AU - Melício F.
AU - Rosa A.
PY - 2012
SP - 106
EP - 115
DO - 10.5220/0004166001060115