## 2 The Relaxed Flexible Flow Shop Problem Model with Sequence-Dependent Setup Times (RFFSP) Methods
### Hybrid Genetic Algorithm in Grid Environment (HGAG)  
The HGAG designed and developed in this work used to solve the RFFSP is presented in Algorithm 1, the steps of which are detailed in the following paragraphs. Also, the main elements of the GA are described. Multiple instances of the HGAG run in the computational grid. The algorithm automatically assigns identifiers unequivocally for each running process. These identifiers are used to select the HGAG code segment to be run: if it is zero, the code segment chosen is for the master process. Otherwise, the code segment selected is for the slave processes. ```
1. Note: blocking routines are used for sending and receiving messages
2. Function \(HGAG\leftarrow\) (Process\({}_{id}\), \(id_{max}\))
3. if(Process\({}_{id}\) == ProcSlave)then
4. \(S_{ant}\leftarrow\{\varnothing\}\)
5. \(C_{max}(S_{BestLocal})\gets 99999\)
6. end if
7. Repeat
8. if(Process\({}_{id}\) == ProcMaster)then
9. ReceiveF(Process\({}_{i}\), population[individual], blocking), \(i=1,2,\cdots,id_{max}\)
10. population \(\leftarrow\)selectionF(rouleCp, population)
11. population\(\leftarrow\)crossoverF(crossoverR, circularOp, population)
12. SendF(Process\({}_{i}\), population[individual], \(i=1,2,\cdots,id_{max}\)
13. Else
14. \(S^{\prime}_{ant}\gets ACS(h,\kappa,\beta,\gamma,\delta,p,q,UB,S_{ant})\)
15. \(S_{metal}\leftarrow\left(S^{\prime}_{ant}f_{-}SA\right)\)
16. \(S^{\prime}_{metal}\gets SA\left(t_{0},m,\mu,t_{f},S_{metal}\right)\)
17. \(S_{individual}\leftarrow\left(S^{\prime}_{metal}f_{-}individual\right)\)
18. \(S_{BestLocal}=min\left(C_{max}(S_{BestLocal},S_{ant},S^{\prime}_{ant},S^{ \prime}_{metal}\right)\right)\to individual\)
19. \(SendF(ProCluster,S_{individual})\)
20. ReceiveF(ProCluster, \(S_{individual}\), blocking)
21. \(S_{ant}\leftarrow\left(S^{\prime}_{individual}f_{-}ACS\right)\)
22. end if
23. until (number of generations)
24. if(Process\({}_{id}\) == ProcMaster)then
25. ReceiveF(Process\({}_{i}\), population[individual], \(i=1,2,\cdots,id_{max}\)
26. \(S_{BestGlobal}\gets min\left(C_{max}(population[individual]]\right)\),\(i=1,2,\cdots,id_{max}\)
27. return(\(S_{BestGlobal}\))
28. Else
29. SendF(ProCluster, \(S_{BestLocal}\))
30. end if
31. end Function\(HGAG\)
```  
**Algorithm 1** Hybrid Genetic Algorithm in Grid Environment (HGAG)  
**Initialization stage**  
**Line 2:** The algorithm receives the process identifier (Process\({}_{id}\)) and the number of the available process (id\({}_{max}\)) as input parameters. **Lines 3-6:** If the Process\({}_{id}\) corresponds to one slave process, the Ant Colony System and the corresponding makespan are initialized (\(S_{ant}\) = \(\O\), \(C_{max}(S_{BestLocal})\) = 999999). **Evolutionary stage**  
**Lines 7-23:** This is the main procedure with regard to the HGAG finding the best solutions for the RFFSP. If Process\({}_{id}\) corresponds to a master process, lines 9-12 are carried out; otherwise, lines 14-21 are run. This procedure is run until a stop condition is reached. **Master process**  
**Line 9:** The master process waits until the slave processes have sent their candidate solutions. With these solutions, it builds the initial population as a vector of individuals. The population size is defined by the variable id\({}_{\text{max}}\) = P\({}_{\text{max}}-1\), where P\({}_{\text{max}}\) is the number of processing cores. The population is initialized with the messages sent by the slave processes (Process\({}_{1}\) to Process\({}_{\text{idmax}}\)). Each message sent is one individual encoding the best solution found by SA (Algorithm 4) and ACS (Algorithm 2). In particular, the _receiveF_ function has a blocking behavior; that is, while the master process waits to receive messages, it is kept blocked until all of them are received. **Line 10:** A new population is generated by applying the selection operator using the roulette method. The aim is to have the best-adapted individuals in the new population. **Line 11:** A new population is generated as a result of applying the circular crossover operator.