## 3 Resolution Approaches
### Approximate Approaches
#### 3.2.3 Simulated Annealing
We observe that, on small problem instances (10 and 20 jobs on 10 machines and 10 jobs on 20 machines), the MILP approach performs, as expected, better than most heuristic approaches. The simulated annealing approach with a large number of iterations, however, ties the MILP approach in the average gap value while also reporting a lower standard deviation. The MILP was, in fact, not able to prove the optimality of the solution, nor even find the best one for all problem instances within the allotted time. The performance of the MILP quickly degrades as the size of the problem instances grows, performing even worse than the greedy constructive heuristic. Among the three tested heuristic approaches, the greedy constructive heuristic is consistently the worst performing, whereas the simulated annealing performs better, especially when increasing the number of iterations it performs. These remarks are also confirmed by the results from Table 11, where the MILP is able to find the best solutions for more problem instances when the number of jobs stays low (\(n=10\)); however, it gets quickly overtaken by the simulated annealing approach with \(10^{6}\) iterations for \(n>10\). \begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline \multirow{2}{*}{\(\mathbf{n}\)} & \multirow{2}{*}{\(\mathbf{m}\)} & \multirow{2}{*}{\(\mathbf{k}\)} & \multicolumn{2}{c}{**MILP**} & \multicolumn{2}{c}{**Greedy**} & \multicolumn{2}{c}{**SA (10\({}^{4}\) iter.)**} & \multicolumn{2}{c}{**SA (10\({}^{5}\) iter.)**} \\  & & & **avg** & **std** & **avg** & **std** & **avg** & **std** & **avg** & **std** \\ \hline
10 & 10 & 5 & **3** & 9 & 35 & 12 & 5 & 5 & **3** & 3 \\
20 & 10 & 5 & **4** & 5 & 37 & 11 & 8 & 4 & 5 & 3 \\
30 & 10 & 5 & 13 & 7 & 39 & 17 & 11 & 6 & **5** & 3 \\
40 & 10 & 5 & 67 & 41 & 40 & 14 & 12 & 6 & **6** & 3 \\
50 & 10 & 5 & 96 & 35 & 50 & 18 & 18 & 7 & **8** & 5 \\ \hline
10 & 20 & 5 & **2** & 4 & 29 & 12 & 4 & 3 & **2** & 2 \\
20 & 20 & 5 & 7 & 6 & 39 & 11 & 7 & 4 & **4** & 3 \\
30 & 20 & 5 & 76 & 41 & 48 & 12 & 12 & 5 & 6 & 3 \\
40 & 20 & 5 & 87 & 36 & 43 & 16 & 13 & 6 & **7** & 4 \\
50 & 20 & 5 & 126 & 31 & 43 & 17 & 15 & 7 & **8** & 4 \\ \hline \hline \end{tabular}
\end{table} 
Table 10: Gap from best solution in percentage (best results depicted in bold). We observe that the MILP always reaches its 3600-second time limit. Since, even for small-sized instances, it was not able to find the best solution overall, we conclude that more than one hour, or more computational resources, are needed for this approach. The constructive heuristic is the fastest, while the execution times of the simulated annealing are of the order of a few seconds when performing fewer iterations, and several minutes when performing more. In order to evaluate the performance of the proposed approaches on instances of a more realistic size, we performed additional tests for problem instances with between 100 and 500 jobs, 50 machines, and 10 resource types. Following the results from the smaller problem instances, we tested here only the heuristic approaches. We report the results on the gap and execution time in Table 13. \begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline \multirow{3}{*}{**n**} & \multirow{3}{*}{**m**} & \multirow{3}{*}{**k**} & \multicolumn{3}{c}{**Gap**} & \multicolumn{3}{c}{**Execution Time**} \\ \cline{3-10}  & & & \multicolumn{2}{c}{**Greedy**} & \multicolumn{2}{c}{**SA (10\({}^{4}\) iter.)**} & \multicolumn{2}{c}{**Greedy**} & \multicolumn{2}{c}{**SA (10\({}^{4}\) iter.)**} \\ \cline{4-10}  & & & **avg** & **std** & **avg** & **std** & **avg** & **std** & **avg** & **std** \\ \hline
100 & 50 & 10 & 35 & 12 & **5** & 3 & **6** & 0 & 112 & 16 \\
200 & 50 & 10 & 42 & 20 & **5** & 3 & **20** & 2 & 232 & 29 \\
300 & 50 & 10 & 37 & 38 & **5** & 4 & **44** & 4 & 469 & 50 \\
400 & 50 & 10 & 33 & 24 & **6** & 4 & **73** & 8 & 779 & 74 \\
500 & 50 & 10 & 24 & 21 & **8** & 6 & **116** & 14 & 1202 & 107 \\ \hline \hline \end{tabular}
\end{table}