## 2 The Relaxed Flexible Flow Shop Problem Model with Sequence-Dependent Setup Times (RFFSP) Methods
### Simulated Annealing Algorithm
The communication overhead is evaluated for the RFFS_SDST_80 \(\times\) 4 \(\times\) 4 \(\times\) 25 problem, using 120 processes distributed over 120 cores and using the virtual private network joining the two clusters. First, experimental tests of sending and returning bit packets between both clusters are carried out. The packet sizes range from 64 to 67,108,864 bits in order to evaluate the time it takes to send them. For example, the send and return time of a 64-bit packet is 750 microseconds, which is equivalent to 0.163 Mb/s. The results of these tests are described in Table 12.

For calculating the overhead that HAGG presents when solving the RFFS_SDST_80 \(\times\) 4 \(\times\) 4 \(\times\) 25 instance with 120 processes distributed over 120 cores in the Grid, it is necessary to determine the number of bits of a solution represented by an individual in the algorithm. The instance comprises 80 jobs, which must be executed in series on four stages, each with four identical parallel machines. The number of bits of an individual is 40,960 bits, so the population's total size is 4,915,200 bits. As the distribution of the 120 processes in the computational grid is 60 in the Cuexcomate cluster and 60 in the Texcal cluster, only half of the population travels from one cluster to another, that is, 2,457,600 bits. Table 12, shows that, for this size, the value is between the interval (2,097,152-4,194,304). By performing an interpolation with these values, a total time of 341,689 usecs is obtained for the population size evaluated in one generation. Therefore, the total overload time for the 30 generations is 10,250,580 usecs, that is, approximately 10.3 s. This is the time that the algorithm spends sending and receiving the slave processes' solutions during the total algorithm execution time. The maximum transfer rate between clusters on the grid is 15 Mbs (15,728,640 bits/s). It is understood that the optimal transfer rate to avoid bottlenecks must be less than or equal to 15,728,640 bits/s. Table 12 shows that the highest transfer rate occurs when sending packets is 8,388,608 bits (14,339 Mb/sec). Comparing this value with the 2,457,600 bits that the HAGG uses per packet, it is clear that there is no traffic congestion between clusters since the packet size sent by the HAGG only represents 29.3% of the bandwidth available to send packages between the grid clusters. Figure 10: Average speedup for the HGAG algorithm for RFFS_SDST_80 \(\times\) 4 \(\times\) 4 \(\times\) 25 problem. ## 5 Conclusions

A hybrid genetic algorithm implemented in a grid environment to solve hard instances of the flexible flow shop scheduling problem with sequence-dependent setup times is described in this paper. Each offspring generated by the evolutionary operators is improved using the combination of an iterative and cooperative local-search. The evolutionary process is conducted in a master process, and the local search is performed in a set of slave processes distributed in a grid environment. The point-to-point communication between the grid nodes is through a message passing mechanism. Since the implemented algorithm uses several parameters, and their performance depends on the values used for them, a sensibility analysis to determine the more suitable values to the parameter setting is conducted. The experimental results are analyzed considering the algorithm convergence and the efficacy and efficiency of the Morelos Grid to solve the test instances. The HGAG has an efficient convergence rate since it uses almost 30 iterations to reach a near-optimal solution. Furthermore, the use of a set of distributed nodes impacts the solution quality since each node applies a combined local search that increases the algorithm running time if implemented in one only process. Finally, the speedup evaluation indicates that 93% of the processors' usage is applied. It is observed that traffic congestion between clusters does not exist since the packet size transmitted by the algorithm uses 29.3% of the available bandwidth.