## 3 Variable Block Insertion Heuristic  
Traditional local search algorithms are based on swap and insertion neighborhood structures. The swap operator exchanges two jobs in a sequence, whereas the insertion operator removes a job from a sequence and inserts it into another position in the sequence. Recently, local search algorithms, which are based on block moves, are presented for the single machine scheduling problem in the literature. A block move of 2-edge exchange was presented in [PERSON] and [PERSON] (2013). Then, [PERSON] et al. (2014) developed five different neighborhoods: swap, insertion, edge-insertion, 3-block insertion and 3-block reverse. The basic idea is to use larger neighborhood move operators rather than the swap and insertion move operators. Relying on this idea, [PERSON] et al. (2015) presented a neighborhood structure called a _Block Move_ in which \(l\) consecutive jobs (called a block) are inserted into another position in the sequence. They represent a block move by a \(triplet\ (i,\ k,\ l)\), where \(i\) represents the position of the first job of the block, \(k\) denotes the target position of the block to be inserted and \(l\) represents the size of the block. Note that one edge insertion, two edge-insertion and 3-block insertion corresponds to the block move neighborhoods with \(l=1\), \(l=2\), and \(l=3\). Similarly, [PERSON] and [PERSON] (2016) developed a variable neighborhood descent algorithm by using three block move neighborhoods were developed and used in a memetic algorithm.  
Inspiring from the algorithms above, we propose a similar, but a different block insertion heuristic, which we call it a variable block insertion heuristic (VBIH) algorithm. We denote two block sizes as \(bS_{min}\) and \(bS_{max}\), where \(bS_{min}\) is the minimum block size and \(bS_{max}\) is the maximum block size. In addition, we define a block move insertion size with a maximum insertion move size denoted as \(mS_{max}\). The VBIH algorithm removes a block of jobs with size, \(bS\), from the current sequence starting from \(bS_{min}=1\), then it makes a number \(mS_{max}\) of block insertion moves randomly in the partial sequence, which we denote it as the block insertion move procedure, \((bIM())\). It chooses the best one amongst a number \(mS_{max}\) of block insertion moves. The sequence obtained after \(bIM()\) procedure goes under a variable local search \((VLS)\), which is based on traditional insertion and swap neighborhood structures. If the new sequence obtained after the \(VLS\) local search is better than the current sequence, it replaces the current sequence. As long as it improves, it keeps the same block size, i.e., \(bS=bS\). Otherwise, the block size is incremented by one, i.e., \(bS=bS+1\) and a simulated annealing type of  
Figure 1: \(f_{fast}\left(\pi,pos1\right)\) function.  
acceptance criterion is used to accept the inferior solution in order to escape from local minima. This process is repeated until the block size reaches at the maximum block size, i.e., \(bS\leq bS_{max}\). The outline of the VBIH algorithm is given in Figure 2. Note that \(\pi^{R}\) is the reference sequence; \(T\) is temperature parameter for the acceptance criterion, and tPF_NEH(x) is a constructive heuristic providing an initial sequence to the VBIH algorithm. They will be explained in detail in the subsequent sections.