# An Improved Variable Neighborhood Search for the Reconfigurable Assembly Line Reconfiguring Problem
## 2 Literature Review
### Solution Methods  
RALRP involves complex process information, such as operations and resources, so it is necessary to establish an efficient data structure modeling this information to accelerate the algorithm. Most studies [16; 17] use a two-vector solution representation, including an Operations Sequence and Machines Sequence. [PERSON] et al. [18] further construct the operation sequence based on precedence constraint in the encoding scheme. However, when the problem involves more complex process information, this low-level data structure consumes a significant amount of time during encoding and decoding, thereby affecting the efficiency of the algorithm.  
As a combinatorial optimization problem, ALRBP and its variants are tackled using exact and approximate methods, as illustrated in Figure 1. Exact methods include mathematical programming and enumerative algorithms [4; 19; 20]. The main advantage of exact methods is guaranteeing global optimal results. However, they are suitable for small-scale problems, and cannot solve large instances within a reasonable time. Approximate methods include heuristic algorithms, meta-heuristic algorithms and hyper-heuristic algorithms. Research mainly focuses on heuristic algorithms and meta-heuristic algorithms. Heuristic algorithms employ rules derived from problem characteristics for efficient solving, such as tabu search [21], heuristic rules [5] and VNS. The basic component of the algorithm is basic VNS proposed by [PERSON] and [PERSON] in 1997 [22; 23]. VNS is a local search based meta-heuristic, which explores increasingly several neighborhoods of the current incumbent solution and jumps from this solution to a new one if and only if an improvement has been made. The selection of neighborhood structures can greatly influence the performance of the VNS method [22]. [PERSON] et al. [24] propose four different neighborhood structures for the assembly line balancing problem. [PERSON] [25] demonstrates the promising advantages of designing effective neighborhood structures for the Assembly Line Rebalancing Problem. [PERSON] et al. [26] introduce a two-phase VNS algorithm. In the first phase, a VNS approach is applied to assign tasks to workstations with the aim of minimizing the cycle time, while in the second phase, a variable neighborhood descent method is applied to assign workers to workstations. Genetic Algorithm (GA) [27], Simulated Annealing Algorithm (SA), and Particle Swarm Optimization (PSO) are typical meta-heuristic algorithms. There is no research on applying SA and PSO to solve ALRBP. [PERSON] [28] proposes a GA hybridized with a heuristic priority rule-based procedure. This hybridization is used to add more rich seeds to the initial population and, consequently, to improve the convergence capability and performance of the GA. [PERSON] et al. [29] propose a modified non-dominated sorting genetic algorithm, which employs some problem-specific designs for encoding and decoding, initial population, crossover operator, mutation operator, and selection operator. In addition, they also use experiments to determine the parameters for GA to solve ALRBP.  
At present, there is a lack of data structures that represent the complex information of the RALRP, as well as a lack of efficient algorithms for the simultaneous allocation of operations and manufacturing resources.