## 4 Exact Approaches
### Performances  
This subsection provides performances comparison between each of the presented MILP, the ATI formulation [13] and the disjunctive formulation [12]. Models are first compared in term of spatial complexity, and then a comparative analysis is conducted on two benchmarks \(B\) and \(B^{\prime}\) of 18 instances each. The benchmark \(B\) differs from \(B^{\prime}\) on setup-times values which are all set to \(0\). The tested instances come from [12] and correspond to instances with \(n=10,15,20\), \(\tau\in\{0.1,0.5\}\), and \(R\in\{0.1,0.5,0.9\}\). Table 2 displays the number of variables and constraints of each formulation using Landau notation. As can be seen, ATI formulation is disadvantaged by its number of decision variables. The other formulations have the same number of variables in the worst case. The TI Pulse formulation benefits from fewer constraints than the other formulations with \(\mathcal{O}(n^{2})\) constraints, coming from the precedence constraints. Results of the tests on the benchmarks \(B\) and \(B^{\prime}\) are reported in Tables 3 and 4. Each line within the tables corresponds to 6 instances of same \(n\) with diverse \(\tau\) and \(R\) values. The number of feasible and optimal solutions found by the models are reported in columns #ea and #opt respectively. Finally, average solving time in seconds (column \(\overline{cpu}\)), average CPLEX gap (column \(\overline{gap}\)), standard deviation for the solving time (column \(\sigma_{cpu}\)) and standard deviation for the gap (column \(\sigma_{gap}\)) are presented for each batch of instances. The last line of the tables gives a summary of performances of each model by displaying the total number of feasible and optimal solutions, the average solving time, the average gap and the average standard deviation values across all instances. In Table 3, models are tested on benchmark \(B\), which is without setup times. The results show that both TI formulations prevail on the other ones in terms of solving time and solution quality. The TI On/Off is even better than the TI Pulse, finding all optimal solutions of \(B\) in a minute on average. According to Table 4, the TI formulations are rapidly overwhelmed in contrast to the ATI and the disjunctive formulations. The solution quality rapidly decreases proportionally to \(n\) for the TI models. In addition, both TI models cannot find some feasible solutions of \(B^{\prime}\). Following the spatial complexity analysis, an explanation can be proposed. The TI formulations are limited by the number of constraints and their nature such as big-M constraints to preserve precedence. Even if the ATI model has a polynomial number of variables, it dominates all the MILP, finding almost all optimal solutions. \begin{table}
\begin{tabular}{c c c c c c c c c c c c c c c c c c c c c c c c c c c c c c c c c c} \hline \hline  & \multicolumn{4}{c}{**Disjunctive**} & \multicolumn{4}{c}{**TI On/Off**} & \multicolumn{4}{c}{**TI Pulse**} & \multicolumn{4}{c}{**ATI**} \\ \hline \(n\) & \#fea & \#opt & \(\overline{cpu}\) & \(\overline{gpu}\) & \(\sigma_{cpu}\) & \#fea & \#opt & \(\overline{gpu}\) & \(\overline{gpu}\) & \(\sigma_{cpu}\) & \#fea & \#opt & \(\overline{gpu}\) & \(\sigma_{cpu}\) & \#fea & \#opt & \(\overline{gpu}\) & \(\sigma_{cpu}\) & \#fea & \#opt & \(\overline{gpu}\) & \(\sigma_{cpu}\) & \(\sigma_{gap}\) \\ \hline
10 & 6 & 6 & 3.17 & 0 & 5 & 0 & 6 & 1 & 3318 & 7 & 690 & 10 & 6 & 6 & 50 & 0 & 37 & 0 & 6 & 6 & 0.7 & 0 & 0.6 & 0 \\
15 & 6 & 6 & 75 & 0 & 68 & 0 & 6 & 0 & 3600 & 529 & 0 & 320 & 6 & 3 & 2567 & 1 & 1530 & 1.7 & 6 & 5 & 609 & 0.1 & 1465 & 0.6 \\
20 & 6 & 1 & 3300 & 6 & 750 & 6.3 & 6 & 0 & 3600 & 1504 & 0 & 850 & 4 & 0 & 3600 & 35 & 0 & 52 & 6 & 6 & 449 & 0 & 830 & 0 \\ \hline  & 18 & 13 & 1687 & 2 & 274 & 2.1 & 18 & 1 & 3506 & 680 & 231 & 393 & 16 & 9 & 2072 & 12 & 522 & 18 & 18 & 17 & 529 & 0.03 & 765 & 0.1 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Models performances on benchmark \(B^{\prime}\).