# An Improved Variable Neighborhood Search for the Reconfigurable Assembly Line Reconfiguring Problem
## 5 Proposed IVNS-RALRP
### Solution Evaluation
If predecessor nodes exit, the process precedence constraint are not satisfied, and the partial solution \(NALO\) is deemed invalid. Line 5 to 7 remove the checked operation nodes (decrementing the indegree of successor operation nodes). If all operations pass the legal check, then every operation in the sequence represented by \(NALO\) satisfies the process precedence constraint denoted by \(G\), and Line 9 outputs 'True'. ```
Data: Product-process-resource information \(G\) with Data Structure 1, operations of new assembly line \(NALO\), the in-degree of all operations \(inDegree\). Result:Bool\(flag\). 1 for\(i=1\) to \(n\)do
2 if\(inDegree[NALO_{i}]\
eq 0\)then
3 return\(flag\)= False;
4
5 end if
6 for\(j\) in \(S_{NALO_{j}}\)do
7\(inDegree[j]\gets inDegree[j]-1\);
8
9 end if
10
11 end for return\(flag\)= True;
```
**Algorithm 4**isLegal

### Shaking

VNS method is applied to find more promising solutions in the solution space through changing neighborhood structures during the search process. Since a neighborhood is usually defined based on moves of operation, the search process can benefit much from suitably selected moves. This paper proposes new problem-specific neighborhood structures \(\mathcal{N}_{k}(k=1,2,3,4,5)\), as illustrated in Figure 5. The neighborhood structures include: Swap operation between the \(i\)th operation and the 1 th operation following it (\(swap_{1}(i)\)). Swap operation between the \(i\)th operation and the 2 th operation following it (\(swap_{2}(i)\)). Swap operation between the \(i\)th operation and the 3 th operation following it (\(swap_{3}(i)\)). Insert operation from the \(i\)th operation to the 3 th operation following it (\(insert_{3}(i)\)). Insert operation from the \(i\)th operation to the 4 th operation following it (\(insert_{4}(i)\)). Neighborhood change about swap operation and insert operation can transform the partial solution \(NALO\) into all possible partial solutions. The changes in neighborhoods are as follows:

1. \(\mathcal{N}_{1}:swap_{1}(i)\): randomly select an integer \(i\) (\(1\leq i\leq m-1\)) and swap the positions of the \(i\)th operation and the \((i+1)\)th operation in the partial solution \(NALO\) of operations. 2. \(\mathcal{N}_{2}:swap_{2}(i)\): randomly select an integer \(i\) (\(1\leq i\leq m-2\)) and swap the positions of the \(i\)th operation and the \((i+2)\)th operation in the partial solution \(NALO\) of operations. 3. \(\mathcal{N}_{3}:swap_{3}(i)\): randomly select an integer \(i\) (\(1\leq i\leq m-3\)) and swap the positions of the \(i\)th operation and the \((i+3)\)th operation in the partial solution \(NALO\) of operations. 4. \(\mathcal{N}_{4}:\mathit{insert}_{3}(i)\): randomly select an integer \(i\) (\(1\leq i\leq m-3\)) and insert the \(i\)th operation into the position of the \((i+3)\)th operation in the partial solution \(NALO\) of operations. 5. \(\mathcal{N}_{5}:\mathit{insert}_{4}(i)\): randomly select an integer \(i\) (\(1\leq i\leq m-4\)) and insert the \(i\)th operation into the position of the \((i+4)\)th operation in the partial solution \(NALO\) of operations. ### Local Search

Local search is an important component to enhance the optimization performance of IVNS-RALRP. In each iteration, a new partial solution is generated from the current partial solution \(NALO\) by applying the aforementioned neighborhood changes. Then, local search is employed to complete resource selection and obtain the final locally optimal solution \(NAL\). The description of local search is shown in Algorithm 5. 1. The first two lines initialize the parameters. 2. Line 3 to 26 conduct iterative local search. The stopping condition, as indicated in Line 26, is to exceed the maximum iteration and have consistent results in two consecutive searches. Line 4 counts the iteration. 3. Line 5 to 20 allocate resources for the partial solution \(NALO\) and design a new assembly line \(NAL^{\prime}\). Line 6 to 13 allocate resources for each operation in the partial solution \(NALO\).