Car Resequencing Problem

General 모듈 활용 사례로 Car Resequencing Problem (CRP)를 소개합니다.

개요

전형적인 자동차 생산 프로세스는 크게 프레스 공정, 차제 공정, 도장 공정, 조립 공정의 4가지 공정으로 이루어져 있습니다. 자동차 생산 업체들은 생산 프로세스의 효율적인 운영을 위해 차량을 저장할 수 있는 저장 시스템을 사용하여 생산 흐름을 제어하는 경우가 많습니다. 예를 들어, 특정 공정을 마친 차량들은 저장 시스템에 저장된 후 순차적으로 인출되어 후행 공정으로 이동하게 되는데, 이때 차량 인출 순서를 제어함으로써 생산 흐름 및 후행 공정에서의 작업 순서 결정이 가능하도록 합니다. 많은 종류의 저장 시스템 중 여러 개의 컨베이어로 구성된 저장 시스템은 비용 효율적이고 운영이 비교적 간단하다는 특성 때문에 자동차 산업에서 널리 활용되고 있습니다. 일반적으로 이러한 저장 시스템은 차체 공정과 도장 공정 사이에 위치하여 도장 공정에서의 작업 순서를 결정하게 됩니다.

Car Resequencing Problem (CRP)은 도장 공정에서의 작업 순서를 고려하여 저장 시스템으로부터의 차량 인출 순서를 결정하는 문제입니다. 도장 공정에서 발생하는 비용은 공정 특성상 작업 순서에 따라 Setup 비용이 달라지게 되는 순서 의존적 비용 구조를 가지고 있습니다. 예를 들어, 자동차를 빨간색으로 도색 후 다음 차량도 동일하게 빨간색으로 도색할 경우 Setup 비용이 발생하지 않지만, 다음 차량을 검은색으로 도색할 경우 이전 도색 시 사용했던 빨간색 도료를 노즐에서 제거하고 검은색 도료를 준비해야 하기 때문에 이에 따른 비용이 발생합니다. 따라서, 최대한 같은 색의 차량을 연속적으로 인출하는 것이 비용을 줄이는 인출 방법이라고 할 수 있습니다.

CRP 문제는 작업 순서 사이에 발생하는 비용 형태에 따라 색 교체 횟수 최소화 문제와 색 교체 비용 최소화 문제로 구분됩니다.

• 색 교체 횟수 최소화 문제: 서로 다른 두 가지 색 사이의 교체 비용이 모두 동일하게 1이라고 가정

• 색 교체 비용 최소화 문제: 서로 다른 두 가지 색 사이의 교체 비용이 순서에 따라 달라질 수 있다고 가정 (ex. 검은색을 도색 후 흰색을 도색하는 것과 흰색을 도색 후 검은색을 도색하는 것의 비용이 다를 수 있음)

자동차 생산 프로세스에서의 차량 저장 시스템

예제

아래와 같이 차량이 저장 시스템에 저장되어 있을 때 도장 공정에서의 색 교체 횟수를 최소화하는 차량 인출 순서를 구하고자 합니다.

색 교체 횟수 최소화 문제 예제

간단한 인출 로직 (Simple rule)

Simple rule은 가장 최근에 인출한 차량과 동일한 색의 차량을 인출 가능할 경우 해당 차량을 인출하고 그렇지 않으면 가장 오래 대기 중인 차량을 인출하는 로직입니다. 로직이 비교적 간단하고 합리적이기 때문에 현업에서 많이 사용하고 있는 인출 로직 중에 하나입니다. Simple rule을 기반으로 구한 차량 인출 순서는 아래 그림과 같으며 총 13번의 색 교체가 발생하였음을 확인할 수 있습니다.

Simple rule 기반 차량 인출 순서

최적 인출 순서

최적화 기법을 통해 최적 차량 인출 순서를 구하면 아래 그림과 같으며 총 9번의 색 교체가 발생하였음을 확인할 수 있습니다. 이는 Simple rule 대비 색 교체 횟수가 약 30% 줄어든 결과입니다.

