## 3 Variable Neighborhood Search (VNS) Algorithms  
We develop VNS algorithms to solve the integrated scheduling problem efficiently. The VNS algorithm is designed to enrich the search space by restarting a local search heuristic with randomly generated neighborhood solutions from an incumbent solution by a pre-determined set of neighborhood structures. Systematic changes of the neighborhood solution within the local search is a key concept of VNS algorithms to improve a solution quality. Thus, the performance of VNS algorithm is mainly influenced by the local search heuristic and the neighborhood structure to meet problem characteristics [20]. The basic VNS algorithm starts with a randomly generated initial solution and repeats the shaking and moving steps until the termination condition (maximum neighborhood number) is met. In the shaking step, a neighbor of the incumbent solution is randomly generated, and the local search heuristic is performed. After the shaking step, the incumbent solution is compared with the local optimal solution and updates the incumbent solution when the local optimal solution is better. Algorithm 1 shows the procedure of the basic VNS scheme given as follows:```
BeginFind an initial solution set \(S^{*}\). Let iteration index \(k\gets 1\). Define maximum neighborhood number \(k_{max}\). While(\(k\leq k_{max}\)) Shaking: find a random solution set \(S\in N_{k}(S^{*})\). Perform a local search with \(S\) to find a local optimum \(S^{\prime}\). Move or not: If\(f(S^{\prime})\leq f(S^{*})\)then\(S^{*}\gets S^{\prime}\). \(k\gets 1\). Else \(k\gets k+1\). End If End While End
```

**Algorithm 1** Basic VNS scheme

### Neighborhood Structure

A solution of the integrated scheduling problem is represented by three sequences in this article: a job sequence for each machine, a job sequence for each batch, and a batch sequence for each truck. The example solution of the integrated schedule in Figure 1 is represented as shown in Figure 2.

The neighborhood solutions are generated by operations describing how they change the incumbent solution. In this article, we use the following nine basic neighborhood operations, for machine schedule (M1, M2, M3, M4), batching (B1), and truck schedule (T1, T2, T3, T4):

#### 3.1.1 Neighborhood Operations for Machine Schedule

* Within single machine: A machine and a job position \(p\) in the job sequence of the machine are randomly selected. Another job position \(q\) is randomly selected within the range [_max\((0,p\)-gap\()\) job_], _min\((p\)+gap\()\) job_, current number of jobs assigned to the machine)]. The interval gap between selecting jobs is defined as _gap\(\mathit{job}=n(I)\times\mathit{preR}\)_, where \(\mathit{preR}\)\((0\leq\mathit{preR}\leq 1)\) is the predetermined relative interval ratio. M1. InsertOnMachine (_gap\()\)_: The job at the position \(p\) is removed and inserted to the position \(q\) in the job sequence of the machine. M2. SwapOnMachine (_gap\()\)_: The jobs at the positions \(p\) and \(q\) are interchanged in the job sequence of the machine. * Across machines: A machine \(m\) and a job position \(p\) in the job sequence of the machine \(m\) are randomly selected. Another machine \(n\) and job position \(q\) in the job sequence of the machine \(n\) are randomly selected within the range [_max\((0,p\)-gap\()\)_], _min\((p\)+gap\()\)_, current number of jobs assigned to the machine \(n\))]. Figure 2: A solution representation for the integrated scheduling problem. * _InsertAcrossMachine (gapJob)_: The job at the position \(p\) in the job sequence of the machine \(m\) is removed and inserted to the position \(q\) in the job sequence of the machine \(n\). * SwapAcrossMachine (gapJob): The job at the positions \(p\) and \(q\) are interchanged in the associated job sequence of the machines \(m\) and \(n\), respectively. #### 3.1.2 Neighborhood Operations for Batching

* _SwapAcrossBatch_(): Two batches and job \(i\) and \(j\) in each batch are randomly selected with checking the feasibility of the truck capacity.