Car Resequencing Problem

We introduce the Car Resequencing Problem (CRP) as a General module use case

Introduction

A typical automotive manufacturing process comprises four major shops: a press shop, a body shop, a paint shop, and an assembly shop. For the efficient operation of the production process, automotive manufacturers often use storage systems that can store cars to control the production flow. For example, cars that have completed an operation are stored in a storage system and then sequentially retrieved and moved to subsequent operations. By controlling the order in which cars are retrieved, it is possible to control the production flow and the order of jobs in subsequent operations. Among the many types of storage systems, storage systems consisting of multiple conveyors are widely utilized in the automotive industry because they are cost-effective and relatively simple to operate. Typically, these storage systems are located between the body shop and the paint shop to determine the sequence of jobs in the paint shop.

The Car Resequencing Problem (CRP) is the problem of determining the sequence of retrieval of cars from a storage system, taking into account the costs incurred in the paint shop. The costs incurred in the paint shop have a sequence-dependent cost structure, where the changeover cost varies depending on the order of operations due to the nature of the operation. For example, if a car is painted red and the next car is painted the same red, there is no changeover cost, but if the next car is painted black, there is a changeover cost because the red paint used in the previous painting must be flushed out from the nozzle and the black paint must be prepared. Therefore, retrieving cars of the same color in succession as much as possible is a retrieval method that reduces costs.

CRP problems are divided into minimizing the number of color changes and minimizing the cost of color changes, depending on the cost structure incurred between job orders.

• Minimizing the number of color changes: Assume that the changeover costs between two different colors are all equal to 1.

• Minimizing the changeover cost between color changes: Assume that the changeover cost between two different colors may vary depending on the order (e.g., painting black followed by white may cost differently than painting white followed by black).

Storage system in automotive paint shops

Example

We want to find a car retrieval sequence that minimizes the number of color changes in the painting process when the car is stored in the storage system, as shown below.

Example of problem minimizing the number of color changes

Simple heuristics (Simple rule)

The simple rule is a logic that retrieves a car of the same color as the most recently retrieved car if it is available; otherwise, it retrieves the car that has been waiting for the longest. Because the logic is relatively simple and reasonable, it is one of the retrieval logics widely used in practice. The car retrieval sequence obtained based on the simple rule is shown in the figure below, and we can see that a total of 13 color changes occurred.

Simple rule-based car retrieval sequence

Optimal solution

The optimal sequence of car retrievals using the optimization approach is shown in the figure below, and we can see that a total of 9 color changes occurred. This is a reduction of about 30% in the number of color changes compared to the simple rule.

Optimal car retrieval sequence

Dynamic Programming

We can model the CRP problem with dynamic programming as follows.

State

Defined as the number of cars retrieved from each conveyor and the last retrieved conveyor number. Thus, given $m$ conveyors, let $P_i$ be the number of cars retrieved from conveyor $i$ and $k$be the last retrieved conveyor number, then state is defined as the following $(m+1)$-tuple.

$$S = (P_1, P_2, \dots , P_m,k)$$

Example Code for Defining the State

Stage

A stage is defined as the total number of cars retrieved from the conveyor. That is, Stage $v$ of state $s$ is as follows.

$$v= \sum^m_{i = 1} P_i$$

Therefore, there are as many stages defined as the total number of cars in the storage system, excluding stages with initial state and final state.

Action and state transition

An action corresponds to an event where a car is retrieved from a conveyor. In other words, the action corresponding to the event of retrieving a car from a conveyor is defined as follows.

$$S=(P_1, \dots, P_l, \dots P_m,k) \rightarrow S^{\prime}=(P_1, \dots,P_l+1, \dots, P_m,k)$$

In this case, the transition cost from to $S^\prime$ is defined as the cost of changing colors between the cars represented by each state.

Here is an example of a state transition network for a problem with two cars on each of two conveyors.

State transition network (two cars on each of two conveyors)

A path from the initial state (Start node) to the final state (Finish node), as indicated by the red line in the figure above, corresponds to the feasible solution of the problem. Therefore, the shortest path in the network corresponds to the optimal solution of the problem.

Example Code of Defining the Actions

State Bounds

The bound information of the state can be used to reduce the search space to speed up the computation time to find the optimal solution, or to find an approximate solution.

Primal Bound

In the case of the CRP problem, the objective function value of the feasible solution is the primal bound as an upper bound on the optimal solution. The simplest way to find the feasible solution by performing a roll-out from each state is to use the Simple rule.

Example Code to Get the Primal Bound

Dual Bound

In the case of the CRP problem, the optimal objective function value of the problem after relaxing some of the constraints defined in the problem is dual bound as a lower bound on the optimal solution. Many different constraint relaxation methods are known, some of which are listed below. For more information, please refer to the related paper.

Precedence constraints relaxation

Due to the nature of conveyors, the preceding car must be retrieved between cars on the same conveyor before the following car can be retrieved. We can obtain a lower bound for this problem by relaxing these precedence constraints between cars. The lower bound for this problem can be the smallest cost that would be incurred if there were no conveyors. Since this is the same situation as if there were no precedence constraints, the "Number of colors in the storage system - 1" could be the lower bound.

The example below relaxes the precedence constraints on all conveyors. In this case, 2 is the lower bound because cars of the same color can be retrieved consecutively, and there are a total of 3 different colors of cars in the storage system.

Reaxing precedence constraints between cars

Example Code to Get the Dual Bound

References

Accelerated Dynamic Programming Algorithms for a Car Resequencing Problem in Automotive Paint Shops. S. Hong, J. Choi, J. Han, K. Lee. Applied Mathematical Modeling. 2018.