# A Decomposition Algorithm for Dynamic Car Sequencing Problems with Buffers
## 4 DCSPwB Decompositional Algorithm
### Simple Rule-Based Heuristic Entry Algorithm  
In the car entry phase, we introduce a scoring model, where the level of the score represents the magnitude of the match, and the scoring model is as in Equation (7). Where \(f_{i}(l)\) denotes the matching degree of car \(i\) with lane \(l\), \(n\) denotes the number of rules, \(r\) denotes the priority of the rules, \(l\) is a positive integer determined by the number of rules, and the rules are formulated based on the attributes of the car. For example, if the configuration of a car is 4 WD and hybrid, then the attributes of the car are {4 WD, hybrid}. Here, we only care about the attributes related to the constraints of the final assembly plant, such as the driving mode and power source of the car, etc. The attributes related to the paint shop, such as the color of the car, are not relevant to the optimization objective Equation (1) and are not considered here. \[\underset{l=1,\ldots,L}{Max}f_{i}(l)=\] \[\left\{ \begin{array}{rl}\sum_{r=1}^{n}\left[u(r)\cdot 2^{n-r} \right],&\text{if lane $l$ is not empty}\\ \sum_{r=1}^{n}2^{n-r}-l,&\text{if lane $l$ is empty}\\ 0,&\text{if $l$ is $x$ and $arg\,Max\,f_{i-1}(l)=x$}\end{array} \right. \tag{7}\] \[u(r)=\left\{ \begin{array}{rl}1,&\text{if $d_{lr}=car_{ir}$} \\ 0,&\text{if $d_{lr}\
eq car_{ir}$}\end{array} \right. \tag{8}\]  
where \(u(r)\) is the attribute consistency metric and \(d_{lr}\) and \(car_{ir}\) denote the attributes of lane \(l\) and car \(i\), respectively, when based on rule \(r\). Once a car enters in a lane, the attributes of the lane remain consistent with that car. We also consider the time problem when cars enter the buffers. Different lanes have different distances from the entrance of the buffers; if a certain lane is close to the entrance of the buffers, the time for a car to enter that lane is shorter than the time for a car to move one space in that lane, which will result in a car waiting situation and increase the time cost of the car sorting process, so we avoid this situation by setting the matching degree of that lane to 0. According to the matching degree scoring model, the inbound heuristic rules in order of priority from highest to lowest are:  
1. Select the lane with the best match. 2. Select the lane with the largest remaining capacity. 3. Select the lane that takes the shortest amount of time to enter the buffers. A simple rule-based heuristic entry is shown in Algorithm 1. Algorithm 1 uses the car \(i\) that needs to enter the buffers and the set \(T\) of the time it takes for the car to enter each lane of the buffers as input. In line 1, the highest match \(maxScore\) of all lanes with car \(i\) is initialized to 0. In line 2, the set \(BL\) consisting of the lanes with the highest matching degree is initialized to empty. The loop in rows 3-7 updates the highest matching \(maxScore\) of all lanes with car \(i\). The loop in lines 8-12 updates the set \(BL\) consisting of the lanes with the highest matching degree. If the lane with the highest matching degree is not unique, in line 14, the function \(choic\_margin(BL)\) is used to calculate the lane with the largest remaining capacity and update \(BL\). If the lane with the largest remaining capacity is not unique, the lane that takes the shortest time for car \(i\) to enter the buffer is calculated by the function \(choic\_time(BL,T)\) and \(BL\) is updated, the lane assigned to car \(i\) is returned at the end of the algorithm. The time complexity of this algorithm is \(O(L)\). The algorithm matches different lanes for cars with different attributes based on the information of cars that are about to be warehoused and the information of the buffers, and does not depend on the information of car sequences in the upstream workshops to meet the dynamic sequencing requirements of cars. ```
Input: A car \(i\), Set of time required for car to enter each lane of buffer \(T\). Output: The set of lanes with the highest matching degree \(BL\).