# A Simple and Efficient Local Search Algorithm for the Machine Reassignment Problem
## 5 Experiments
### Comparison with the Best of ROADEF  
Table 2 summarizes the best qualification and final phase scores and their associated competing teams. Table 3 shows the best quality values reported in the ROADEF challenge for each instance. Moreover, it also shows the average, best, and worst results obtained by our algorithm SMaRT and their corresponding score. It is important to note that the best values reported as Best ROADEF in this table are not associated with a unique solving algorithm. These values correspond to the best values found for each instance by any of the algorithms in the competition. The maximum execution times of all these experiments is fixed to 300 s as established by the ROADEF competition.  
We show in bold the cases when equal or best results were found using in each problem instance using SMaRT algorithm. From these results, we can observe that SMaRT obtains good quality results, reporting consistently better values on Instances B_1 and X_1. These are shown as negative scores in the table. Looking at the worst results of SMaRT, all of them are close to the average values. Moreover, by computing the sum of scores and considering it as the total score, as used in the ROADEF challenge, the worst-case results of SMaRT also obtain a competitive total score, while the average-case and the best-case are better than those in the challenge.  
Additionally, Table 4 shows the comparison of SMaRT with the five best algorithms in the final phase of the ROADEF competition. This table shows the results published by the algorithms proposed in the competition and is currently available at [[https://roadef.org/challenge/2012/en/results.php](https://roadef.org/challenge/2012/en/results.php)]([https://roadef.org/challenge/2012/en/results.php](https://roadef.org/challenge/2012/en/results.php)) (accessed on 28 June 2025). It only lists the average results for each instance. No team obtained the best results on all of the problem instances.  
\begin{table}
\begin{tabular}{l l l l l l l} \hline \hline
**Instance** & **1\({}^{*}\)** & **2\({}^{*}\)** & **3\({}^{*}\)** & **4\({}^{*}\)** & **5\({}^{*}\)** \\ \hline \multirow{2}{*}{Qualification Phase (Instances A)} & \multirow{2}{*}{1.73 (J17)} & \multirow{2}{*}{3.58 (S25)} & 5.92 & 9.55 & \multirow{2}{*}{10.97 (S21)} \\  & & & (S38 [5]) & (S23 [9]) & \\ \hline \multirow{2}{*}{Final Phase (Instances B y X)} & \multirow{2}{*}{0.47} & \multirow{2}{*}{0.62} & \multirow{2}{*}{1.72} & \multirow{2}{*}{2.60} & \multirow{2}{*}{3.91 (S14)} \\  & & (S41 [3]) & & & & \\ \hline \hline \end{tabular}
\end{table}
Table 2: Best 5 scores for each phase.  
\begin{table}
\begin{tabular}{l l l l l l l l} \hline \hline \multirow{2}{*}{**Inst.**} & \multicolumn{2}{c}{**Best ROADEF**} & \multicolumn{2}{c}{**Avg. SMaRT**} & \multicolumn{2}{c}{**Best SMaRT**} & \multicolumn{2}{c}{**Worst SMaRT**} \\ \cline{2-9}  & **OF Value** & **OF Value** & **Score** & **OF Value** & **Score** & **OF Value** & **Score** \\ \hline B\_1 & 3,339,186,879 & 3,331,636,980 & \(\mathbf{-0.099}\) & 3,307,834,020 & \(\mathbf{-0.410}\) & 3,346,269,668 & 0.093 \\ B\_2 & 1,015,553,800 & 1,017,433,717 & 0.036 & 1,015,737,594 & 0.004 & 1,023,968,682 & 0.162 \\ B\_3 & 15,638,578 & 157,475,897 & 0.014 & 156,594,657 & 0.002  
In this case, we divide the set of instances into the hardest instances and the easiest ones. We consider the hardest instances as those where only one team found the best value in the competition. These instances were B_1, B_3, B_5, B_7, X_1, and X_2. We consider the easiest instances as those where at least two teams found the best values of the competition. These instances were B_4, B_6, B_9, X_4, X_5, X_6, X_8, and X_9. The hardest instances are listed in boldface in Table 4, and the easiest are shown in normal font. For the easiest instances, SMaRT obtained the same performance as the other algorithms, finding the minimum values on each problem instance. For the hardest instances, our algorithm was able to obtain better scores than most of the analyzed teams, especially on Instances B_1 and X_1.