## 3 Variable Neighborhood Search (VNS) Algorithms
And then, find the machine with the shortest completion time is found and the job is permanently assigned to the machine and placed on the end-position of the manufacturing sequence of the machine. * **Batching rule**: Find the first available batch, allowing the capacity of the batch to be greater than the volume of the job, as well as shipping towards the same customer and assigning the job to the batch. If no batch was satisfied by the conditions from the current available batches, create a new batch and assigned the job to the batch. * **Truck assignment rule**: Calculate the completion times of each truck by temporarily assigning the current batch to the end of the sequence in the corresponding truck. And then, find the truck with the shortest completion time and the batch was permanently assigned to the truck and placed on the end-position of the shipping sequence of the truck. For the local search with SMSA, we classified seven modification cases according to which sequence arrays were selected to apply the modification (see Table 3). Cases 1, 2, and 3 applied only one sequence array to the modification process and cases 4, 5, and 6 applied two of three sequence arrays to the modification process. Case 7 applies all three sequence arrays to the modification process. One of seven cases is randomly chosen according to the case selection probability \(P_{c}\) in every iteration of the local search with SMSA. In this article, we developed two kinds of procedures for the local search with SMSA. The difference between two procedures is to update whether the case selection probabilities are used or not when the modification of sequence array is processed. The first local search uses the static even case selection probability with the value 1/(the number of modification cases). The second local search uses the dynamic case selection probability, which is increased when the case is selected and decreases with a deterioration rate when the case is not selected. Three sequence operators for the modification of sequence array in SMSA were used. For the operators, two front and rear positions were randomly selected in the original sequence array. * **Pull operator**: All digits between two positions (including the digits in the positions) are removed and placed to the end of the sequence array and the digits on the right side of the rear position are pulled to the position of the front point. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline  & \multicolumn{4}{c}{**Modify or Not**} & \multicolumn{4}{c}{**Modify or Not**} \\ \cline{2-9}
**Case** & \begin{tabular}{c} **Machine** \\ **Sequence** \\ **Array** \\ \end{tabular} & \begin{tabular}{c} **Batch** \\ **Sequence** \\ **Array** \\ \end{tabular} & \begin{tabular}{c} **Truck** \\ **Sequence** \\ **Array** \\ \end{tabular} & \begin{tabular}{c} **Case** \\ **Sequence** \\ **Array** \\ \end{tabular} & \begin{tabular}{c} **Machine** \\ **Sequence** \\ **Array** \\ \end{tabular} & \
\begin{tabular}{c} **Batch** \\ **Sequence** \\ **Array** \\ \end{tabular} &
\begin{tabular}{c} **Truck** \\ **Sequence** \\ **Array** \\ \end{tabular} \\ \hline
1 & O & X & X & 4 & O & O & X \\
2 & X & O & X & 5 & X & O & O \\
3 & X & X & O & 6 & O & X & O \\  & & & & 7 & O & O & O \\ \hline \hline \end{tabular}
\end{table} 
Table 3: The modification cases. * **Insert operator**: The digit in the rear position is removed and simply inserted into the position in front of the digit in the front position. * **Swap operator**: The two digits at the front position and the rear position are mutually interchanged. The pseudo codes of two local search procedures with SMSA are given in Algorithm 2 and 3 as follows:

```
Begin  Define termination count \(t_{max}\). Define number of modification cases \(C_{max}\)  Let the initial case selection probability \(P_{c}\gets 1/C_{max}\). Find an initial sequence arrays \(C^{*}\) encoded from the solution set \(S\). Let current local optimum \(S^{\prime}\gets S\). Let iteration index \(t\gets 1\).