## 2 The Relaxed Flexible Flow Shop Problem Model with Sequence-Dependent Setup Times (RFFSP) Methods
### Simulated Annealing Algorithm  
Algorithm 4 implements the iterative local search by applying a simulated annealing (SA) algorithm [30]. SA is applied by HGAG, as shown in line 16 of Algorithm 1. In each SA iteration, the Metropolis cycle uses the Boltzmann probability function as an acceptance criterion, computed using the temperature control parameter T, avoiding local optimum since it cannot accept improved solutions. Its elements are described in the following paragraphs:```
1. FunctionSA(t\({}_{0}\), m, \(\mu\), t\({}_{t}\), Smetal)
2. \(T\gets T_{o}\)
3. \(C_{max}(S_{BestLocal})\gets 999999\)
4. \(S_{ncent}\gets S_{metal}\)
5. Repeat
6. for\(i\), \(i\) = 1, 2,..., \(m\)do
7. \(S_{new}\gets N(S_{ncent})\)
8. if(\(C_{max}\)\(S_{new}\)) \(\leq C_{max}(S_{ncent})\)) then
9. \(S_{ncent}\gets S_{new}\)
10. if(\(C_{max}(S_{ncent})\leq C_{max}(S_{BestLocal})\)) then
11. \(S_{BestLocal}\gets S_{ncent}\)
12. end if
13. else if\(S_{diff}\gets C_{max}(Snew)-C_{max}(S_{ncent})\)
15. \(r\leftarrow\) random [0, 1]
16. if(\(r\leq e^{-\frac{S_{eff}}{T}}\)) then
17. \(S_{ncent}\gets S_{new}\)
18. end if
19. end if
20. end for
21. \(T\gets T\). \(\mu\)
22. until(\(T\leq T_{f}\))
23. return(\(S_{BestLocal}\))
24. end Function SA
```

**Algorithm 4** SA (Simulated Annealing)

**Line 1:** SA receives the following parameters:

* \(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 is the solution found by the ACS algorithm. **Line 2:** The temperature T is initialized to a temperature \(T_{o}\) that will be decreased as the search progresses. **Line 3:** The makespan of the initial \(S_{BestLocal}\) solution is set using a maximum value. **Line 4:** The \(S_{ncent}\) solution is initialized to the \(S_{metal}\) value. **Lines 5-22:** This is the external cycle of the SA algorithm. This cycle updates the temperature control parameter and ends when the current temperature \(T\) is lower than the final temperature \(T_{f}\). **Lines 6-20:** This is the Metropolis internal cycle. The Markov chain length determines its number of iterations. * **Line 7:** A new solution \(S_{new}\) is created using a local search in the neighborhood of \(S_{ncent}\)\(N(S_{ncent})\). * **Lines 8-12:** If the objective function cost, defined in Equation (1), of the solution \(S_{new}\) is not greater than those of the \(S_{ncent}\) solution, \(S_{new}\) replaces \(S_{ncent}\). \(S_{ncent}\) always takes the best solution found. Furthermore, the \(S_{bestLocal}\) solution is updated with \(S_{new}\). * **Lines 13-19:** On the other hand, if the objective function cost of the solution \(S_{new}\) is greater than those of the \(S_{ncent}\) solution, the Boltzmann criterion is used to accept the \(S_{new}\) solution as the \(S_{ncent}\) solution. This criterion allows escaping from local optimums and the continued exploration of the solution space. **Line 23:** The algorithm returns the \(S_{bestLocal}\) solution. ### Solution Representation

The SA candidate solution representation is the same as those used in the HGAG. In Figure 5, the sequence of the operations depicted in Figure 5 is:

\[O_{111}\to O_{131}\to O_{221}\to O_{122}\to O_{212}\to O_{232}\to O_{123}\to O_{133} \to O_{213}\]

The neighborhood structure used to find new candidate solutions is based on exchanging pairs of adjacent operations processed on the same machine or different machines. An example of one exchange in the same machine is as follows:

\[O_{131}\to O_{111}\to O_{221}\to O_{122}\to O_{212}\to O_{232}\to O_{123} \to O_{133}\to O_{213}\]

On the other hand, an example of an exchange of pairs of operations processed in different machines is as follows:

\[O_{221}\to O_{131}\to O_{111}\to O_{122}\to O_{212}\to O_{232}\to O_{123} \to O_{133}\to O_{213}\]

It is necessary to indicate that another machine executes the operation.