# A Decomposition Algorithm for Dynamic Car Sequencing Problems with Buffers
## 2 Literature Review  
CSP exists in a large number of automotive production companies and has gradually developed into a classical type of planning and scheduling problem. CSP was first proposed by [PERSON] et al. [15] and gradually gained attention. [PERSON] et al. [16] proved that CSP is an NP-hard problem. [PERSON] et al. [17] divided the methods for solving CSP into two categories: exact methods (constraint planning, integer planning, etc.) and heuristic methods (genetic algorithms, ant colony optimization algorithms, etc.). [PERSON] et al. [1] classified three types of sorting methods in mixed-flow assembly based on different sorting objectives: mixed model sorting, car sorting, and level scheduling. [PERSON] and [PERSON] [18] proposed an integer planning model for CSP. [PERSON] et al. [19] solved CSP based on mixed integer programming (MIP) with large neighborhood search (LNS) by minimizing the violation of car separation rules. [PERSON] et al. [20] proposed two local search methods that use invariants to speed up the search for the optimal solution of the algorithm to solve the CSP. [PERSON] and [PERSON] [11] proposed two methods to solve CSP, i.e., integer linear programming (ILP) and hybrid variable neighborhood search, and showed the superiority of the algorithms by experimental examples. [PERSON] [21] solved the CSP with color by improving the variable neighborhood search (VNS) results with the Tabu metaheuristic. [PERSON] et al. [22] studied the effect of different heuristics on CSP and proposed a slack-based filtering algorithm.  
For CSPwB, [PERSON] [23] developed an artificial-neural-network-based metamodel simulation combined with the genetic algorithm (ANN-GA) to search for optimal solutions. [PERSON] et al. [24] investigated the effect of using different metaheuristics on solving CSPwB. [PERSON] et al. [25] used a branch-and-bound algorithm to solve CSPwB with the objective of minimizing the number of color switches in the paint shop. [PERSON] et al. [26] proposed a new algorithm of gravity-like mechanism to achieve the sequencing of cars in the buffers by encoding them as particles. [PERSON] et al. [27] proposed a store/retrieve algorithm and simulated the proposed algorithm to verify the effectiveness of the proposed algorithm. [PERSON] et al. [28] developed a new branch-and-bound algorithm that exploits the symmetry of the problem and improves the efficiency of the algorithm.  
Currently, these studies on CSP and CSPwB tend to consider only the degree of violation of the rules and the operational efficiency of the algorithm, and do not consider the time cost of car sorting. However, in the actual enterprise production, sometimes, there is a surge of orders and the production beat needs to be accelerated, and the excessive car sequencing time will affect the production schedule. Furthermore, previous studies were often based on static reordering [13], i.e., all information is known before car sequencing, and thus, decomposing the problem into a series of static problems within rolling planning. The algorithm proposed in this paper is based on the dynamic sequencing of cars, i.e., the sequence of cars before reaching the buffer is not known, which makes the car sequencing problem an online problem.