## 3 Meta-Heuristic Algorithms
### IG Algorithms
In Algorithm 4, job \(\pi_{k}\) at position \(k\) is randomly chosen from the solution \(\pi\) without repetition, and partial solution \(\pi_{p}\) is obtained. Then, job \(\pi_{k}\) is inserted into all possible positions of the partial solution \(\pi_{p}\). When the best-improving insertion position is found, job \(\pi_{k}\) is inserted into that position, and a complete solution \(\pi^{*}\) is obtained. These steps are repeated for all jobs. If an improvement is found, the local search is rerun again until no better solution is obtained. ``` for\(i=1\) to \(n\) do \(\pi_{p}=\mathit{Remove job}\)\(\pi_{k}\) from solution \(\pi\) randomly and without repetition \(\pi^{*}=\mathit{Insert}\mathit{loblnBestPosition}(\pi_{p},\,\pi_{k})\) if\((f(\pi^{*})<f(\pi))\) then do \(\pi=\pi^{*}\) endif endfor return \(\pi\) and \(f(\pi)\) ```
**Algorithm 4** First improvement insertion neighborhood(\(\pi\))  
Recently, a new \(\mathrm{IG_{ALL}}\) algorithm has been presented in the literature [5] with excellent results for the PFSP with makespan minimization. The difference between \(\mathrm{IG_{ALL}}\) and \(\mathrm{IG_{RS}}\) is that \(\mathrm{IG_{ALL}}\) applies an additional local search to partial solutions after destruction, which substantially enhances solution quality. In the \(\mathrm{IG_{RS}}\) algorithm, local search is applied to the complete solution after the construction phase to improve the current candidate solution whereas, in \(\mathrm{IG_{ALL}}\) algorithm, local search is applied to a partial solution after destruction phase. This idea is applied in heuristic algorithms by Reference [39]. They study on vehicle routing problem and apply local search on the routes in the construction phase. Applying local search to the partial solution is more advantageous in terms of computational time and providing different search directions. Due to having a partial solution, a local search is applied to the smaller size of the complete solution so that the search procedure can be conducted quickly. Another difference between \(\mathrm{IG}_{\mathrm{RS}}\) and \(\mathrm{IG}_{\mathrm{ALL}}\) is due to the fact that the initial solution is constructed by FRB5 heuristic. The pseudo code of \(\mathrm{IG}_{\mathrm{ALL}}\) algorithm is presented in Algorithm 5. ```
\(\pi=\mathrm{FRB5}\) \(\pi^{\text{best}}=\pi\)  While (NotTermination) do \(\pi_{D}=\text{Destruction}(\pi)\) \(\pi_{p}=\text{LocalSearchToPartialSolution}(\pi_{p})\) //Algorithm 4 \(\pi^{1}=\text{Construction}(\pi_{p},\pi_{D})\) \(\pi^{1}=\text{LocalSearchToCompleteSolution}(\pi^{1})\) //Algorithm 4 if\(f(\pi^{1})\leq f(\pi)\)then do \(\pi=\pi^{1}\) if\(f(\pi^{1})<f(\pi^{\text{best}})\)then do \(\pi^{\text{best}}=\pi^{1}\) endif else if\((r<\text{exp}\{-(f(\pi^{1})-f(\pi))/T\})\) \(\pi=\pi^{1}\) endif endwhile return\(\pi^{\text{best}}\) and \(f(\pi^{\text{best}})\) endprocedure
```
**Algorithm 5**\(\mathrm{IG}_{\mathrm{ALL}}\) algorithm  
Note that Algorithm 3 is used in the FRB5 heuristic in order to construct the initial solution with a single run due to its deterministic property. In both algorithms, Algorithm 4 is employed in applying local search to both partial and complete solutions.