## 2 Problem Description  
FJSP is a kind of resource allocation problem, _i.e._, given \(M\) machines and the \(N\) work pieces, FJSP aims to minimize the operating time by optimizing the arrangement of the operations of all jobs t. A set of machines \(M\) = {\(M_{1}\),\(M_{2}\),...,\(M_{m}\)} and a set of independent jobs \(J\) = {\(J_{1}\),\(J_{2}\),..., \(J_{n}\)} are given. Additionally, each job \(J_{i}\) consists of a sequence of operations \(O_{ij}\), where \(O_{ij}\) represents the \(j\)-th operation of the job \(i\). All of the operations of each job should be performed one after another in a given order. Each operation \(O_{ij}\) can be processed on any machine among a subset \(M_{i,j}\subseteq M\) of compatible machines. Based on the different conditions of resource restriction, the flexible job shop scheduling problem can be divided into a total flexible job-shop scheduling (T-FJSP) problem and a partial flexible job-shop scheduling (P-FJSP) problem. In T-FJSP, every process of each operation can choose any one machine to be processed; in P-FJSP, some processes of some work pieces can be processed on any one of the machines, and some certain processes can only choose parts of machines. All jobs and machines are available at Time 0, and a machine can only execute one operation at a given time. The processing time of each operation is dependent of the machine, and \(p_{mi}\) represents the processing time of operation \(O_{ij}\) on machine \(i\). If the operation \(O_{ij}\) cannot be processed on machine k, the processing time \(p_{mk}\) is assumed as \(\infty\). Each operation must be completed without interruption during its process. The objective of FJSP is to assign each operation to one machine that is capable of performing it and to determine the starting time for each operation in order to minimize the makespan. In order to describe the FJSP well, Figure 1 is an example of FJSP with three jobs and five machines. In Figure 1, (0, 0, 0) means spending zero seconds on the first machine, zero seconds on the second one and zero seconds on the third one. Therefore, the flexible job-shop scheduling problem model can be described as follows:  
\[\text{Minimize C}_{\text{max}} \tag{1}\]  
Subject to  
\[s_{jh}+x_{ijh}\times p_{jh}\leq c_{jh}\left(i=1,\ldots,n;h=1,\ldots,h_{j}\right)\] (a)  
\[c_{jh}\leq s_{j(h+1)}\left(j=1,\ldots n;h=1,\ldots,h_{j}-1\right)\] (b)  
\[c_{jh_{i}}\leq c_{\text{max}}\left(j=1,\ldots n\right)\] (c)  
\[s_{jh}+p_{jh}\leq s_{kl}+L(1-y_{ijhkl}),\] (d)  
\[\left(j=0,\ldots,n;k=0,\ldots,n;h=1,\ldots,h_{j};l=1,\ldots h_{k};i=1,\ldots,m\right)\] (e)  
\[\sum_{i=1}^{m_{\mu}}x_{ijh}=1\left(h=1,\ldots,h_{j};j=1,\ldots,n\right)\] (f)  
\[\sum_{j=1}^{n}\sum_{h=1}^{h_{j}}y_{ijhkl}=x_{ijh}\left(i=1,\ldots,m;k=1,\ldots,n;l=1,\ldots,h_{k}\right)\] (g)  
\[\sum_{k=1}^{n}\sum_{h=1}^{h_{k}}y_{ijhkl}=x_{ijh}\left(i=1,\ldots,m;j=1,\ldots,n;h=1,\ldots,h_{k}\right)\] (h)  
\[s_{ik}\geq 0,c_{jh}\geq 0\left(j=0,1,\ldots,n;h=1,\ldots,h_{j}\right)\] (i)  
where  
\[x_{jh}= \begin{cases}1&\text{If the operation $O_{jh}$ is on machine $i$}\\ 0&\text{otherwise}\end{cases}  \tag{2}\]  
Figure 1: An example of the flexible job scheduling problem (FJSP). \[y_{j\,j\,bkl}= \begin{cases}1&\text{if the operation }O_{j\,h}\text{ is before the operation }O_{k\,l}\text{ on machine }i\\ 0&\text{otherwise}\end{cases}  \tag{3}\]  
\(n\) is the total number of jobs; m is the total number of machines; \(h_{j}\) is the total number of operations of job \(j(j\in n)\); \(O_{jh}\) is the \(h\)-th operation of job \(j\) (\(h\) = 1,2,...,\(h_{l}\)); \(p_{j\,j\,h}\) is the processing time of the \(h\)-th operation of job \(j\) on the machine (\(I\in\ m\)); \(s_{j\,h}\) is the start processing time of the \(h\)-th operation of job \(j\); \(c_{j\,h}\) is the completion time of the \(h\)-th operation of job j; \(L\) is a given big integer; \(C_{max}\) is the maximum completion time. Formulas (a) and (b) are the operation constraints of each job. Formula (c) is the time constraint of each job.