Solving the examination timetabling problem in GPUs
Main Author: | Κολώνιας, Βασίλειος |
---|---|
Other Authors: |
Γούλας, Γεώργιος Γκόγκος, Χρήστος Αλεφραγκής, Παναγιώτης Χούσος, Ευθύμιος |
Format: | Article |
Language: | English |
Published: |
MDPI
2014
|
Subjects: | |
Online Access: |
http://cris.teiep.gr/jspui/handle/123456789/1307 |
Physical Description: |
σελ. 295-327 |
---|---|
ISSN: |
1999-4893 |
Abstract: |
The examination timetabling problem belongs to the class of combinatorial
optimization problems and is of great importance for every University. In this paper, a
hybrid evolutionary algorithm running on a GPU is employed to solve the examination
timetabling problem. The hybrid evolutionary algorithm proposed has a genetic algorithm
component and a greedy steepest descent component. The GPU computational capabilities
allow the use of very large population sizes, leading to a more thorough exploration of the
problem solution space. The GPU implementation, depending on the size of the problem, is
up to twenty six times faster than the identical single-threaded CPU implementation of the
algorithm. The algorithm is evaluated with the well known Toronto datasets and compares
well with the best results found in the bibliography. Moreover, the selection of the encoding
of the chromosomes and the tournament selection size as the population grows are examined
and optimized. The compressed sparse row format is used for the conflict matrix and was
proven essential to the process, since most of the datasets have a small conflict density, which
translates into an extremely sparse matrix. |