최적 차량 인출 순서

동적 계획법

CRP 문제는 동적 계획법으로 모형화가 가능합니다.

State

각 컨베이어에서 인출한 차량 개수와 마지막으로 인출된 컨베이어 번호로 정의됩니다. 즉, $m$개의 컨베이어가 있을 때 $P_i$를 컨베이어 $i$​에서 인출된 차량의 개수, $k$를 마지막으로 인출된 컨베이어 번호라고 할 때 State $S$는 다음과 같은 $(m+1)$​-tuple로 정의됩니다.

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

State 정의 예시 코드

Stage

Stage는 컨베이어에서 인출한 총 차량 개수로 정의됩니다. 즉, State $S$의 Stage $v$는 아래와 같습니다.

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

따라서, Initial State와 Final State가 포함된 Stage를 제외하고 저장 시스템에 존재하는 총 차량 개수만큼 Stage가 정의됩니다.

State Transition

State Transition은 특정 컨베이어에서 차량이 인출되는 이벤트와 대응됩니다. 즉, 컨베이어 $l$​에서 차량을 인출하는 이벤트에 대응하는 State Transition은 아래와 같이 정의됩니다.

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

이때 $S$에서 $S^{\prime}$사이의 Transition cost는 각 State가 의미하는 차량 간의 색 교체 비용으로 정의됩니다.

이해를 돕기 위해 2개의 차량이 2개의 컨베이어에 각각 존재하는 문제에 대한 State Transition Network를 그림으로 나타내면 다음과 같습니다.

State Transition Network (2개의 컨베이어에 2개의 차량이 각각 존재하는 경우)

위의 그림에서 빨간색으로 표시한 것처럼 Initial State(Start 노드)로부터 Final State(Finish 노드)까지의 하나의 경로가 문제의 가능해와 대응되며, 가능한 경로 중 가장 짧은 경로가 문제의 최적해와 대응됩니다.

State Transition 예시 코드

State Bounds

State의 Bound 정보를 통해서 DP의 탐색 범위를 줄여 최적해를 구하는 계산 시간을 단축시키거나 근사해를 구하는 데에 활용할 수 있습니다.

Primal Bound

CRP 문제의 경우 가능해의 목적함수 값이 최적해의 상한으로 Primal Bound가 됩니다. 각 State로부터 가능해를 구하는 가장 간단한 방법으로 Simple rule을 사용합니다.

Primal Bound 예시 코드

Dual Bound

CRP 문제의 경우 문제에 정의된 제약의 일부분을 완화시킨 문제의 최적 목적함수 값이 최적해의 하한으로 Dual Bound가 됩니다. 다양한 제약 완화 방법이 알려져 있으며 그중에서 대표적인 방법은 아래와 같습니다. 자세한 사항은 관련 논문을 참조하시기 바랍니다.

차량 간 선/후행 제약 완화 (Precedence constraints relaxation)

컨베이어의 특성으로 인해 같은 컨베이어에 존재하는 차량 간에는 반드시 선행차량이 먼저 인출되어야 후행 차량이 인출될 수 있습니다. 이러한 차량 간 선/후행 제약을 완화함으로써 본 문제의 하한을 구할 수 있습니다. 가장 간단한 방법으로 컨베이어가 모두 없다고 생각했을 때 발생할 수 있는 가장 작은 비용이 본 문제의 하한이 될 수 있습니다. 이는 선/후행 제약이 전혀 없는 것과 동일한 상황이므로 저장 시스템 내에 존재하는 "색상 개수-1"이 하한 값이 될 수 있습니다.

아래의 예시는 모든 컨베이어의 선/후행 제약을 완화한 모습입니다. 이 경우 동일한 색상의 차량들을 연속하여 인출할 수 있고 저장 시스템 내에 총 3가지 색상의 차량이 존재하므로 2가 하한 값이 됩니다.

차량 간 선/후행 제약 완화

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.