Lot Sizing Problem

General 모듈 활용 사례로 Lot Sizing Problem (LSP)를 소개합니다.

개요

Lot Sizing Problem (LSP)는 경영과학 및 최적화 분야에서 전통적으로 다뤄져 왔던 생산계획 문제입니다. 여기서 의사결정자는 주어진 계획구간의 각 Period에서 발생하는 수요를 만족시키면서 총비용(생산 비용, 고정 비용 및 재고 비용의 합)을 최소화하는 생산량을 결정하고자 합니다. 특정 Period의 수요는 해당 Period에서의 생산 또는 재고량을 통해 만족시키게 됩니다. 이때 여러 가지 비용들이 발생하게 되는데 제품을 생산하는 경우 생산설비를 가동하는데 필요한 고정 비용이 발생하며 생산량에 비례하는 가변 비용이 발생합니다. 또한, 재고의 경우 유지 비용이 발생합니다.

Lot Sizing Problem의 네트워크

예제

아래는 LSP의 간단한 예제입니다. 제품에 대한 5일간의 수요와 가변 비용, 고정 비용, 그리고 재고 비용에 대한 정보가 아래의 표와 같이 주어진다고 가정합니다.

Info.	Day 1	Day 2	Day 3	Day 4	Day 5
수요	3	2	1	2	1
생산 비용	3	0	1	0	2
고정 비용	0	12	7	4	5
재고 비용	0	0	0	0	0

위 문제의 가능한 해, 즉 5일 동안의 수요를 만족하는 생산계획은 매우 많습니다.

Solution 1

Info.	Day 1	Day 2	Day 3	Day 4	Day 5
생산량	3	2	1	2	1

위의 Solution 1은 매일 필요한 만큼만 생산하는 계획에 대응되며 이때 총비용은 아래와 같이 계산됩니다.

$$\text{Cost} = (3 \times 3 + 0) + (2 \times 0 + 12) + (1 \times 1 + 7) + (2 \times 0 + 4) + (1 \times 2 + 5) = 40$$

Solution 2

Info.	Day 1	Day 2	Day 3	Day 4	Day 5
생산량	5	0	1	2	1

한편, 위의 Solution 2의 경우 Day 1에 다음날 필요한 양까지 생산하는 계획으로 2만큼의 재고가 발생하게 됩니다. 이때 총비용은 아래와 같이 계산됩니다.

$$\text{Cost} = (5 \times 3 + 0) + 0 + (1 \times 1 + 7) + (2 \times 0 + 4) + (1 \times 2 + 5) = 34$$

따라서, Solution 2가 Solution 1보다 비용 관점에서 더 나은 Solution 임을 알 수 있습니다.

동적 계획법

최적해의 특성

LSP는 동적 계획법으로 모형화할 수 있는데 이를 위해서는 LSP가 갖는 고유한 성질, 즉 최적해의 구조적 특성을 활용합니다. LSP는 다음의 특성을 만족하는 최적해가 존재한다는 것을 알 수 있습니다.

LSP 최적해의 특성

1. $1 \leq t_1 < t_2 <\cdots < t_r \leq T$를 만족하는 $t_1, \cdots, t_r$ 정의. $1\leq j\leq r$인 $j$에 대해 $t_j$에서 생산하는 양은 $d_{t_j}+\cdots+d_{t_{j+1}-1}$ 이다. ($t_{r+1}= n+1$)
2. 현재 가지고 있는 재고가 0일 경우에만 생산을 수행한다.

3. Period $t$에서 생산을 한다면, 생산량은 $0\leq k \leq T-t$인 $k$에 대해 $t$부터 $t+k$까지의 총 수요량과 정확히 일치한다.

위의 특성을 풀어서 설명하면 전체 $T$​ Period 중 생산이 일어나는 Period는 일부이며 매 생산 Period마다 현재부터 다음 번 생산 Period 직전 Period까지의 수요를 정확히 만족하도록 생산한다는 의미입니다. 따라서, 매 생산 Period가 시작할 때 가지고 있는 재고는 0이 됩니다. 이를 네트워크 그림으로 표현하면 다음과 같습니다. Period 1에서 생산 시 1부터 3까지의 수요를 모두 만족하도록 생산하고, 재고가 0인 상태에서 Period 4에서 Period 5까지의 수요를 모두 만족하도록 생산합니다. 이때, Interval $[1,3]$과 $[4,5]$를 Regeneration interval 이라고 합니다.

LSP 최적해의 구조적 특성

이러한 특성을 활용해 LSP를 다음과 같이 동적계획법으로 모형화합니다.

State

Final Stage가 아닌 Stage $t$에서의 State는 $k \leq t$인 $k$에 대해 $(k,t)$의 순서쌍으로 정의됩니다. State $(k,t)$는 Period 1부터 $t$까지의 LSP를 풀 때, 마지막 생산이 일어난 Period가 $k$임을 의미합니다. 즉, $[k,t]$가 마지막 Regeneration interval이며 Period $k$에서의 생산량은 $d_k+\cdots +d_t$가 됩니다. 각 State에 대응되는 비용을 $J(k,t)$라고 하면, 이 값은 마지막 Regeneration interval이 $[k,t]$인 모든 계획들의 비용 중 최소비용을 나타냅니다.

