# No-Wait Job Shop Scheduling Using a Population-Based Iterated Greedy Algorithm
## 3 Population-Based Iterated Greedy Algorithm
### Initialization  
Since the PBIG is a pullulation-based algorithm, there is a population with \(p\) solutions evolving in the algorithm. Each solution is performed with the IG procedure. The Nawaz-Enscore-Ham (NEH) heuristic ([PERSON] et al. (2018)) has been shown to be one of the most effective heuristics for flow shop problems, and it has been extensively utilized to generate initial solutions for metaheuristics for the flow shop problems. The NEH heuristic firstly sequences the jobs in non-increasing order of the total processing time on all the machines. Then it constructs a partial solution by taking into consideration the first two jobs. Finally, a complete solution is constructed by inserting these jobs one by one into the current partial solution.  
To adapt the NEH heuristic for NWJSP, the evaluation of a partial sequence in NWJSP is different from that in PFSP. For a partial sequence, here the timetabling method is applied to construct a partial time table as a partial solution. With this, the NEH heuristic is described as follows.  
Step 1: sequence the jobs in non-increasing order of the total processing time on all the machines and obtain a priority job order \(\rho=(\rho_{[1]},\ldots,\rho_{[n]})\). Let partial sequence \(\sigma=(\rho_{[1]})\) and \(k=2\).  
Step 2: insert job \(\rho(k)\) to all the possible \(k\) positions of \(\sigma\) and obtain \(k\) tentative partial sequences. Evaluate these partial sequences by applying the timetabling method, replace \(\sigma\) with the partial sequence that results in the minimum makespan.  
Step 3: Let \(k=k+1\). If \(k\leq n\), go to step 2; otherwise \(\sigma\) is the final permutation.  
To employ the NEH heuristic to generate a random solution with good quality, we use a random job permutation as job order in the first step, and develop a variant of the NEH heuristic, called NEH_RAN. It should be noted that both the left timetabling and inverse left timetabling methods can be used in the above NEH heuristic and its variants. In other words, the heuristic can be applied with the left timetabling for the original instance to obtain a solution, and it can also be applied with the inverse timetabling for the inverse instance to obtain another solution.  
To take advantage of both the left timetabling and inverse left timetabling methods, both methods are applied in the \(p\) IG procedures. A bool vector \(m_{d}=(m_{d}(1),\ldots,m_{d}(p))\) is designed to indicate the timetabling method for the \(p\) IG procedures. \(m_{d}(k)=\textit{true}\) means that the \(k\)-th IG procedure is performed with the left timetabling, otherwise it is performed with the inverse left timetabling. \(m_{d}\) is initialized in a form of \((\textit{true},\textit{false},\textit{true},\textit{false},\ldots)\). Then, the \(p\) initial solutions of the \(p\) IG procedures are initialized as follows.  
The first is initialized by the NEH heuristic using the left timetabling, and the second is initialized by the NEH heuristic using the inverse left timetabling. The remaining \(p-2\) initial solutions are initialized by the NEH_RAN using the inverse left timetabling (if the \(m_{d}(k)\) value is _true_) or using the inverse left timetabling (if the \(m_{d}(k)\) value is _false_). Such an initialization strategy not only takes advantage of both the timetabling methods, but also constructs the initial start solutions with both quality and diversity.