# No-Wait Job Shop Scheduling Using a Population-Based Iterated Greedy Algorithm
## 2 No-Wait Job Shop Scheduling Problem (NWJSP) with Makespan Minimization
### Problem Formulation  
In conformity with the description in Zhu and Li [16], the notations in Table 1 are used. For two jobs \(J_{i}\) and \(J_{j}\), let \(u\) and \(v\) be their two operations that are processed on the same machine (\(\{u,v\}\in\xi_{ij}\)). According to the no-wait constraint, the completion time of operation \(u\) and \(v\) is \(t_{i}+P_{iu}\) and \(t_{j}+P_{jv}\), respectively. Operation \(u\) is either anterior or posterior to operation \(v\). Therefore, we have \(t_{j}+P_{jv}-p_{jv}\geq t_{i}+P_{iu}\) or \(t_{i}+P_{iu}-p_{iu}\geq t_{j}+P_{jv}\), which is equivalent to:  
\[t_{j}-t_{i}\geq P_{iu}-P_{jv}+p_{jv}\text{ or }t_{i}-t_{j}\geq P_{jv}-P_{iu}+p_{iu} \tag{1}\]Using the above condition (1), the problem with the makespan criterion can be described as follows:  
\[\text{min}t_{n+1}\text{s.t.}t_{n+1}-t_{i}\geq L_{i}\text{ for all }i\in\{1,\ldots,n\} \tag{2}\]  
\[t_{i}\geq 0\text{ for all }i\in\{1,\ldots,n\} \tag{3}\]  
\[t_{j}-t_{i}\geq P_{iu}-P_{jp}+p_{jp}\text{ or }t_{i}-t_{j}\geq P_{jp}-P_{iu}+p_{iu} \text{for all }\{u,v\}\in\xi_{ij},i<j,i,j\in\{1,\ldots,n\} \tag{4}\]  
\(t_{n+1}\) is the start time of a dummy job, representing the makespan. Constraint (3) means that each job starts after time zero. Constraint (4) guarantees that the no-wait requirement is satisfied for any two jobs. Note that the number of constraint (4) is reduced by using \(i<j\) instead of \(i\
eq j\). For the above operation pair \(\{u,v\}\in\xi_{ij}\), let \(M_{k}\) denote the same machine of operations \(u\) and \(v\), then \(P_{iu}\), \(P_{ju}\), \(p_{ju}\), mean the same as \(P_{i}^{k}\), \(P_{j}^{k}\), \(P_{i}^{k}\), \(P_{j}^{k}\), respectively. Condition (1) can be rewritten as:  
\[t_{j}-t_{i}\in\left(-\infty,P_{i}^{k}-P_{j}^{k}-P_{i}^{k}\right]\cup\left[P_{ i}^{k}-P_{j}^{k}+P_{j}^{k},+\infty\right) \tag{5}\]  
For two jobs \(I_{i}\) and \(J_{j}\), if their start time difference \(t_{j}-t_{i}\) satisfies condition (5), then these two jobs do not conflict on machine \(M_{k}\). Obviously, the start times \(t_{i}\) and \(t_{j}\) are feasible if and only if jobs \(J_{i}\) and \(J_{j}\) do not conflict on all machines, which means that \(t_{j}-t_{i}\) satisfies condition (5) for all machines \(M_{k}\) (\(k=1,2,\ldots,m\)). Therefore, constraint (4) can be described as \(t_{j}-t_{i}\in F_{ij}\), where \(F_{ij}\) is an interval set with the feasible values of \(t_{j}-t_{i}\), obtained by:  
\[F_{ij}=\frac{k<m}{k=1}\left(-\infty,P_{i}^{k}-P_{j}^{k}-P_{i}^{k}\right]\cup \left[P_{i}^{k}-P_{j}^{k}+P_{j}^{k},+\infty\right) \tag{6}\]  
With the above notations, the NWJSP with the makespan criterion is further formulated as follows:  
\[\text{min}t_{n+1}\text{s.t.}t_{n+1}-t_{i}\geq L_{i}\text{ for all }i\in\{1,\ldots,n\} \tag{7}\]  
\[t_{i}\geq 0\text{ for all }i\in\{1,\ldots,n\} \tag{8}\]  
\[t_{j}-t_{i}\in F_{ij}\text{ for all }i<j,i,j\in\{1,\ldots,n\} \tag{9}\]  
\(L_{i}\) and all \(F_{ij}\) can be computed in advance. According to Equation (6), all \(F_{ij}\) can be computed in time \(O(n^{2}m\log m)\). \(F_{ij}\) is an interval set with at most \(m+1\) intervals. The existing effective approaches for the problem usually decompose it into the sequencing and timetabling sub-problems. The purpose of the sequencing sub-problem is to find a job sequence, denoted here as \(\pi^{*}=(\pi^{*}_{[1]},\ldots,\pi^{*}_{[m]})\), that generates a schedule minimizing the makespan. Clearly, the search space of the sequencing sub-problem