Zero-Wait 방안에서 다품종 회분식 공정의

Size와 Scheduling의 동시결정

복 진광, 문 성득, 박 선원

한국과학기술원 화학공학과

Simultaneous Sizing and Scheduling of Multiproduct Batch

Plants under Zero-Wait Policy

Jinkwang Bok, Sungdeuk Moon, and Sunwon Park

Dept. of Chemical Engineering, KAIST

1. 서	론

최근 들어서는 회분식 조업에 있어서 scheduling 문제를 design 단계에서 동시에 고려하는 연구가 활발히 진행되고 있다[1]. 이것은 조업순서의 결정을 고려해 조업하는 장치의 크기를 구하는 문제를 의미한다. 즉 하나의 제품에 대해 중간처리 장치가 없는 단순한 scheduling 정책의 경우, 장치의 크기를 결정하는 단계에서의 단순화된 scheduling 정책은 실제문제에서의 시간적인 요구조건에 대해 과오를 범하기 쉽기 때문에, 이에 대한 보완으로 Birewar와 Grossmann[1]는 MINLP 모델을 제안하였다. 일반적으로 MINLP는 이진변수만 다룰 수 있고 비 이진 정수 변수는 다루지 못하기 때문에, 그들은 어림법 (round off method)를 이용하여 비 이진 정수변수를 예측하였다. 그러나 그들의 논문에서 볼 수 있듯이 이러한 절차는 제한조건에 위배되는 결과를 얻게된다. 이에 본 논문에서는 보다 효율적인 scheduling알고리즘을 사용함과 동시에 비 이진 정수변수를 처리하기 위한 이진 표현법을 이용해, design과 scheduling을 동시에 고려하는 새로운 MINLP 식을 제안하고자 한다.

2. Sizing and Scheduling Model

M개의 장치로 구성되어 있고, [eqn: N_p]개의 제품들을 총 N개의 회분만큼 생산하는 다품종 회분식 공정을 가정하자. 또한, 각 제품 i (i=1,…,[eqn: N_p])에 대한 생산 회분수는 [eqn: n_i]개 이며, 각 장치 k ([eqn: k=1, CDOTS , M] )에 대하여 조업시간 [eqn: P_ik] 와 수송시간 [eqn: T_ik]이 주어졌다고 가정한다.

각 회분에 대한 장치의 크기를 부피 [eqn: V_k]로 나타내고 제품을 생산해야 하는 총 요구량은 [eqn: Q_i]로 주어졌다. 공정의 모든 조업은 주어진 scheduling horizon, H내에 끝나야 한다. 회분의 크기와 scheduling을 결정하여 회분조업에 필요한 조업비를 최소화하는 것이 본 문제의 목적함수이다.

①[eqn: min sum_k=1 ^M a_k V_k ^beta_k]	(1)

s.t.

[eqn: V_k >= S_ik B_i]	[eqn: k = 1, cdots, M]; [eqn: i = 1, cdots, N_p]	(2)

[eqn: n_i = Q_i over B_i]	[eqn: i = 1, cdots, N_p]	(3)

위 모델식에서 목적함수는 조업비용을 최소화하는 것이며 각 장치에 대한 부피의 함수로써 나타내었다[1]. 첫번째 제약식은 각 장치에서, 크기요소 (size factor) [eqn: S_ik]와 회분크기 [eqn: B_i]의 관계로 요구량에 대한 제약식을 나타내었고, 두번째 제약식은 각 제품의 정해진 요구량 [eqn: Q_i]에 대한 한 회분의 크기 [eqn: B_i]를 구함으로써 회분 회수 [eqn: n_i]를 결정한다.

② 조업순서에서의 처음과 마지막에 제조되는 제품은 각각 하나씩이다.

[eqn: sum_i=1 ^N_p YH_i = 1]	(4)

[eqn: sum_i=1 ^N_p YL_i = 1]	(5)

③ 다음식도 각 제품에 대해 생산해야 하는 총 수를 계산하는 식이다.	[eqn: YH_j + sum_i=1 ^N_p X_ij =n_j]	[eqn: j = 1, cdots, N_p]	(6)

[eqn: YL_i + sum_j=1 ^N_p X_ij =n_i]	[eqn: i = 1, cdots, N_p]	(7)

④ 각 장치에서의 makespan은 주어진 scheduling horizon을 넘어서는 안된다는 제한조건이 식(8)에 나타내었다. 많은 회수에 걸쳐서 제품을 생산하는 방안 중 Multiple Product Campaign (MPC)에 대한 모델은 다음과 같다.

[eqn: MS_k = sum_i=1 ^N_p YH_i HD_ik + sum_i=1 ^N_p sum_j=1 ^N_p X_ij D_ijk +][eqn: sum_i=1 ^N_p YL_i TL_ik + sum_i=1 ^N_p n_i LEFT [ {T_i(k-1) +P_ik +T_ik } RIGHT ] <= H]

[eqn: k = 1, cdots, M]	(8)

⑤[eqn: X_ii < n_i -1]	[eqn: i = 1, cdots, N_p]	(9)

Single Product Campaign (SPC)정책에 대해서 조업할 경우는 makespan에 관한 제약식은 (8)와 동일하다고 할 수 있지만  (9)의 제약식이 다음과 같이 바뀌어야 한다.

[eqn: X_ii = n_i -1]	[eqn: i = 1, cdots, N_p]	(9□)

문제해결의 효율성을 증명해나가기 위해서 Birewar가 제시한 동일한 예제[1]에 대해서 두 가지 방법에 대한 결과를 비교하도록 하겠다.

