## 2 The Relaxed Flexible Flow Shop Problem Model with Sequence-Dependent Setup Times (RFFSP) Methods
### Hybrid Genetic Algorithm in Grid Environment (HGAG)
A crossover rate is defined to explore the solutions space of the new population. **Line 12:** The new population is distributed to the slave processes: _individual\({}_{1}\)_ is sent to Process\({}_{1}\), _individual\({}_{2}\)_ is sent to Process\({}_{2}\), and so on until the entire population is sent. All the slave processes wait for an evolved solution and then apply the mutation operator. **Slave process**  
**Line 14:** The ACS (Algorithm 2) is used to compute an improved solution based on that received from the master process. ACS uses a cooperative mutation guided by the pheromone traces based on the initial solution and returns \(S^{\prime}_{ant}\) as the best-found solution. **Line 15:** The \(S_{metal}\) solution is calculated using a transformation function to convert the best solution found by ACS (\(S^{\prime}_{ant}\)) to be used as the SA initial solution. \(S_{metal}\) is equivalent to \(S^{\prime}_{ant}\) since the transformation function does not alter the scheduling. It only realizes a context change on the solution representation. **Line 16:**\(S^{\prime}_{metal}\) is calculated using SA (Algorithm 4). The SA parameters are the follows:  
* \(t_{0}\) is the initial temperature. * \(m\) is the Markov chain length. * \(\mu\) is the frozen coefficient. * \(t_{f}\) is the final temperature
* \(S_{metal}\) is the SA initial solution. This routine applies an iterative mutation guided by the initial solution \(S_{metal}\). SA returns \(S^{\prime}_{metal}\) as its best-found solution. **Line 17:**\(S_{individual}\) is computed using a transformation function to convert the best solution found by SA (\(S^{\prime}_{metal}\)) in one GA individual. This transformation enables SA to send \(S^{\prime}_{metal}\) to the master process to build a new population. **Line 18:** The best solution between those found by ACS and SA is stored in the variable \(S_{BestLocal}\). **Line 19:** The best local solution is sent to the master process. At this point, the master process waits to receive all solutions from the slave processes. **Line 20:** Every slave process waits for the master process to send it \(S^{\prime}_{individual}\). The _ReceiveF_ function blocks the slave process until a solution is received. **Line 21:**\(S_{ant}\) is computed using a transformation function. This transformation prepares the algorithm for the next generation that begins with a cooperative mutation with ACS. **Final stage**  
**Line 27:** Finally, the best global solution found by HGAG is returned (\(S_{mBSetGlobal}\)). **Population Construction**  
The HGAG population is distributed in the grid with a 1:1 ratio, i.e., one individual for each process \(p\) generated in the computational grid. A single process is assigned to each core that the processor contains. The master process stores the solutions found by the other process in a solutions vector. The master process receives the best solutions found by each slave process and assigns these solutions to the vector to build a new population in each generation. The symbolic representation of a solution encoded as a GA individual is presented in Figure 5. This representation consists of a data structure storing the sequence of operations in each machine and each stage, and the scheduling obtained using all start times \(s_{jk}\) for each operation. With the scheduling, the Makespan \(C_{jk}\) of each job is obtained for the last stage to compute the maximum Makespan \(C_{max}\). In Figure 5, the individual encodes the solution depicted in Figure 2. The scheduling of this solution is shown in Figure 3. In this case, \(C_{max}=36\). For the sake of simplicity, the individual is represented in a sequence of operations for each machine, as follows:  
\[O_{111}\rightarrow O_{131}\rightarrow O_{221}\rightarrow O_{122}\to O _{212}\rightarrow O_{232}\rightarrow O_{123}\rightarrow O_{133}\to O _{213}\]