## 3 Meta-Heuristic Algorithms
### Variable Block Insertion Algorithm  
In this paper, we propose a VBIH algorithm as follows. The VBIH algorithm employs the FRB5 heuristic as an initial solution. It has a minimum block size \((b_{min})\), and a maximum block size \((b_{max})\). It removes a block of jobs \((\pi_{b})\) with size \(b\) from the current solution and obtains a partial solution \((\pi_{p})\). Similar to the \(\mathrm{IG}_{\mathrm{ALL}}\) algorithm, it applies the local search in Algorithm 4 to the partial solution. Then, it makes a number, \(n-b+1\), of block insertion moves sequentially in the partial solution. It chooses the best one amongst those solutions from block insertion moves. Well-known RIS local search in the literature is applied to the complete solution found after block insertion moves. If the new solution obtained after the local search is better than or equal to the current solution, it replaces the current solution. As long as it improves, it retains the same block size (_i.e._, \(b=b\)). Otherwise, the block size is incremented by one (_i.e._, \(b=b+1\)) and a simulated annealing-based acceptance criterion, similar to \(\mathrm{IG}_{\mathrm{RS}}\) and \(\mathrm{IG}_{\mathrm{ALL}}\) algorithms, is employed to accept the new solution to escape from local minima. This process is repeated until the block size reaches its maximum limit (_i.e._, \(b\leq b_{max}\)). The outline of the VBIH algorithm is given in Algorithm 6. Note that \(\pi^{R}\) is the reference sequence; \(tP\) is temperature parameter for the acceptance criterion and \(r\) is a uniform random number between 0 and 1. ```
\(\pi=FRB5\) \(\pi^{\text{best}}=\pi\) \(\pi^{\text{best}}=\pi^{\text{best}}\) while(NotTermination) \(b=b_{min}=2\) do \(\pi_{b}=Remove\ block\ \pi_{b}\ from\ \pi\) \(\pi_{p}=LocalSearchToPartialSolution(\pi_{p})\) //Algorithm 4 \(\pi^{1}=InsertBlockInBestPosition(\pi_{p},\pi_{b})\) \(\pi^{1}=RISLocalSearchToCompleteSolution(\pi^{1})\) //Algorithm 5 \(if\ (f(\pi^{1})<f(\pi))\) then do \(\pi=\pi^{1}\) \(b=b\) if\ ((f(\pi^{1})<f(\pi_{best}))\)then do \(\pi^{\text{best}}=\pi^{1}\) \(\pi^{\text{best}}=\pi^{\text{best}}\) endif else \(b=b+1\) if\ ((\ r<exp\{-(f(\pi^{1})-f(\pi))/T\})\) \(\pi=\pi^{1}\) endif \(\text{endif}\) while\(((b\leq b_{max})\) endwhile return\(\pi^{\text{best}}\) and \(f(\pi^{\text{best}})\)
```  
**Algorithm 6**VBIH algorithm  
To explain the block insertion procedure, we give the following example. Suppose that we are given a current solution \(\pi=\{1,\ 2,\ 3,\ 4,\ 5\}\). Furthermore, assume that the block size is \(b=2\). Let's randomly choose a block \(\pi_{b}=\{2,\ 5\}\), thus ending up with a partial solution, \(\pi_{p}=\{1,\ 3,\ 4\}\). After applying local search to the partial solution \(\pi_{p}\), suppose that we have a partial solution \(\pi_{p}=\{3,\ 1,\ 4\}\). Now, the block \(\pi_{b}\) is inserted into four positions as follows: \(\pi^{1}=\{2,\ 5,\ 3,\ 1,\ 4\}\), \(\pi^{2}=\{3,\ 2,\ 5,\ 1,\ 4\}\), \(\pi^{3}=\{3,\ 1,\ 2,\ 5,\ 4\}\) and \(\pi^{4}=\{3,\ 1,\ 4,\ 2,\ 5\}\). Among these four solutions, the best one will be chosen as a final solution. Regarding the local search algorithm that will be applied only to complete solutions, we use a well-known referenced insertion scheme local search, RIS [8; 40]. RIS is guided by a reference solution \(\pi^{R}\), which is the best solution obtained so far during the search process. For instance, if the reference solution is given by \(\pi^{R}=\{3,\ 5,\ 1,\ 4,\ 2\}\) and the current solution by \(\pi=\{1,2,3,4,5\}\). The reference solution \(\pi^{R}\) implies that job 3 in the current solution \(\pi\) might not be in a proper position. For this reason, the RIS local search first removes job 3 from the current solution \(\pi\) and inserts it into all possible slots of the partial solution \(\pi_{P}\). A new solution with the best insertion slot is replaced by the current solution, and the iteration counter is reset to one if any improvement occurs. Otherwise, the iteration counter is incremented by one.