## 2 Problem Description  
The examination timetabling problem (ETP) is an optimization problem, whose goal is to assign a set of examinations to a set of time slots in a way that a set of constraints are satisfied. The constraints are categorized as hard for the ones that should be satisfied in order for a timetable solution to be feasible and legal and soft for the ones for which when satisfied, the solution becomes better in terms of quality. Two versions of the ETP problem exist, the capacitated and the uncapacitated one. In the capacitated version, the room capacity is taken into account, while in the uncapacitated, it is not. In this paper, the Carter/Toronto datasets are used as benchmarks to evaluate the proposed algorithm. For these datasets, there exists essentially one hard constraint that has to do with the fact that a student cannot sit in two or more examinations at the same time. The main soft constraint involves the spreading of the examinations in the whole examination period in order to facilitate the preparation of the students. The Carter/Toronto benchmark Version I problems are summarized in Table 1.  
A formal description of the problem follows. Let \(E\) be a set of examinations assuming values one to \(|E|\) and \(P\) a set of periods assuming values one to \(|P|\). Binary variables \(x_{ip}\) are defined over each \(i\in E\) and \(p\in P\) assuming value one if exam \(i\) is scheduled to period \(p\) or zero otherwise. Let \(S\) be the total number of students, \(N_{ij}\) be the number of students that examinations \(i\) and \(j\) have in common and \(w\) a weight vector that assumes values \(w=\{16,\ 8,\ 4,\ 2,\ 1,\ 0\}\). Each of the \(w\)'s values corresponds to a distance between two examination periods. When the distance between two examinations is only one \begin{table}
\begin{tabular}{l c c c c} \hline \hline
**Dataset** & **Examinations** & **Students** & **Periods** & **Conflict Density** \\ \hline car-f-92 I & 543 & 18,419 & 32 & 0.14 \\ car-s-91 I & 682 & 16,925 & 35 & 0.13 \\ ear-f-83 I & 190 & 1125 & 24 & 0.27 \\ hec-s-92 I & 81 & 2823 & 18 & 0.42 \\ kfu-s-93 I & 461 & 5349 & 20 & 0.06 \\ lse-f-91 I & 381 & 2726 & 18 & 0.06 \\ pur-s-93 I & 2419 & 30,032 & 42 & 0.03 \\ rye-s-93 I & 486 & 11,483 & 23 & 0.07 \\ sta-f-83 I & 139 & 611 & 13 & 0.14 \\ tre-s-92 I & 261 & 4360 & 23 & 0.18 \\ uta-s-92 I & 622 & 21,266 & 35 & 0.13 \\ \multicolumn{1}{l}{ute-s-92 I} & 184 & 2749 & 10 & 0.08 \\ \multicolumn{1}{l}{yor-f-83 I} & 181 & 941 & 21 & 0.29 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Toronto examination timetabling problem (ETP) datasets. time slot, the value of \(w\) is 16, and as the distance increases, the value of \(w\) decreases. Equation (1) is the objective function that should be minimized. Constraint Equation (2) ensures that each exam will be assigned to exactly one period. Constraint Equation (3) assigns to variables \(e_{i}\) the number value of the period to which examination \(i\) is scheduled. Constraint Equation (4) ensures that no two examinations having students in common will be scheduled to the same period. In this constraint, \(M\) is a very large number and \(|e_{i}-e_{j}|\) is the distance between the time slots to which examinations \(i\) and \(j\) are scheduled. \[minimize\qquad\frac{1}{S}\sum_{i=1}^{|E|}\sum_{j=i+1}^{|E|}w(|e_{i}-e_{j}|)N_{ij} \tag{1}\]  
s.t. \[\sum_{p=1}^{|P|}x_{ip}=1\qquad(i:1..|E|) \tag{2}\]  
\[e_{i}=\sum_{p=1}^{|P|}x_{ip}p\qquad(i:1..|E|) \tag{3}\]  
\[(M+|e_{i}-e_{j}|)N_{ij}>=(M+1)N_{ij}\qquad(i,j:1..|E|) \tag{4}\]  
For this problem, a conflict matrix that shows the percentage of examinations with common students among the various examinations and, in effect, models the computational complexity of the problem is also defined. The (\(E\times E\)) conflict matrix, with the examinations being both on its rows and columns, has the value \"1\" at the intersections of pairs of examinations with common students between them.