## 4 Computational Results
Both algorithms presented in the current contribution, as well as the four algorithms mentioned in the previous paragraph, use the same formalism for modeling the timetabling problem and the same three performance criteria (teachers' teaching hours' distribution, lessons' hours' distribution and teachers' gaps) in order to evaluate their performance. Thus, we can perform a straightforward and fair comparison of their experimental results. The input instances selected in order to compare the performance of these algorithms is the well-established Beligiannis data set [6, 7], which has been used by all these algorithms in the respective contributions. In Table 2 the major characteristics of the input instances used in the experimental results are presented. The interested reader can find a thorough description of these instances in [19, 20]. The proposed PSO algorithm as well as the proposed AFS algorithm is by nature stochastic. As a result, different computational results may be obtained in different runs. So, in order to demonstrate their efficiency, in Table 3 we present not only the best but also the worst and the average fitness achieved together with the respective standard deviation. The average execution time as well as the respective standard deviation is presented, too. In Table 4 the best performance of both proposed algorithms is compared with the best timetables created by the evolutionary algorithm (EA) presented in [25], the simulated annealing (SA) algorithm presented in [19], the hybrid PSO algorithm presented in [20] and the genetic algorithm selection perturbative hyper-heuristic (GASPHH) presented in [26]. The reason why we decided to present and compare the best timetables constructed by the proposed algorithms is that in [19, 20, 25, 26] also the best timetables constructed are presented. Thus, in this way a fair comparison between all algorithms can be performed. Note that in order to compare two different timetables, we define one unit cost for any soft constraint violation among the three performance criteria (teachers' teaching hours' distribution, lessons' hours' distribution, and teachers' gaps) [26]. All values presented in Tables 3 and 4 are computed after executing 100 Monte Carlo runs. For both algorithms the average fitness achieved is very close to the best fitness. Additionally, the respective \begin{table}
\begin{tabular}{c c c c c c} \hline \multirow{2}{*}{**Instance**} & **Number of Classes** & **Number of Teachers** & **Number of Teachers** & **Number of** **Lotives** & **Number of Lotives** \\  & **Classes** & **Teachers** & **Hours** & **Involved** & **Co-** \\  & & & & **in Co-Teaching** & **Teachers** \\ \hline
1 & 11 & 34 & 385 & 9 & 36 \\
2 & 11 & 35 & 385 & 17 & 67 \\
3 & 6 & 19 & 210 & 0 & 0 \\
4 & 7 & 19 & 245 & 6 & 31 \\
5 & 6 & 18 & 184 & 0 & 0 \\
7 & 13 & 35 & 455 & 17 & 70 \\ \hline \end{tabular}
\end{table} 
Table 2: Major characteristics of the Beligiannis school timetabling data set. STD value is rather small. This demonstrates their efficiency and stability. Furthermore, the STD concerning the execution time of both algorithms is really small. This also demonstrates that both algorithms are very stable. In Table 4 the best results, which are the best results found until today for the respective instances, are written in bold. The proposed PSO algorithm appears to have the best performance among all other algorithms achieving the best results ever found for 5/6 instances of the Beligiannis data set. The proposed AFS algorithm has also very satisfactory performance, since it surmounts the heuristic algorithms presented in [19, 25, 26]. At this point we have to call to mind that the proposed AFS algorithm uses many user-defined parameters that affect the algorithm's convergence and efficiency. As a result, it is still an open issue to investigate thoroughly the best set of parameter values for the proposed AFS approach which will assist it to achieve even better results.