# An Improved Variable Neighborhood Search for the Reconfigurable Assembly Line Reconfiguring Problem
## 5 Proposed IVNS-RALRP
### Initialization  
VNS iteratively optimizes based on an initial solution until a final solution is obtained. If the objective value of initial solution is poor, the entire algorithm converges slowly. Additionally, the initial solution must satisfy both cycle time constraint and process precedence constraint. This paper proposes a two-stage initialization method. Since the cost of moving individual resources in the old assembly line is much lower than adding new resources (\(\lambda\ll\varphi,\kappa,\lambda\)), the optimization objective is to minimize the sum of moving old resources and adding new resource costs. Therefore, in the first stage of the initialization method, resources that can be reused, and their corresponding operations for new products, are searched for. In the second stage, operations are sequentially assigned to stations according to process precedence constraint, prioritizing the use of resources identified in the first stage from the old assembly line. This process continues, generating subsequent stations according to the cycle time constraint until all operations are allocated, thereby forming a new assembly line as the initial solution. The pseudocode in Algorithm 2 illustrates this procedure. ```
Data: Product-process-resource information \(G\) with Data Structure 1, cycle time \(ct\), old assembly line \(OAL\) with Data Structure 2. Result: New assembly line \(NAL\) with Data Structure 2. Initialize maximum iteration \(maxIter\), \(iter\gets 0\) ; Calculate in-degree of all operations \(inDegree\) in \(G\) ; \(NAL\gets initialization(G,ct,OAL)\) in Algorithm 2; Reconfiguration cost \(rc\gets rcCalculate(OAL,NAL)\) in Algorithm 3 ; whileiter \(<maxIter\)do \(iter\gets iter+1\), \(k\gets 1\); repeat repeat  Partial solution, i.e., operations of new assembly line \(NALO\leftarrow\mathcal{N}_{k}(G,ct,NAL)\) ; until\(isLegal(G,NALO,inDegree)\) in Algorithm 4; \(NAL^{\prime}\gets search(G,ct,NALO)\) in Algorithm 5 ; \(rc^{\prime}\gets rcCalculate(OAL,NAL^{\prime})\); if\(rc^{\prime}<rc\)then \(rc\gets rc^{\prime}\); \(NAL\getsNAL^{\prime}\); \(k\gets 1\); else \(k\gets k+1\);  end while until\(k=k_{\text{max}}\);  end while
```  
**Algorithm 1**IVNS-RALRP  
First Stage:  
1. The first two lines focus on searching for resources that can be maximally utilized by operations, where each operation corresponds uniquely to a resource. In Line 1, if operation \(i\) of product \(G\) can be processed by resource \(j\) of the old assembly line \(OAL\), then \(r_{ij}=1\); otherwise, \(r_{ij}=0\). The matrix \(R_{m\times z}\) represents the many-to-many relationship between operations and resources. To maximize the number of reusable resources, this problem is transformed into an assignment problem. Line 2 utilizes the Hungarian algorithm [30] to obtain an optimal assignment scheme \(M_{m\times z}\) for operations and resources. 2. Due to the ability of reconfigurable and flexible resources to process multiple operations, Line 3 to 9 allocate feasible operations to the identified reconfigurable and flexible resources. And the result is stored in \(M_{m\times z}\). Second Stage:
3. Line 10 to 11 perform initialization. Line 12 identifies operations without process precedence constraint. 4. Line 13 to 28 establish the new assembly line. Line 14 randomly selects a feasible operation. Line 15 to 19 match resources for the selected operation. If a resource corresponding to the operation selected in the first stage is available, a random resource from those corresponding resources is chosen; otherwise, a random resource is selected from the resource library. Line 20 to 24 indicate that if placing the resource at the current station meets the cycle time constraint, it is placed; otherwise, the next station is opened and the resource is placed there. 6. Line 25 records the results of operations and resources into the solution \(NAL\). 7. Line 26 and Line 27 obtain the optional operations for the next iteration.