## 2 The Relaxed Flexible Flow Shop Problem Model with Sequence-Dependent Setup Times (RFFSP) Methods
### Simulated Annealing Algorithm
Figure 9: HGAG behavior using different population sizes. Table 8 presents the results for the RFFS_SDST_40 \(\times\) 4 \(\times\) 4 \(\times\) 25 instance. 30 runs are carried out in this test. Again, a similar behavior to the previous example is observed: the best result is obtained when an overload of processes is done. The population increases from 120 to 240 individuals, but the execution time increases more than double for the version with 120 individuals. ### Process cooperation in medium instances

Table 9 shows the cooperation results obtained for the RFFS_SDST_60 \(\times\) 4 \(\times\) 4 \(\times\) 25 instance. This table shows that the best result is obtained when using 240 processes and shows that the average of the 30 makespan tests and the best value found improves steadily from 15 processes, in the order 15, 30, 60, 120, 240. Table 10 shows the cooperation results obtained for the RFFS_SDST_80 \(\times\) 4 \(\times\) 4 \(\times\) 25 instance. This table shows that the best result is obtained using 240 processes and that the makespan average and the best value of the 30 tests constantly improve from five processes in the following order: 5, 10, 15, 30, 60, 120, 240. It is also observed that the execution time is close to 4 h for the case of 240 processes. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & \multicolumn{4}{c}{**RFFS_SDST_20 \(\times\) 4 \(\times\) 4 \(\times\) 25**} \\ \hline
**P** & **N** & **Np** & \
\begin{tabular}{c} **Cmax** \\ **Average** \\ \end{tabular} &
\begin{tabular}{c} **t, s** \\ **Average** \\ \end{tabular} & **Best** \\ \hline
5 & 5 & 24 & 1631 & 1631 & 664 \\ \hline
10 & 10 & 12 & 1696 & 1696 & 659 \\ \hline
15 & 15 & 8 & 1747 & 1747 & 656 \\ \hline
30 & 30 & 4 & 660.87 & 1664 & 655 \\ \hline
60 & 60 & 2 & 659.30 & 1708 & 655 \\ \hline
120 & 120 & 1 & 657.97 & 1996 & 654 \\ \hline
240 & 120 & 1 & 656.73 & 4857 & 649 \\ \hline \hline \end{tabular}
\end{table} 
Table 8: RFFS_SDST_40 \(\times\) 4 \(\times\) 4 \(\times\) 25 results. ### HGAG Efficiency on the Grid

**Speedup evaluation**

Figure 10 shows the speedup obtained in the evaluation of the RFFS_SDST_80 \(\times\) 4 \(\times\) 25 problem. The average efficiency of the processors' usage is 93% when using 10, 30, 60, and 120 processes. The remaining 7% represents the non-parallelizable HGAG portion and the communications overhead. This overhead corresponds to the time used to send and receive solutions, leaving out the MPI typical synchronization times, the overload of external processes, and the Linux operating system's communication services. When the number of processes increases, it is observed that the real speedup moves away from the ideal speedup. This behavior is due to the communications overhead increment since the algorithm data usage increases when the number of processes increases. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & \multicolumn{4}{c}{**RFFS_SDST_80 \(\times\) 4 \(\times\) 4 \(\times\) 25**} \\ \hline
**P** & **N** & **Np** & \
\begin{tabular}{c} **Cmax** \\ **Average** \\ \end{tabular} &
\begin{tabular}{c} **t, s** \\ **Average** \\ \end{tabular} & **Best** \\ \hline
5 & 5 & 24 & 1282 & 6521 & 1273 \\ \hline
10 & 10 & 12 & 1279 & 6480 & 1272 \\ \hline
15 & 15 & 8 & 1278 & 6606 & 1270 \\ \hline
30 & 30 & 4 & 1275 & 6618 & 1269 \\ \hline
60 & 60 & 2 & 1274 & 6715 & 1266 \\ \hline
120 & 120 & 1 & 1272 & 6803 & 1264 \\ \hline
240 & 120 & 1 & 1271 & 13,299 & 1263 \\ \hline \hline \end{tabular}
\end{table} 
Table 10: RFFS_SDST_80 \(\times\) 4 \(\times\) 4 \(\times\) 25 results. **Evaluation of the communications overload on the Grid**

The computational grid overhead is calculated based on the maximum bandwidth provided by the communication between clusters, which is 15 Mb/s. The Grid Morelos infrastructure allows two-way communication since messages can be sent and received simultaneously (upload and download). Therefore, the total bidirectional bandwidth can reach 30 Mb/s.