# An Improved Variable Neighborhood Search for the Reconfigurable Assembly Line Reconfiguring Problem
## 3 Problem Description and Formulation
### Problem Statement  
We consider a RAL that produces several products from the same product family at different stages. Each product requires a specific set of operations to complete its production. Each operation is performed by a resource selected from a set of optional resources, each with varying processing times, and must be executed according to process precedence constraint. Therefore, an acceptable RAL configuration for a product must include a resource for each operation and satisfy the process precedence constraint. Product updates lead to changes in operations, process precedence constraints, and optional resources. Thus, RALRP allocates new operations to stations while optimally utilizing the resources from the existing old assembly line and new resources. For example, in an assembly line, a resource reassignment can be seen as a relocation of a robot from one station to another. Without loss of generality, we suppose that the logistics time of both stations is less than the process time of the station. Moreover, we do not consider the inclusion and exclusion constraints that force certain tasks to be assigned, or not, to the same station.  
In order to ensure high efficiency and quality reconfiguration, it is important to optimize the number of resource reassignments performed when product update. Since  
Figure 1: Classification of optimization approaches.  
different types of resource reassignments have different costs. In this case, it is relevant to RALRP so that the resource reassignments cost is minimized.  
To better illustrate the above-described RALRP, Figure 2 shows an example where previously Assembly Line A produced Product A. After some time, Product A is upgraded to Product B, prompting Assembly Line A to be reconfigured to Assembly Line B to accommodate the new operations and process precedence constraint. Thus, the input to the optimization problem consists of the old assembly line and the new product, and the output is the new assembly line configuration. In the figure, product information is represented by corresponding process precedence graphs with resources. Circles denote operation number, arrows denote the process precedence constraint, and rectangles represent optional manufacturing resource names and their process time. For example, in the process precedence graph with resources for Product A, circle 2 represents operation number 2, with the corresponding rectangle indicating optional manufacturing resources D2 and RI, with process time of 100 s and 80 s, respectively. An arrow from circle 2 to circle 5 signifies that operation 2 must be completed before operation 5. Assembly Line A, corresponding to Product A, consists of five stations, where the first station S1 includes resource D1, processing operation 1 with a total process time of 160 s. In Product B, sections highlighted in yellow denote the parts of the product that have changed. Assembly Line B represents a reconfigured configuration. Compared to Assembly Line A, resources D2 and D3 in station S2 have been relocated, resource D4 has been removed, and new resource D11 has been added. Additionally, new resource D12 has been introduced into station S2. A new station S4 has been added, equipped with resource R6.  
Figure 2: Reconfiguration of RAL for product upgrade.