## 3 Variable Block Insertion Heuristic
### Initial Solution  
The initial solution for the VBIH algorithm is generated by the tPF_NEH(x) heuristic, which is proposed for the first time in this paper in the literature. It is a novel modification of the PF_NEH(x) heuristic presented in [PERSON] and [PERSON] (2016). In the PF_NEH(x) heuristic, the cost function to determine the next job to be scheduled is comprised of the total idle and blocking times. Note that the cost function devised for any constructive heuristic has a significant impact on the results. For this reason, [PERSON] et al. (2017) developed a PFT_NEH(x) heuristic for the BFSP with the makespan criterion, which was inspired from the PF_NEH(x) heuristic in [PERSON] and [PERSON] (2016). In (2017), a new cost function was devised by adding the departure time of the last job on the last machine to the total idle and blocking times. In this paper, we extend the PFT_NEH(x) heuristic to the total flowtime criterion and denote it as the tPF_NEH(x) heuristic. As in the PFT_NEH(x) heuristic, we consider the total idle and blocking times as a part of the cost function. In addition, we also consider the sum of the departure times on all machines of the last job that could be inserted into the partial sequence, which is one of the main contribution of this paper. To implement the tPF_NEH(x) heuristic, an initial order of jobs should be determined. To construct the initial order, we use the front delay and total processing times of each job as in [PERSON] et al. (2014). The following measure is employed to construct the initial order of jobs of jobs:  
\[iO(j)=\frac{2}{m-1}\left(\sum_{k=1}^{m}(m-k)p_{\pi_{j},k}\right)+\sum_{k=1}^{m }p_{\pi_{j},k} \tag{6}\]  
In order to establish the initial order of jobs, we sort the \(iO\left(j\right)\) values with an ascending order. Now, the number \(x\) of new sequences can be generated from the initial order of jobs as follows. Since the first job has an impact on the solution quality, the first job of the initial order is taken as the first job of the new sequence and the tPF_NEH(x) heuristic is applied to generate the new solution. Then, the second job of the initial order is taken as the first job of the new sequence and tPF_NEH(x)  
Figure 2: Variable block insertion heuristic. heuristic is applied to generate another new solution. This is repeated \(x\) times and the number \(x\) of new sequences will be generated. Of course, the best one amongst them is chosen as the initial solution for the VBIH algorithm. The proposed constructive heuristic can be summarized as follows. Suppose that \(\pi_{i-1}\) jobs have already been scheduled and a partial sequence, \(\pi=\{\pi_{1},\pi_{2},..,\pi_{i-1}\}\), is obtained. Clearly, job \(\pi_{i}\) will be the next job to be inserted into the partial sequence \(\pi_{i-1}\). It can be any job from all jobs in the set \(U\) of the unscheduled jobs. To select the job \(\pi_{i}\), we need a cost measure \((CM)\). For the BFSP with the total flowtime criterion, we propose a new cost function consisting of the total idle and blocking times as well as the sum of the departure times of job \(\pi_{i}\) on all machines. We first calculate the total idle and blocking time as follows:  
\[IT_{i}=\sum_{k=1}^{m}\left(d_{i,k}-d_{i-1,k}-p_{\pi_{i},k}\right) \tag{7}\]  
Then, we calculate the indexed sum of the departure times of job \(\pi_{i}\) on all machines as follows:  
\[SD_{i}=\sum_{k=1}^{m}\frac{md_{i,k}}{k+i\left(m-k\right)/\left(n-2\right)} \tag{8}\]  
Now, we define our cost function as follows:  
\[CM_{i}=\left(1-\mu\right)\times IT_{i}+\mu\times SD_{i} \tag{9}\]  
Note that we also employ an index function, \(m/\left(k+i\times\left(m-k\right)/\left(n-2\right)\right)\), to give a weight to departure time on each machine. Then, the job with the smallest sum of \(CM_{i}\) amongst all jobs in \(U\) is determined as the \(i\)th job to be inserted to the partial sequence \(\pi_{i-1}\). Figure 3 outlines the procedure of the proposed heuristic.