## 2 The Relaxed Flexible Flow Shop Problem Model with Sequence-Dependent Setup Times (RFFSP) Methods
### Disjunctive Graph Model  
Figure 1 shows a disjunctive graph G modeling the RFFSP for an example of two jobs (\(N=2\)) processed in three stages (\(M=3\)), each stage with two identical machines (\(M_{k}=2\)). \(G\) is composed of three sets representing the conjunctive arcs \(A\), the disjunctive arcs \(E\), and the graph nodes \(O_{i,jk}\). These nodes identify the jobs' operations. Set \(A\) includes three arcs subsets, each by one job. For example, the subset of arcs joining \(O_{[1\,2]11}\), \(O_{[1\,2]12}\), and \(O_{[1\,2]13}\) operations correspond to job 1. Also, the conjunctive arcs define the precedence relation between operation pairs. For example, \(O_{[1\,2]11}\) must be processed before \(O_{[1\,2]12}\), and \(O_{[1\,2]12}\) before \(O_{[1\,2]13}\). Each node in \(G\) is depicted using a blue circle with a dashed line, and inside it, two gray circles with continuous lines represent the parallel machines used in this stage. The processing time \(p_{jk}\) of each operation is also depicted in the blue circle, \(p_{11}=7\) for \(O_{[1\,2]11}\) in Figure 1, for example. Furthermore, \(G\) uses two fictitious operations, labeled as _input_ and _output_, to specify the start and end of each job's processing time. The operations processed in the same stage define a clique, since they are joined using disjunctive arcs. For example, \(O_{[1\,2]11}\), \(O_{[1\,2]21}\), and \(O_{[1\,2]31}\) are processed in stage one. It is necessary to find the operations processing sequence at each stage, selecting one of the parallel machines for each operation. Once this sequence is found, the disjunctive  
Figure 1: A disjunctive graph representing a RFFSP with three jobs, three stages, and two machines by stage. arches will become conjunctive arcs. Table 1 shows the setup times for each operation of the example shown in Figure 1.  
Figure 2 shows a solution to the example previously described. It can be seen that the sequence of the operations in each stage is defined, disjunctive arcs are now conjunctive, and only one machine has been assigned to each operation. Furthermore, the processing and setup times are depicted in each arc with black and red numbers, respectively. A Gantt diagram of the scheduling of the solution described previously is shown in Figure 3, where the job's operations are outlined using the same color. In this diagram, the solution fulfills the precedence constraints between pairs of operations of the same job, and each operation starts its processing until the machine setup time is accomplished. The solution of any RFFSP instance can be reached using the mathematical model described in the previous section. \begin{table}
\begin{tabular}{c c c c c} \hline \hline \(ST_{ijk}\) & \(j=1\) & \(j=2\) & \(j=3\) & **0 (Cleaning)** \\ \hline \multicolumn{5}{c}{Stage 1 (\(ST_{ijk}\))} \\ \hline
0 (start) & \(ST_{011}=2\) & \(ST_{021}=1\) & \(ST_{031}=3\) & \(ST_{001}=0\) \\ \(l=1\) & \(ST_{111}=0\) & \(ST_{121}=2\) & \(ST_{131}=1\) & \(ST_{101}=0\) \\ \(l=2\) & \(ST_{211}=1\) & \(ST_{221}=0\) & \(ST_{231}=1\) & \(ST_{201}=0\) \\ \(l=3\) & \(ST_{311}=2\) & \(ST_{321}=3\) & \(ST_{331}=0\) & \(ST_{301}=0\) \\ \hline \multicolumn{5}{c}{Stage 2 (\(ST_{ijk}\))} \\ \hline
0 (start) & \(ST_{012}=1\) & \(ST_{022}=2\) & \(ST_{032}=3\) & \(ST_{002}=0\) \\ \(l=1\) & \(ST_{112}=0\) & \(ST_{122}=3\) & \(ST_{132}=2\) & \(ST_{102}=0\) \\ \(l=2\) & \(ST_{212}=1\) & \(ST_{222}=0\) & \(ST_{232}=1\) & \(ST_{202}=0\) \\ \(l=3\) & \(ST_{312}=3\) & \(ST_{322}=3\) & \(ST_{332}=0\) & \(ST_{302}=0\) \\ \hline \multicolumn{5}{c}{Stage 3 (\(ST_{ijk}\))} \\ \hline
0 (start) & \(ST_{013}=3\) & \(ST_{023}=3\) & \(ST_{033}=1\) & \(ST_{003}=0\) \\ \(l=1\) & \(ST_{113}=0\) & \(ST_{123}=2\) & \(ST_{133}=1\) & \(ST_{103}=0\) \\ \(l=2\) & \(ST_{213}=2\) & \(ST_{223}=0\) & \(ST_{233}=1\) & \(ST_{203}=0\) \\ \(l=3\) & \(ST_{313}=3\) & \(ST_{323}=2\) & \(ST_{333}=0\) & \(ST_{303}=0\) \\ \hline \hline \end{tabular}
\end{table}