## 5 Methodology
### Initial Construction of Solutions
As can be seen from the above equations, we chose to split the work into two blocks of threads for all of the big datasets containing more than 512 examinations, and not only for the _pur-s-93_ dataset. In order to achieve better performance, the weight factor \(w\) and the array used to calculate the total cost of a chromosome \(lcost\) are placed in the shared memory. Given that the data in the shared memory have the lifetime of a block and the threads of each block cannot access the data in the shared memory of another block, in the datasets with a number of examinations greater than 512, an atomic operation is needed to calculate the total cost of one chromosome. One thread (the first) of each of the needed blocks in the x-axis adds the result of the total sum of its block to the corresponding position of the costs array in the global memory, in order to get the total cost of the whole chromosome. The pseudocode for the examination-threaded approach is given in Algorithm 3. #### 5.3.1 Weight Factor

The weight cost factor to produce examination spreading is related to the distance between two examinations in the timetable. Due to the fact that the conditional on \(distance>6\) to use a \(w=0\) can be a problem with CUDA, since conditional statements decrease performance, \(w\) is transformed to a vector of a size equal to the number of available time slots, padded with zeros. Furthermore, in order to heavily penalize conflicts and very tight schedules, a value \(M\) (a very large value) was selected for exam conflicts. Therefore, \(w\) takes the following form:

\[w=\{40,000,\ 16,\ 8,\ 4,\ 2,\ 1,\ 0,\ 0,\ldots,\ 0\}\]

#### 5.3.2 Exploiting Sparsity

As shown in Table 1, the conflict matrix is sparse. Thus, in this work, apart from the full conflict matrix, the compressed sparse row (CSR) format is also used (Figure 3). In CSR, the sparse matrix becomes a vector of rows, \(R\). Each row \(R_{i}\) is a vector of pairs, one for each non-zero element. Each pair contains the non-zero column index and the element value:

\[R_{i}=\{(j,C_{i,j}):\forall j:e_{j}\in E,C_{i,j}\
eq 0\}\]

In a pre-processing stage, the compressed conflict matrix is calculated in two different forms. One form represents the full conflict matrix, where each examination is associated with each other examination in conflict. The CSR format is equivalent to the adjacency matrix for the conflict graph between the examinations. The other form, more useful for this work, is the diagonal conflict matrix. For every examination \(i\), the diagonal conflict matrix row \(R_{Di}\) contains only conflicts with examinations indexed with \(j\geq i+1\). \[R_{Di}=\{(j,C_{i,j}):\forall j:e_{j}\in E,j>i,C_{i,j}\
eq 0\}\]

This way, the \(O(|E|^{2})\) complexity for the full evaluator is reduced to \(O(|E|^{2}C^{D}))\), where \(C^{D}<1\) is the conflict density. The CSR evaluators exploit the sparse features of the conflict matrix. ### Selection and Reproduction

The next step of the algorithm is the selection of the parents that will form two new children, according to their cost. The tournament selection with a size 3% of the population size and the one-point crossover operator were selected. During the experiments that were done, it was observed that the tournament selection size is of great importance for the performance of the algorithm. For small population sizes, the size of the tournament selection can be small, as well, but as the population size increases, a small tournament selection size does not allow the algorithm to improve the solutions. Thus, the tournament selection size needs to be increased for bigger populations, but this comes with a cost in execution time, and therefore, a balance should be found. After many runs, we ended up in this fraction of the population size. The two parallelization approaches were implemented for this stage, as well. In the chromosome-threaded approach, each thread selects two chromosomes as parents, according to their costs, and forms two new chromosomes for the next generation.