# No-Wait Job Shop Scheduling Using a Population-Based Iterated Greedy Algorithm
## 2 No-Wait Job Shop Scheduling Problem (NWJSP) with Makespan Minimization
### Timetabling Methods  
There are several timetabling methods to determine a feasible schedule from a provided job permutation. The combinations of different timetabling methods and different sequencing algorithms are extensively studied by [PERSON] et al. (2015). They found that complicated methods are not necessarily superior to simple methods, and some simpler methods prove to be more effective. [PERSON] et al. (2016) investigated several timetabling methods for the problem with total flow time criterion and found that the left timetabling and inverse left timetabling methods are more effective when the algorithm for the sequencing problem is run with the same computational efforts. In the left timetabling method, we set \(t_{[1]}=0\), and compute the minimum \(t_{[i]}\) successively for \(i=2\),..., \(n\), subjected to (1) \(t_{[i]}\geq 0\) and (2) \(\pi_{[i]}\) does not conflict with \(\pi_{[i]}\) for all \(j<i\). The inverse left timetabling method is the same as the left timetabling method except that it is performed on the inverse instance. The inverse left timetabling method is based on the fact that a solution for the inverse instance is also applicable for the original instance (see more in [PERSON] (2013) and [PERSON] et al. (2015)).  
As stated above, \(t_{j}-t_{i}\in F_{i,j}\) means the start times of \(J_{j}\) and \(J_{i}\) are feasible. Let \(S_{i,j}=[0,+\infty)\cap F_{i,j}\), then \(t_{j}-t_{i}\in S_{i,j}\) means the start times of \(J_{j}\) and \(J_{i}\) are feasible and \(J_{j}\) starts not earlier than \(J_{i}\). All \(F_{i,j}\) and \(S_{i,j}\) can be computed in advance with time complexity \(O(n^{2}m\log m)\). Without loss of generality, assume that the permutation is \(\pi=(J_{1},J_{2},\ldots,J_{n})\). The left timetabling of \(\pi\) utilizes all the precomputed \(S_{1,j}\) (\(1<j\)) and \(F_{i,j}\) (\(1<i<j\)). First let \(t_{1}=0\). Then \(t_{j}\) is computed successively from \(j=2\) to \(j=n\). For job \(J_{j}\), with the already computed \(t_{i}\) (\(i<j\)), the steps to compute \(t_{j}\) is designed as follows.  
Step 1: set \(t_{j}-t_{1}\) as the minimum value that satisfies the first interval of \(S_{1,j}\).  
Step 2: check \(F_{i-1,j}\),..., \(F_{2,j}\), \(S_{1,j}\) successively. When checking \(F_{i,j}\) (\(i>1\)) or \(S_{i,j}\) (\(i=1\)), if the incumbent \(t_{j}-t_{i}\) does not satisfy any interval of \(F_{i,j}\) (\(i>1\)) or \(S_{i,j}\) (\(i=1\)), augment \(t_{j}\) to make it satisfied and then check \(F_{i-1,j}\),..., \(F_{2,j}\), \(S_{1,j}\) successively again. This step is repeated until \(t_{j}-t_{i}\) satisfies all the \(F_{i-1,j}\),..., \(F_{2,j}\), \(S_{1,j}\).  
Since there are at most \(m+1\) intervals in \(F_{i,j}\) or \(S_{i,j}\), when the worst case happens, to compute \(t_{j}\) needs time complexity \(O(m\eta^{2})\), and to compute all the \(t_{j}\) (\(j=1,\)..., \(n\)) needs time complexity \(O(mn^{3})\), which results in the worst case time complexity \(O(mn^{3})\) for the left timetabling. According to [PERSON] et al. (2016), the above procedure is effective for the left timetabling method and inverse left timetabling method.