## 3 Meta-Heuristic Algorithms
### IG Algorithms  
IG algorithms mainly have four components; namely, initial solution, destruction-construction (DC) procedure, local search, and acceptance criterion. The traditional IGR is proposed by [4]. In this algorithm, the initial solution is constructed by the NEH heuristic in [37]. In the destruction step, \(dS\) jobs are randomly removed from the solution \(\pi\) without repetition and stored in \(\pi_{D}\). The remaining jobs are also stored in \(\pi_{P}\) that represents the partial solution. In the construction step, each job in \(\pi_{D}\) is inserted into the partial solution \(\pi_{P}\), in the order in which they were removed, until a complete solution of \(n\) jobs is constructed. Having carried out the destruction and construction procedure, a local search is employed to further enhance solution quality. After a local search, if the solution is better than or equal to the incumbent solution, it is accepted. Otherwise, it is accepted with a simple simulated annealing-type acceptance criterion, which is suggested by [38]:  
\[T=\frac{\sum_{j=1}^{n}\sum_{k=1}^{m}p_{kj}}{10 nm}\times\tau P \tag{17}\]  
where \(\tau P\) is a parameter to be adjusted. The pseudo-code of the traditional IGR is given in Algorithm 1, where \(r\) is a uniform random number between 0 and 1. ```
\(\pi=NEH\) \(\pi^{\text{best}}=\pi\) while(NotTermination) do \(\pi_{D}=\text{Destruction}(\pi)\) \(\pi^{1}=\text{Construction}(\pi_{D},\pi_{P})\) \(\pi^{1}=\text{LocalSearch}(\pi^{1})\) // Algorithm 4 \(\pi=\pi^{1}\) if \((f(\pi^{1})\leq f(\pi))\)then \(\pi^{\text{best}}=\pi^{1}\) endif elseif \((r<\text{exp}\{-(f(\pi^{1})-f(\pi))/T\})\) then \(\pi=\pi^{1}\) endif endwhile return\(\pi^{\text{best}}\) and \(f(\pi^{\text{best}})\)
```  
**Algorithm 1**Traditional IGR algorithm  
The IGR algorithm for the PFSP under makespan minimization employs an initial solution generated by the NEH heuristic. In addition, the NEH heuristic was extended to the FRB5 heuristic with a local search on the partial solutions [39]. Both heuristics are simple and very effective for minimizing the makespan, and its pseudo-code is given in Algorithm 2. In the first phase, the sum of the processing times on all machines are calculated for each job. Then, jobs are sorted in decreasing order to obtain \(\delta\). In the second phase, the first job in \(\delta\) is selected to establish a partial solution \(\pi_{1}\). The remaining jobs in \(\delta\) are inserted in the partial solution one by one. After each iteration, optionally, a local search is applied to the partial solution. Local search is implemented as long as the partial solution is improved. After having inserted all jobs, a complete solution is obtained. Note that the NEH heuristic is denoted as FRB5 heuristic with an optional local search to partial solutions. ```
**Algorithm 2** NEH and FRB5 constructive heuristics

The \(\mathrm{IG_{RS}}\) algorithm employs insertion neighborhood structure as a local search after destruction and construction procedure. Insertion neighborhood is very effective with the speed-up method explained in Section 3.1 for makespan minimization. Insertion neighborhood can be deterministic or stochastic depending on the decision of choosing a job from solution to be removed. The deterministic variant is given in Algorithm 3. This procedure removes \(\pi_{i}\) from the solution \(\pi\) and inserts it into all possible positions of the incumbent solution \(\pi\). When the best-improving insertion position is found, job \(\pi_{i}\) is inserted into that position. These steps are repeated for all jobs. If an improvement is observed, the local search is re-run until no better solution is obtained. ``` for\(i=1\) to \(n\) do \(\pi^{*}=\mathit{Insert}\mathit{loblnBestPosition}(\pi,\,\pi_{i})\) if\((f(\pi^{*})<f(\pi))\) then do \(\pi=\pi^{*}\) endif endfor return \(\pi\) and \(f(\pi)\) ```
**Algorithm 3** First improvement insertion neighborhood(\(\pi\))  
In the stochastic variant given in Algorithm 4, jobs are randomly chosen from solutions to make insertions.