## 2 Description of the FJSSP  
The flexible job shop scheduling problem (FJSSP) consists of a set \(J=\{J_{1},J_{2},\ldots J_{n}\}\) of \(n\) jobs and a set \(M=\{M_{1},M_{2},\ldots M_{m}\}\) with \(m\) machines. Each job \(J_{i}\) has \(n_{i}\) operations \(O_{J_{i}}=\{O_{i,1},O_{i,2},\ldots,O_{i,n_{i}}\}\). Each operation \(O_{i,j}\) can be performed by one machine from a set of feasible machines \(M_{i,j}\subseteq M\), for \(1\leq i\leq n\) and \(1\leq j\leq n_{i}\). The processing time of \(O_{i,j}\) in \(M_{k}\) is represented by \(p_{i,j,k}\), and \(o=\sum n_{i}\) is the total number of operations.  
It is necessary to carry out all operations to complete a job, respecting the operation precedence. The FJSSP has the following conditions: (1) At the start, all jobs and all machines are available. (2) Each operation can only be performed by one machine. (3) A machine cannot be interrupted when processing an operation. (4) Every machine can perform one operation at the same time. (5) Once defined, the order of operations cannot be changed. (6) Machine breakdowns are not considered. (7) Different jobs have no precedence restrictions of operations. (8) The machines do not depend on each other. (9) The processing time includes the preparation of the machines and the transfer of operations.  
One solution of an FJSSP instance includes two parts, a sequence of operations that respects the precedence constraints for each job, and the assignment of a feasible machine to each operation. The objective of this paper is to calculate the sequence of operations and the assignment of machines that minimize the makespan \(C_{max}\), the total time needed to complete all jobs, as defined in Equation (1).  
\[min\{C_{max}\}\text{ where }C_{max}=max\{C_{i}\},\text{ for }1\leq i\leq n \tag{1}\]  
\(C_{i}\) is the time when all operations in \(J_{i}\) are completed, subject to:  
\[1\leq i\leq n,\ 1\leq j\leq n_{i},\ 1\leq k\leq m\text{ such that }M_{k}\in M_{i,j},\ p_{i,j,k}>0 \tag{2}\]  
\[s_{i,j,k}+p_{i,j,k}\leq s_{i,j+1,k} \tag{3}\]  
\[X_{i,j,k}=\left\{\begin{array}{ll}1,&\text{if operation }O_{i,j}\text{ is processed on }M_{k}\\ 0,&\text{otherwise}\end{array}\right\} \tag{4}\]  
\[\sum_{k=1}^{m}X_{i,j,k}=1 \tag{5}\]  
\[\sum_{i=1}^{n}\sum_{j=1}^{n_{i}}X_{i,j,k}=1 \tag{6}\]  
In this formulation, the start time of operation \(O_{i,j}\) in \(M_{k}\) is \(s_{i,j,k}\). The processing time of every operation greater than 0 is reviewed in Equation (2). The precedence between operations of the same job is considered in Equation (3). Equation (4) is an assignment record of one operation to a valid machine; Equation (5) represents that each operation is processed by only one machine. The constraint in Equation (6) guarantees that, at any time, every machine can process only one operation.  
Table 1 provides an example of an FJSSP instance with three jobs, two operations per job, and three machines, where all machines can perform all operations. A possible solution to this problem is presented in the Gantt chart in Figure 1.  
\begin{table}
\begin{tabular}{c c c c c} \hline
**Job** & **Op.** & \(M_{1}\) & \(M_{2}\) & \(M_{3}\) \\ \hline \(J_{1}\) & \(O_{1,1}\) & 3 & 4 & 4 \\  & \(O_{1,2}\) & 1 & 2 & 1 \\ \(J_{2}\) & \(O_{2,1}\) & 2 & 3 & 3 \\  & \(O_{2,2}\) & 3 & 3 & 2 \\ \(J_{3}\) & \(O_{3,1}\) & 3 & 3 & 3 \\  & \(O_{3,2}\) & 2 & 2 & 1 \\ \hline \end{tabular}
\end{table}
Table 1: Example of an FJSSP with 3 jobs, 3 operations per job, and 3 machines.  
Figure 1: Gantt diagram of one possible solution for the FJSSP in Table 1.