Stage

문제에서 정의된 Period가 Stage에 대응됩니다. 또한 종료를 나타내는 Final State가 포함된 Stage를 추가로 정의합니다. 즉, 위의 예제는 Stage가 6(=5+1) 개로 정의됩니다.

Action과 State Transition

$k \leq t < T$인 State $(k,t)$에서 가능한 Action은 2가지 입니다.

1. $t+1$을 현재 Regeneration interval $[k,t]$에 포함시킨다. 이 경우, State $(k,t)$에서 $(k,t+1)$로 Transition이 발생합니다. 의미상 Period $k$에 추가적으로 $t+1$에 해당하는 수요 $d_{t+1}$을 추가로 생산해야 하므로 $p_k \cdot d_{t+1}$의 Transition cost가 발생합니다.
2. $t+1$에서 새로운 Regeneration interval을 시작한다. 이 경우, State $(k,t)$에서 $(t+1,t+1)$로 Transition이 발생합니다. Period $t+1$에서 새롭게 생산을 진행하므로 Setup 비용과 생산비용의 합 $q_{t+1}+p_{t+1} \cdot d_{t+1}$의 Transition cost가 발생합니다.

마지막 Stage의 State로의 Transition cost는 0으로 정의합니다. 위의 Action을 그림으로 나타내면 아래와 같습니다.

State (k,t)에서 가능한 Action

앞에서 살펴본 예제의 State Transition Network는 다음과 같습니다.

LSP의 State Trasition Network

Initial State(Start 노드)로부터 Final State(Final 노드)까지의 하나의 경로가 문제의 가능해와 대응되며, 가능한 경로 중 가장 짧은 경로가 문제의 최적해와 대응됩니다. 아래는 최적해를 나타내는 경로를 나타낸 것입니다.

LSP의 최적해와 대응되는 네트워크 상의 최단경로

DP Recursion

각 State에 대응되는 비용을 $J(k,t)$​라고 하면, 이 값은 마지막 생산이 Period가 $k$에 일어나는 계획들의 비용 중 최소 비용을 나타냅니다. ​

$t$ Period 동안의 문제의 최소 비용을 $G(t)$라고 하면, 다음의 식이 성립합니다.

$$G(t) = \min_{k: \, k \leq t} \{J(k,t)\}$$

각 State 간의 관계와 Transition cost는 아래와 같이 정의됩니다. ($G(0)=0$으로 정의)

$$\begin{align*} &J(k,t+1) = J(k,t) + p_k d_{t+1} \qquad \text{for all } k,t \text{ with } k \leq t, \\ &J(t,t) = G(t-1)+q_t+p_td_t \qquad \text{for all } t. \end{align*}$$

예제 문제 풀이 방법

$G(1)=J(1,1)=0 + 3 \times 3=9$

$J(1,2)=J(1,1)+2 \times 3=15$

$J(2,2)=G(1) + 12 + 2 \times 0 = 21$ 이므로 $G(2) = \min \{ J(1,2), J(2,2)\} = 15$

$J(1,3)=J(1,2) + 3 = 18$

$J(2,3) = J(2,2) + 0 = 21$

$J(3,3)=G(2) + 7+1 \times 1 = 23$ 이므로 $G(3)=18$과 같이 계산됩니다.

위와 같은 방식으로 $G(0)=0$에서 시작하여 Forward Recursion을 통해 $G(5)$를 계산함으로써 이 문제의 최적해를 구할 수 있습니다.

State Bounds

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

Primal Bound

State $(k,t)$에서의 Primal Bound를 구하기 위해서는 하나의 가능해를 구하면 됩니다. 가능해를 구하는 방법은 여러가지가 있을 수 있으며, 가장 단순한 방법으로는 남아 있는 $t+1$부터 $T$까지의 Period를 하나의 Regeneration interval로 묶는 것입니다. 이러한 가능해는 최적이 아닐 수 있지만 이 때 Primal Bound는 $J(k,t)+ q_{t+1} + p_{t+1}(d_{t+1}+\cdots + d_T)$가 됩니다.

Dual Bound

State $(k,t)$에서의 Dual Bound를 구하기 위해서는 문제에 포함된 제약의 일부를 완화시킨 완화문제를 풀면 됩니다. 가장 단순한 Dual Bound로는 $t$시점 이후의 모든 비용 파라메터를 0이라고 설정하는 것입니다. 이 경우 얻을 수 있는 Dual Bound는 $J(k,t)$​가 됩니다. 이외에도 다양한 완화 기법을 활용할 수 있습니다.

References

Production Planning by Mixed Integer Programming. Y. Pochet, L. Wolsey. Springer. 2006.