## 2 The Relaxed Flexible Flow Shop Problem Model with Sequence-Dependent Setup Times (RFFSP) Methods
### Ant Colony System Algorithm  
Algorithm 2 generates the cooperative-local search by applying an ant colony system (ACS) [28]. The ACS is used by HGAG, as is shown in line 14 of Algorithm 1. Figure 7: Hybrid genetic algorithm in grid environment (HGAG). The ACS elements are described as follows:  
**Line 1:** ACS receives the following parameters:  
* \(h\) is the number of ants. * \(\alpha\) is the importance coefficient alpha. * \(\beta\) is the importance coefficient beta. * \(\gamma\) is the evaporation coefficient for the local transition. * \(\delta\) is the evaporation coefficient for the global transition. * \(q\) is the coefficient to divide the exploration and exploitation rates. * \(p\) is the stop criterion of the algorithm. * \(UB\) is the best-known quote in the literature. * \(S_{ant}\) is the ACS initial solution. **Line 2:** The minimum pheromone value \(\tau_{0}\) used in each arc of the solution depicted in Figure 2 is defined. \(\tau_{0}\) is computed using the problem values (\(n,m,k\)) and its best upper bound known. **Line 3:** The \(\tau_{0}\) value is assigned to each graph arc in Figure 2.  
**Line 4:** Extra pheromone is deposited on the arcs of the initial solution received (\(S_{ant}\)), which is computed using the inverse of its fitness value. If \(S_{ant}\) is an empty solution, no extra pheromone is deposited. **Line 5:** The makespan of the initial \(S_{BestLocal}\) solution is set using a maximum value. **Lines 6-20:** This is the local search procedure involving the generation of solutions for the \(k\) ants, the evaporation of pheromone step by step, the updating of the best solution, and the adding of pheromone to the best solution in a cycle of \(p\) iterations. **Lines 7-9:** The \(S_{ant}\) solutions are generated for each ant using the _BuildSolution_ function with \(\alpha,\beta,\gamma,q\), \(\tau_{r,s}\), and ant\({}_{k}\) as parameters. These solutions are stored in a vector \(S[ant_{k}]\) with \(k\) = {1,..., _h_}. The _BestSolution_ function is described in Algorithm 3. **Line 10:** In each iteration, the best solution with the lowest cost is identified, and its path is assigned to the \(S_{BestLocal}\) variable. **Lines 11-19:** All solutions in the vector \(S[ant_{k}]\) are updated by evaporating and depositing pheromone only in those arcs that belong to the best solution found, where \(\delta\) \(\in\) (0, 1] is an evaporation coefficient. **Line 21:** At the end of the local search procedure, the \(S_{bestLocal}\) solution is returned. The _BuildSolution_ function is described in Algorithm 3, which is used to create the solutions for each \(ant_{k}\). Its elements are explained in the following paragraphs:  
```
1 Function BuildSolution(\(\alpha\), \(\beta\), \(\gamma\), \(q\), \(\tau_{r,s}\), \(k\))
2\(r\leftarrow\) input
3\(S_{k}\leftarrow\)[r]
4 Repeat
5\(r\leftarrow\) random [0, 1]
6 if\(s\in S_{k}(r)\wedge r\leq q\wedge s\
otin tabu_{k}\)then
7\(\text{Sig}^{k}{}_{rs}\leftarrow\max s\
otin S_{k}(r)[\ (\tau_{r,s})\ ^{\alpha}. (u_{r,s}) ^{\beta}\ ]\)
8 elseif\(s\in S_{k}(r)\wedge r>q\wedge s\
otin tabu_{k}\)then
9\(\text{Sig}^{k}{}_{rs}\leftarrow\text{roulette}((\tau_{r,s})^{\alpha}. (u_{r,s}) ^{\beta})/(\sum_{u}\in S_{k}(r)((\tau_{r,u})^{\alpha}. (u_{r,u})^{\beta})\)
10 Otherwise
11\(\text{Sig}^{k}{}_{rs}\gets 0\)
12 endif
13\(S_{k}=S_{k}+sig_{s}\)
14\(\tau_{r,s}=(1\text{-}\gamma)\). \(\tau_{r,s}+\gamma.\tau_{0}\)
15\(\text{s}\leftarrow\text{r}\)
16 until(r == exitCondition)
17 return(\(S_{k}\))
18 endFunctionBuildSolution
```  
**Algorithm 3** Local Cooperative Search-BuildSolution()  
**Line 1:** The algorithm receives \(\alpha\), \(\beta\), \(\gamma\), \(q\), \(k\) as parameters. **Line 2:** The ant \(k\) is placed in the initial arch. **Line 3:** The initialization of the solution of ant \(k\) (\(S_{k}\)) by adding the first arc \(r\) visited. **Lines 4-16:** This is the core section of the algorithm. The ant \(k\) traverses the graph, node by node, until it reaches the final node.