## 1 Introduction  
Optimization is the process of finding the best solution from a set of available alternatives, taking into account all of the required problem constraints [1]. A single objective optimization problem consists of finding the minimum or the maximum value of an objective function that measures the quality of each solution. The variables of optimization problems can be either continuous or discrete. Optimization problems with discrete variables are also called combinatorial optimization problems [1], and the examination timetabling problem (ETP) that is solved in this work belongs to this class of problems. There are many techniques and algorithmic strategies that are used to solve difficult combinatorial optimization problems, but none of them manages to solve efficiently all of the categories of optimization problems, as [PERSON] and [PERSON] [2] proved. Mathematical programming [3], artificial intelligence [4] and meta-heuristic techniques [5] are some of the algorithmic families for the solution of these problems. The class of evolutionary algorithms (EA) [6; 7; 8], which is used in this paper, is based on Darwinian theory [9] and is usually included in the computational intelligence family. The examination timetabling problem (ETP) is a problem of great importance for every University, as it implicitly affects the performance of students in examinations. The goal is to assign a set of examinations to a set of time slots in a way such that a set of constraints are satisfied. Some constraints are hard and should not be violated, as a student should not have to sit for two exams at the same time, while others are soft, and violating them results in a bad solution. Practical aspects of the ETP problem can be found in [10] alongside an approach of solving the problem carried out by our team in [11]. There is a rich literature on the ETP, including benchmark datasets, as the ones used in this work, proposed by [PERSON] [12], with a simplified version of the problem. Other known benchmarks available are the University of Nottingham benchmark data [13] and the University of Melbourne benchmark data [14]. Parallel computation has gained significant interest in recent years due to the fact that the computer clock speed cannot be increased anymore, due to the physical limitations of semiconductor technology [15]. In order to sustain the constant increase of processing power, manufacturers promoted the multicore and many-core architectures. Graphical processing units (GPUs) are powerful commodity computer components that include a large number of processing cores in order to provide better performance of computer graphics. However, given the available processing power, GPU processors attracted the interest of many researchers and scientists for generic computation, as well, leading to the introduction of the term, general purpose graphical processing units (GPGPUs). After NVIDIA introduced the Compute Unified Device Architecture (CUDA), a large number of scientific applications have been ported to GPUs with remarkable speedups [16; 17]. In this paper, a hybrid evolutionary algorithm (hEA) is presented that is designed to solve the ETP using a GPU. The computing power of the GPU gives the opportunity to explore better the solution space by using great population sizes. Emphasis is given to the encoding and the representation of the solution in order to take full advantage of the GPU architecture. Moreover, the compressed sparse row format is used for the conflict matrix to improve performance, while a greedy steepest descent algorithm component is employed to improve the quality of the solutions of the genetic algorithm in every generation. Furthermore, the significance of the size of the tournament selection as the population size grows is shown. In the next section, the problem description is stated. In Section 3, related work for the ETP problem is surveyed, while in Section 4, an introduction to the GPU architecture and the CUDA programming model is presented.