## 3 Variable Block Insertion Heuristic
### Variable Local Search  
The traditional variable neighborhood search (VNS) algorithm was developed in [48] and successfully applied to scheduling problems in [49; 50; 51; 52; 53]. Very recently, a variable local search (VLS) algorithm is developed by [PERSON] et al. [32; 40; 41]. The VLS algorithm is a novel and different from the traditional VNS algorithms in such a way that when a sequence is improved by any randomly chosen neighborhood structure, it switches to another neighborhood structure. For example, if a sequence is improved by the LS1 local search (i.e., swap neighborhood), it systematically switches to LS2 local search (i.e., insertion neighborhood), which is the difference between traditional VNS and VLS algorithms. As seen in Figure 6, if a sequence is improved by the local search type \"\(LS\)\", it switches to \(LS=1-LS\). Suppose that the \(LS\) is randomly chosen as 1, then if the sequence is improved by the insertion neighborhood, the variable local search type is switched to 0 by \(LS=1-1=0\). This is different from the traditional VNS algorithms, where if a neighborhood improves, that neighborhood is kept for the search process and it switches to the second neighborhood if it fails, which is a common sense to follow. Note that, at least one time, both neighborhoods are ensured to be applied by using a _Counter_. The VLS local search is given in Figure 6.  
Figure 5: Block insertion procedure.  
Figure 6: Variable local search (VLS) algorithm.  
Note that the VLS algorithm employs two powerful local search algorithms in the VBIH algorithm, namely, referenced insertion scheme (RIS) and referenced swap scheme (RSS). Briefly, in the VLS algorithm, the RIS local search is used as LS1 whereas the RSS local search is employed as LS2. The RIS and RSS local search algorithms are outlined in Figures 7 and 8, respectively.  
The RIS local search is an insertion local search neighborhood. The details can be found in [47; 54; 55; 56; 57; 58; 59]. Note that the fast fitness calculation is used in the RIS local search.  
\[\begin{array}{c}\textit{Procedure}\;RSS\big{(}\pi,\pi^{\pi},f(\pi)\big{)}\\ \textit{Counter}=1\\ pos=1,pt1=-1,pt2=-1\\ \textit{while}(\textit{Counter}\leq n)\textit{do}\\ k=1\\ \textit{while}\left(\pi_{x}!=n_{pos}^{\pi}\right)k=k+1;\textit{endwhile}\\ pos=(pos+1)(mod)n\\ \textit{update}\;D_{j,k}\;\textit{matrix},\;i=1,..,n;k=1,..,..m\\ \textit{for}\;i=0,t\;n\\ \textit{endfor}\;i=1,..,n-1;k=1,..,m\\ \textit{for}\;i=0,t\;n\\ \textit{endfor}\\ \textit{endfor}\\ \textit{endfor}\\ \textit{return}\;\pi\;\textit{and}\;f(\pi)\]  
Figure 8: Referenced swap scheme (RSS) local search.  
Figure 7: Referenced insertion scheme (RIS) local search.  
As seen in Figure 8, the RSS local search designates the job to be swapped by using the reference sequence \(\pi^{R}\) as in the RIS algorithm. Then, for each job \(\pi_{k}\), it exchanges job \(\pi_{k}\) with each \(\pi_{i}\) until the last job in the sequence. As long as the sequence improves after a number \(n\) of swap moves, the counter is fixed to 1 so that the search starts from the beginning again. Note that the fast fitness calculation is used in RSS local search, too.  
After the local search phase, it should be decided if the new sequence is accepted as the incumbent sequence for the next iteration. A simple simulated annealing type of acceptance criterion is used with a constant temperature, which is suggested by [PERSON] and [PERSON] (2006), as follows:  
\[T=\frac{\sum_{j=1}^{n}\sum_{k=1}^{m}p_{j,k}}{10\times n\times m}\times\tau P \tag{10}\]  
where \(\tau P\) is a parameter to be adjusted.