# A Decomposition Algorithm for Dynamic Car Sequencing Problems with Buffers
## 3 Problem Description and Mathematical Model  
In this section, we develop a detailed mathematical model for DCSPwB. Consider an initial sequence of \(N\) cars of different models: \(i=1,2,\ldots,N\), \(O\) is the set of options required for different models of cars, and for any option in the set, the capacity constraint, i.e., \(r_{o}:s_{o}\), is defined, and the number of cars with option \(o\) cannot exceed \(r_{o}\) in the sequence \(s_{o}\) of cars requiring option \(o\). The capacity constraints are determined based on the production characteristics of the assembly plant downstream of the buffer. Violation of these constraints can cause problems, such as excessive workload of assembly plant workers and uneven consumption of parts. The following is a simple example to illustrate the capacity constraint, as shown in Table 1, which considers a car production schedule with four types, i.e., A, B, C, and D, for a total of five cars. Different types of cars need to satisfy different options; for example, Class A cars need to satisfy options \(o_{1}\) and \(o_{2}\), while Class B cars only need to satisfy \(o_{1}\). The constraints associated with \(o_{1}\) and \(o_{2}\) are \(1/2\) and \(1/3\), respectively. These five cars can generate \(5!=120\) kinds of car sequences; here, we use the \"sliding window\" method to count the number of violations. This method will be repeated to amplify the number of violations of the option constraints, which is equivalent to increasing the weight of the \"problem car\", so that the algorithm tends to disperse the \"problem car\". For example, if the sequence of cars after reordering in the buffer is [B, A, A, C, D], then the subsequence [B, A], [A, A] violates the constraint \(o_{1}\), and the subsequence [A, C, D] violates the constraint \(o_{2}\), and thus, the total number of violations of the sequence is three. Here, the second car is a \"problem car\", and removing or replacing the second car will reduce the number of violations by two. The buffer consists of \(L\) parallel lanes, each of which can hold up to \(V\) cars. The initial sequence of cars is reordered through the buffer to generate a new sequence into the downstream shop, and only one car can enter and leave the buffer at a time, so the flexibility of reordering is related to the buffer capacity. We also consider the time cost of DCSPwB and add it to the objective function. In addition, the following assumptions are made:  
1. Each car takes the same amount of time to move one space in either lane of the buffer and can only move in one direction. 2. The buffer continues to function normally, regardless of fault conditions. According to the above expression and the definition of symbols in Table 2, DCSPwB is defined as follows:  
Min:  
\[F =\sum_{o\in O}w_{o}\cdot\sum_{j=1}^{\min(j+s_{o}-1,N)}z_{oj}\] \[+w_{t}\cdot sc_{t}\sum_{i=1}^{N}\sum_{l=1}^{L}y_{il}[(V-1)\cdot TL +te_{l}+tf_{l}] \tag{1}\]  
Subject to:  
\[\sum_{l=1}^{L}y_{il} =1,\forall i=1,\ldots,N \tag{2}\] \[\sum_{i=1}^{N}y_{il} \leqslant V,\forall l=1,\ldots,L\] (3) \[\sum_{i=1}^{N}c_{il} =1,\forall j=1,\ldots,N \tag{4}\] \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Car Type** & **A** & **B** & **C** & **D** \\ \hline \(o_{1}\) & ✓ & ✓ & & 1/2 \\ \(o_{2}\) & ✓ & & ✓ & ✓ & 2/3 \\ Amount & 2 & 1 & 1 & 1 & \\ \hline \hline \end{tabular}
\end{table} 
Table 1: A simple example of a car sequencing problem. \[\sum_{k=1}^{N}c_{ik}\cdot k-\sum_{k=1}^{N}c_{jk}\cdot k\leqslant MI \left(2-y_{il}-y_{jl}\right),\] \[\forall i=1,\ldots,N-1,j=i+1,\ldots,N,l=1,\ldots,L \tag{5}\] \[\sum_{i=1}^{N}\sum_{\tau=j}^{j+s_{0}-1}a_{io}\cdot c_{i\tau} \leqslant r_{0}+M\cdot z_{oj},\] \[\forall oeO,j=1,\ldots,N-s_{o}+1 \tag{6}\]  
The objective Equation (1) is to minimize the number of violations of the car sequence in all options and the time cost of car sorting, balancing the importance of time by the weight coefficient \(w_{t}\).