Solving the examination timetabling problem in GPUs
type: Item
instance of: scholarly article
title: Solving the examination timetabling problem in GPUs
zbMATH Open document ID: 1461.90179
author: Vasileios Kolonias
author: George Goulas
author: Christos Gogos
author: Panayiotis Alefragis
author: Efthymios Housos
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 7042208
zbMATH Keywords: evolutionary algorithms
zbMATH Keywords: examination timetabling problem
zbMATH Keywords: GPU computing
zbMATH Keywords: CUDA
describes a project that uses: EASEA
describes a project that uses: CUDA
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a7030295
OpenAlex ID: W2080574925
cites work: Q4821526
cites work: Q4225802
cites work: Handbook of metaheuristics
cites work: Q4692508
cites work: Q4079017
cites work: Setting the research agenda in automated timetabling: the second international timetabling competition
cites work: An improved multi-staged algorithmic process for~the~solution of the examination timetabling problem
cites work: A survey of search methodologies and automated system development for examination timetabling
cites work: An upper bound for the chromatic number of a graph and its application to timetabling problems
cites work: Solving examination timetabling problems through adaption of heuristic orderings
cites work: Constraint satisfaction problems: Algorithms and applications
cites work: Q2779804
cites work: Using tabu search with longer-term memory and relaxation to create examination timetables.
cites work: A robust simulated annealing based examination timetabling system.
cites work: Q2779807
cites work: A study of heuristic combinations for hyper-heuristic systems for the uncapacitated examination timetabling problem
cites work: Hybridizations within a graph-based hyper-heuristic framework for university timetabling problems
cites work: Parallel metaheuristics: recent advances and new trends
cites work: GPU Computing for Parallel Local Search Metaheuristic Algorithms
cites work: Cellular Genetic Algorithm on Graphic Processing Units
cites work: ECC2K-130 on NVIDIA GPUs
cites work: Investigating Ahuja-Orlin's large neighbourhood search approach for examination timetabling
DOI: 10.3390/A7030295
Recommended article: A study of scheduling problems with preemptions on multi-core computers with GPU accelerators
Recommended article: Analysis of a High-Performance TSP Solver on the GPU
Recommended article: Solving path problems on the GPU
description: scientific article; zbMATH DE number 7042208