## 4 Results of Experiments
### Comparison with Other Methods  
Six algorithms published between 2016 and 2021 were used to compare the GA-RRHC performance. These algorithms include the global-local neighborhood search algorithm (GLNSA) [40], the hybrid algorithm (HA) [19], the greedy randomized adaptive search procedure (GRASP) [51], the hybrid brain storm optimization and late acceptance hill-climbing (HBSO-LAHC) [38], the improved Jaya algorithm (IJA) [52], and the two-level PSO (TIPSO) [53].  
Comparing the execution times of the different algorithms is not appropriate since these were implemented in different architectures and languages and with different programming skills. That is why this work compares these algorithms using their computational complexity concerning the total operation number \((\mathcal{O}(o))\). To use a standard notation for all algorithms, the number of solutions will be represented by \(X\), the iteration number by \(G_{n}\), the number of local search iterations by \(H_{n}\), and \(m\) is the number of machines. The CA-inspired neighborhood algorithms (GA-RRHC and GLNSA) satisfy that \(X=S_{n}l\), where \(l\) is the number of neighbors in the global search.  
The GLNSA uses elitism to select solutions and generates \(l\) neighbors with insertion, swapping, path-relinking operators, a machine mutation, and a tabu search on \(S_{n}\) solutions.  
\begin{table}
\begin{tabular}{l l c} \hline \(G_{n}\) & total iterations of the algorithm & 250 \\ \(G_{b}\) & limit of stagnation iterations & 50 \\ \(S_{n}\) & number of smart-cells & 100 \\ \(E_{p}\) & proportion of elite smart-cells & 0.02 \\ \(l\) & neighbors of each smart-cell & 3 \\ \(\alpha_{m}\) & mutation probability & 0.1 \\ \(H_{n}\) & iterations of the RRHC & 100 \\ \(H_{r}\) & iterations to restart the RRHC & 30 \\ \(\alpha_{c}\) & probability of moving a critical operation in the RRHC & 0.05 \\ \hline \end{tabular}
\end{table}
Table 2: Parameters selected for the execution of the GA-RRHC.  
The GRASP calculates a Gantt chart and then applies a greedy local search which is quadratic with respect to \(o\). The HA applies four genetic operations for each solution and then a TS to select different machines for the critical operations. The HBSO-LAHC uses a clustering of solutions, which requires calculating the distance between them, and then applies four strategies and three neighborhoods for each solution, with one of them on critical operations. For the local search, a hill-climbing algorithm with late acceptance for \(H_{n}\) steps is applied in each solution. The IJA is a modified Java algorithm that applies three exchange procedures to each solution and a local search with the random exchange of blocks of critical operations. Finally, the TIPSO uses two modifications of the PSO: the first is applied to improve the order of operations, and in each iteration of the first PSO, another PSO is used for the allocation of machines.  
Table 3 presents the algorithms ordered from least to most complex, with \(S_{n}<X<H_{n}\) since \(H_{n}\) usually has a high value concerning obtaining a better local search. This table shows that the GA-RRHC has computational complexity comparable to recently proposed state-of-the-art algorithms.  
This analysis only considers the complexity inherent in modifying the order of operations and the machine assignment in a solution. The computational complexity for calculating the makespan or tracking the critical operations is not considered since all the algorithms use them. Thus, the analysis only focuses on the computational processes that make each method different.