## 3 Variable Neighborhood Search (VNS) Algorithms
The job \(i\) and \(j\) are interchanged. #### 3.1.3 Neighborhood Operations for Truck Schedule

* Within single truck: A truck and a batch position \(r\) in the batch sequence of the truck are randomly selected. Another batch position \(s\) is randomly selected within the range [\(max(0\), \(r\)-gapBatch), min(\(r\)+gapBatch), current number of batches assigned to the truck)]. The interval gap between selecting batches is defined as \(gapBatch=n(B)\times preR\), where \(preR\) (\(0\leq preR\leq 1\)) is the predetermined relative interval ratio. * InsertOnTruck (gapBatch): The batch in the position \(r\) is removed and inserted to the position \(s\) in the batch sequence of the truck. * SwapOnTruck (gapBatch): The batches in the position \(r\) and \(s\) are interchanged in the batch sequence of the truck. * Across trucks: A truck \(k\) and a batch position \(r\) in the batch sequence of the truck \(k\) are randomly selected. Another truck \(l\) and batch position \(s\) in the batch sequence of the truck \(l\) are randomly selected within the range [\(max(0\), \(r\)-gapBatch), \(min(r\)+gapBatch\), current number of batches assigned to the truck \(l\)]]. * InsertAcrossTruck (gapBatch): The batch at the position \(r\) in the batch sequence of the truck \(k\) is removed and inserted to the position \(s\) in the batch sequence of the truck \(l\). * SwapAcrossTruck (gapBatch): The batch at the positions \(r\) and \(s\) are interchanged in the batch sequence of the associated trucks \(k\) and \(l\), respectively. In order to simultaneously determine machine schedule, batch assignment, and truck delivery schedule, a combination of the basic neighborhood operations for each decision would be examined in each iteration of the main VNS scheme. For the combination, the neighborhood operations for each decision are grouped, respectively, and an operation is randomly selected in each group when making a neighborhood. The grouped neighborhood structure is shown in Table 2.

### Local Search Scheme

For the local search in VNS algorithms, we used a search method based on sequence arrays (SMSA). To apply SMSA to the integrated scheduling problem, three sequence arrays were used, which are machine scheduling, batching, and truck scheduling arrays. The sequence arrays, which are represented by a single dimensional string array with digits, and those require assignment rules to determine manufacturing sequence of machines, batching construction, and shipping sequence of trucks. The digits for machine, batching, and truck scheduling represent a job sequence to apply to the machine assignment rule, the batching rule, and the truck assignment rule, respectively [21]. The decoding processes of the sequence arrays are carried out by the three rules. [PERSON] and [PERSON] [16] \begin{table}
\begin{tabular}{c c c} \hline \hline
**Group for Machine Schedule** & **Group for Batching** & **Group for Truck Schedule** \\ \hline \hline
[NONE, M1, M2, M3, M4] & [NONE, B] & [NONE, T1, T2, T3, T4] \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Grouped neighborhood structure. studied a similar problem (makespan problem) and compared the several assigning rules for their GA algorithm. The processing time and completion time-based assigning rules for machine and truck sequence arrays, and the minmax-based and rotation-based batching rules for batch sequence array were compared. They concluded that the completion time-based assigning rule for the machine and truck sequence arrays and the rotation-based batching rule for batch sequence array provided the best performance in terms of its effectiveness and efficiency for their algorithm. According to their result, we used three rules for decoding the sequence arrays to a compound solution for our local search scheme. The procedures of the three rules are as follows:

* **Machine assignment rule**: Calculate the completion times of each machine by temporarily assigning the current job to the end of the sequence in the corresponding machine.