3. 비 이진 정수의 이진표현법

어느 비 이진 정수 변수에 대해서도 우리는 이진수로 나타낼 수 있음은 이미 알고 있는 사실이다. 가령 100이라는 십진수에 대해서는 110010[2]로 나타낼 수 있다. 결국 다음과 같은 제한조건을 추가하므로써 비 이진 정수변수 처리에 대한 문제를 해결할 수 있다. 즉 문제가 되고 있는 비 이진 정수변수인 각 제품에 대한 회분수에 대해 다음과 같은 표현을 사용함으로써 정수 값을 가질 수 있도록 할 수 있다.

[eqn: n_i = 2^0 TIMES Y_1i +2^1 TIMES Y_2i + 2^2 TIMES Y_3i + 2^3 TIMES Y_4i][eqn: +2^5 TIMES Y_5i CDOTS]

[eqn: =SUM_j=0 2^j Y_(j+1)i], 여기서[eqn: Y_ji]는 이진변수 (0 또는 1)	(10)

처리해야하는 제품수의 증가에 따라 이진변수의 증가로 계산시간이 커지는 단점이 있기는 하지만 본 문제의 경우처럼 비 이진 정수변수가 많지 않은 경우는 적절하게 이용할 수 있는 알고리즘이다.

4. 예	제

기존의 Birewar와 Grossmann[1]의 모델로써 구한 경우, Birewar의 모델에 어림법을 적용하지 않고 비 이진 정수의 이진표현법을 적용한 경우, 그리고 새롭게 제안한 모델, 이렇게 세 가지 모델로써 구한 결과를 비교해 보도록 하겠다.

필요한 데이터는 [1]에 잘 나타나 있고, 이에 대해 SPC, MPC 정책에 대해 GAMS [3]를 이용해서 모델링하였다. 본 예제에서는 6개의 제품에 대해 4개의 회분을 거쳐야하는 문제이다. 세척시간은 없는 경우로 하였고, ZW에 대해 SPC와 MPC 문제를 만들어 풀어보았다. 표 1에서는 MPC모델에 의한 결과를 보여주고 있다. 표에 보여주듯 어림법에 의한 Birewar 모델의 결과는 제한조건에 위배되는 해를 구한다. 이진표현법을 적용할 경우, Birewar의 모델은 이진변수가 너무 많이 늘어나서 해를 발견하지 못하는 반면, 제안된 모델에 대해서는 적당한 시간 내에 해를 찾아내는 것을 볼 수 있다. SPC의 경우도 마찬가지로, Birewar의 모델의 경우, 어림법을 적용한 경우는 제한조건에 위배되는 해를 구하고, 이진표현법을 적용하면 해를 구하지 못하지만 새로운 모델로 풀 경우는 해를 발견한다. 결국 실제 규모로 문제의 크기가 커짐에 따라 제안된 모델식만이 적당한 시간 내에 작은 설계비용을 갖으며 모든 제한조건 범위내에 존재하는 해를 구해낼 수 있다.

5. 결	론

본 연구에서는 ZW 방안의 다품종 회분식 공정에 대한 회분의 크기 결정 및 생산조업 순서를 결정하는 새로운 MINLP 모델식을 제안하였다. 크기 결정에 따른 모델식은 Birewar의 모델식을 이용하였고 생산순서 결정과 관련된 부분은 Moon et al.[4]이 제안한 것을 이용하여 새롭게 모델식을 구성하였다. Birewar의 round off 방식에 의해 제한조건에 위배되는 것을, 비 이진 정수의 이진표현법을 이용하여 제한조건을 만족하는 해를 얻을 수 있었고 훨씬 빠른 시간 내에 적은 비용을 갖는 설계 방침을 찾아냄으로써 그 효율성을 입증하였다.

참고문헌

1. Birewar, D. B. and Grossmann, I. E. "Incorporating scheduling in the optimal design of multi product batch plants", Com. & Chem. Eng., 13, 141 (1989)

2. Birewar, D. B. and Grossmann, I. E. "Simultaneous production planning and scheduling in multiproduct batch plants", Ind. Eng. Chem. Res., 29, 570 (1990)

3. Brooke, A., Kendrix, D., Meeraus, A.: In GAMS : Users Manual, Scientific Press, Redwood City, CA(1992).

4. Moon, Seungdeuk, Sunwon Park, and Wonkook Lee, "New MILP models for scheduling of multiproduct batch plants under zero-wait policy", Ind. Eng. Chem. Res., (1996) in press

감사

본 연구는 학술진흥재단과 한국과학재단 지정 우수 연구센타인 포항공대의 지능자동화 연구센타를 통한 과학재단의 부분적인 재정적인 지원에 의해 수행되었으므로 이에 감사를 드립니다.

표 1. 예제에 따른 결과

		Birewar(RO)	Birewar(BR)**	Proposed
Volume [lt]	V1	6250.0	·	5982.9
	V2	7500.0	·	6000.0
	V3	4285.7	·	4494.4
	V4	7500.0	·	7200.0
No. of Batches	A	240	·	250
	B	240	·	234
	C	280	·	267
	D	240	·	251
	E	80	·	100
	F	80	·	67
Capital Cost [$]		190820.0	·	182787.8
Horizon [hr]		6008*	·	6000
CPU [sec]***			∞	39.65

*   denotes an infeasible solution.

**  cannot obtain any solution.

*** the time to solve the proposed MINLP using the NLP solver DICOPT+ through the GAMS on SUN/SPARC system.