## 5 Computational Results
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Input** & \multicolumn{3}{c}{**Best roster reported ever [38]**} & \multicolumn{3}{c}{**Best roster found by the proposed algorithm**} \\ \cline{2-5}
**Instance** & **Found by** & **Fitness value** & **Execution Time** & **Fitness value** & **Execution Time** \\ \hline Valouxi-1 & [PERSON], 3/9/2008 & 20 & Not mentioned & 20 & 17.64 s \\  & [PERSON], [PERSON] and & & & & \\ BCV3-46.2 & [PERSON], using a Hybrid & 894 & 4 h, 57 min & 894 & 16 min \\  & VDS, 2/8/2008 & & & & \\ MUSA & Not mentioned & 175 & Not mentioned & 175 & 0.12 s \\  & [PERSON], using a variable & 301 & 10 s & 301 & 0.3 s \\  & depth search, 5/9/2008 & & & & \\ BCV4-13.1 & Not mentioned & 10 & Not mentioned & 10 & 3 s \\ [PERSON] & [PERSON] _et al._, 5/4/2009 & 5 & Not mentioned & 5 & 9.1 s \\ HED01 & Tec on BEECHBONE (CS), & 136 & Not mentioned & **129** & 29.1 s \\  & 11/2/2010 & & & & \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Comparing the best timetables constructed by the proposed algorithm with the best timetables ever reported for these specific instances. Experimental results presented in Table 4 show that the average fitness reached by the proposed two-phase variable neighborhood search approach is, in most cases, very close to the best one achieved for each input instance. This demonstrates that the proposed algorithm is stable and efficient. We also notice that CV of fitness function value ranges from 0% to 41.7%, with the great majority of CV values being below 10%. More specifically, in four out of seven cases, CV equals 0, which means that the algorithm is totally homogenous. This observation leads to the conclusion that the behavior of the algorithm concerning the resulted fitness function value for 100 Monte Carlo runs per input instance is quite homogenous. Note that we have intentionally avoided calculating CV values for the execution time. This is done because STD and average values are close to each other, so the CV value for the execution time would be misleading. Moreover, in Table 4, we present the success rate, _i.e._, the percentage of cases that the proposed algorithm achieves the best fitness function value among 100 Monte Carlo runs. The fact that, in most cases, the success rate achieved is bigger than 60%, demonstrates the efficiency of the proposed algorithm. In addition, in four cases, the success rate is 100%. Finally, we present convergence results (maximum, average and minimum evaluation function value _versus_ number of function evaluations) in order to illustrate the evolutionary behavior of the proposed algorithm. Figure 8 illustrates the convergence behavior of the proposed algorithm for four input instances, namely, MUSA, LLR, BCV4-13.1 and HED01. In all cases, the algorithm's convergence behavior is very satisfactory, since it avoids falling into local optima very quickly and shows significant improvement during the evolutionary process. In these experiments, because our main concern was to reach or even beat the best ever reported result for each different input instance, we used as the determination criterion \"the total number of generations\".