# A Decomposition Algorithm for Dynamic Car Sequencing Problems with Buffers
## 1 Introduction  
The introduction of [PERSON]'s Model T revolutionized automobile manufacturing, and its creative assembly line has greatly reduced the cost of automobile production. As the automotive industry continues to evolve, product requirements and production system requirements have changed dramatically, and orders with \"small lot size, multiple varieties, and customization\" have made the mixed-flow production model increasingly popular. The so-called mixed-flow production model means that different body types, different colors, and different parts are produced on the same production line, making the production process more complex. Assembly line balancing and car sequencing are the two main issues for effective operation of mixed-flow assembly lines [1]. The assembly line balancing problem has been widely studied since its introduction [2; 3; 4; 5; 6]; scholars have constructed different models for the simple assembly line balancing problem (SALBP) and the generalized assembly line balancing problem (GALBP) by considering the number of workstations, productivity, assembly line cost, smoothness index of parts consumption, and workstation idle time to optimize the solution. In addition to the assembly line balancing problem, the car sequencing problem (CSP) of automobiles is equally important. There are usually multiple departments in automobile production, such as welding shop, painting shop, and final assembly shop, etc. Each shop has different preferences for the sequence of car production. For example, the painting shop tends to limit the car production sequence by car color in order to save the cost of cleaning paint nozzles [7], and the final assembly shop tends to limit the production by model and configuration based on the consideration of man hours and parts consumption. Since the constraints of each shop on the mixed-flow assembly line are different, each shop has different car sequencing goals, which leads to production scheduling that cannot follow the same sequence of continuous production. In particular, the sequence difference between the paint shop and final assembly shop is large. For this situation, there are two solutions. The first one is to generate a fixed compromise sequence by considering the productionneeds of multiple shops simultaneously. [PERSON] et al. [8], [PERSON] et al. [9], [PERSON] [10], [PERSON] and [PERSON] [11], and [PERSON] [12] have described how to generate the initial production sequence, and it is obvious that the generated such sequences all violate the constraint rules of each workshop to varying degrees. Another approach is to create a buffer between these two shops to reorder the cars to obtain the desired sequence, at which point the CSP evolves into the car sequencing problem with buffer (CSPwB). There are various forms of buffer zones, and [PERSON] [13] and [PERSON] [14] summarized several structural forms of buffer zones:  
* Pull-out buffer: Cars at any position in the car sequence can be removed and placed in the backward buffer, and then inserted into the appropriate position as the car sequence advances, so that cars can be moved to any position later in the sequence, and the advancement of the car sequence is limited by the number of cars allowed out of the column. * Ring buffer: Multiple cars can be selected from the car sequence into the ring buffer, and cars from any position in the ring buffer can be put back into the sequence. * Automated storage and retrieval system (AS/RS): Consisting of hundreds of buffer points, each buffer point can be accessed individually to generate the desired sequence of cars, and the flexibility of car sequencing is influenced by the number of buffer point locations.