수송 및 준비시간을 고려한 다제품 회분식 공정의

최적생산 방안을 위한 혼합 정수 선형 모델

변승헌□이해평□김경숙*□류경옥

한양대학교 공과대학 화학공학과, 동양공업전문대학 화학공학과*

Mixed Integer Linear Model for the Scheduling of

Multiproduct Batch Processes with  Transfer and Setup Times

Seung Heon Byun, Hae Pyeong Lee, Kyong Sook Kim, Kyong Ok Yoo

Dept. of Chem. Eng., College of Eng., Hanyang University

1. Introduction

최근 들어 화학공업산업에서 연속공정이 보편화되어가고 있지만 고부가가치의 정밀 화학제품에 대한 수요가 커짐에 따라 제약제품, 식품, 생물화학제품등과 같이 정밀성을 요구하는 고부가가치의 소량생산물이나 유사한 생산경로를 통해 생산되는 다품종 제품의 생산에 적합한 회분식공정에 대한 관심이 증가되고 있다. 이러한 회분식 공정은 연속 공정과는 달리 많은 노동력의 요구, 다음 조업을 위한 장치의 제정비등 많은 생산경비가 소요되어 조업의 여지가 매우 큰 공정으로  회분식 공정에서 생산성효율의  최적화는 생산할 제품과 장치들과의 적절한 조합에 의하여 제품의 생산순서를 계획함으로써 정해진 제품들을 최단시간내에 생산하는 것이 그 목적이다.

다품종 회분식공정의 scheduling방법에는 중간저장탱크의 사용방안에 따라 UIS, FIS, NIS, ZW방안등이 있으며 Jung등[1]은 수송시간과 준비시간이 고려된 다품종 회분식공정에서 MINLP모델식을 통하여 최적 생산계획을 수립하였다. 그러나,  이진 변수( binary variable) [eqn: X_ij]의 비선형성으로 인한 MINLP모델식은 일반적으로 최적해를 찾아가는 과정에서 local optimum에 빠질 경우 더 이상의 search를 하지않고 해답으로 받아들임으로 최적해를 보장할 수 없다는 단점을 갖고 있다. 따라서 본 연구에서는 MINLP식들을 MILP로 모델링함으로서 최적해를 찾아내고 기존의 MINLP나 combinatorial exhaustive search방법 등의 제품수의 한계를 어느 정도 극복하기 위해 heuristic에 extensive search 방식으로서 본 연구에서 제안한 MILP모델을 도입함으로써 제품 size가 클 경우에 보다 나은 준최적해를 구할수 있는 방법을 제시하고자 한다.

2. MILP formulation

다품종 회분식 공정에서 수송시간[eqn: a_ik]는 제품 i를 장치 k에서 k+1로 이동시키는데 걸리는 시간이며, 준비시간[eqn: S_lik]는 장치 k에서  제품i 다음에 제품 l을 생산하기 위해 필요한 세척시간이나 준비시간이다. 조업 완료시간인 makespan을 구하기 위하여 MINLP모델식과는 달리 이진변수[eqn: X_ij]이외에 이진변수[eqn: Y_lij]를 도입하여 비선형성을 제거할 수 있다. 그러므로 이진변수[eqn: Y_lij]를 다음과 같이 정의한다.

[eqn: Y_lij = CASES{ 1 & i가~ j위치에 ~있고~ l이~ j-1위치에 ~있을때 # 0 & 그렇지 않을때 }]

그리고 , 이진변수   [eqn: Y_lij]과[eqn: X_ij]의 제한 조건식들은 다음과 같다.

[eqn: Y_lij >=X_ij +X_l(j-1) -1]	(1)

[eqn: Y_lij <= 1over2 ( X_ij +X_l(j-1) )]	(2)

[eqn: SUM FROM i=1 to N Y_iij =0]  (j=2,....N)	(3)

[eqn: SUM FROM i=1 to N X_ij =1 (j=1,2,...N)]	(4)

[eqn: SUM FROM j=1 to N X_ij =1 (i=1,2,...N)]	(5)

식 (1)과 (2)는 [eqn: X_ij]과 [eqn: X_l(j-1)]의 값이 1인 경우만 [eqn: Y_lij]값에 1을 할당하고 그 이외에는 0을 할당하게 나타낸 식이다. 또 식 (3)은 제품i 다음에 제품i가 조업할 수 없다는 것을 나타낸다. 본 연구에서는 UIS방침과 NIS방침을 다루었다.

2-1 UIS공정에서 MILP formulation

UIS공정의 경우 저장탱크가 무한대라고 가정하는 공정으로서 다음과 같이 나타낼 수 있다.

[eqn: C_jk >=C_j(k-1) +sum from i=1 to N X_ij (a_i(k-1) +t_ik )]

[eqn: C_jk >=C_(j-1)k +sum from l=1 to N a_lk X_l(j-1) +sum from i=1 toN SUM from l=1 to N Y_lij S_lik +SUM FROM i=1 to N X_ij (a_i(k-1) +t_ik )]            목적함수는 공정완료시간을 최소화하는 것으로서 다음과 같다.

Objective Function : Min [eqn: C_NM +sum from i=1 to N a_iM X_iN]

2-2 NIS공정에서 MILP formulation

NIS공정의 경우 저장탱크가 없다고 가정하는 공정으로서 다음과 같이 나타낼 수 있다.

[eqn: C_jk >=C_j(k-1) +sum from i=1 to N X_ij (a_i(k-1) +t_ik )]

[eqn: C_jM >=C_(j-1)k +sum from l=1 to N a_lk X_l(j-1) +sum from i=1 toN SUM from l=1 to N Y_lij S_lik +SUM FROM i=1 to N X_ij (a_i(k-1) +t_ik )]

[eqn: C_jk >=C_{(j-1)(k+1)} +sum from l=1 to N a_l(k+1) X_{l(j-1)} +sum from i=1 toN SUM from l=1 to N Y_lij S_li(k+1)]

목적함수는 UIS공정과 마찬가지로 다음과 같다.

Objective Function : Min [eqn: C_NM +sum from i=1 to N a_iM X_iN]

3. Approximate MILP formulation

MINLP나 MILP formulation의 경우 제품 수와 장치수의 증가에 따라 CPU time이 exponential하게 증가하고 제품수는 8개 정도가 한계였다. 그러나 모든 저장 방침을 고려해 줄 수 있는 MILP formulation은 그 정확성으로 인해 dispatch rule을 이용한 기존의 heuristic에 local search 방식으로서 적용하는데  다른 접근 방법보다 효율적인 방법이 된다. 기존의 MILP formulation이 제품이 존재하는 범위를 모든 위치로 두고 풀어 나가는 것과는 달리 본 연구에서는 NH(New Heuristic)[2]을 통해 나온  준최적해를 초기해로 둠으로써  제품의 존재 범위를 제한하는 방법을 사용했다. 예로써 만약 제품수 N이 10일 경우 Heuristic을 통해 나온 값중 5번째 위치에 해당하는 제품이 MILP에서 고려해줘야 할 위치는 3, 4, 5, 6, 7 위치로 한정한다.

4. Results and Discussion

본 연구는 UIS방침과 NIS방침에 따른 다품종 회분식공정의 예제들에서  제안된  MILP모델과 Approximate MILP와 MINLP모델식, NHES(New Heuristic Extensive Search)를 비교하여 그 효율성을 입증하고자 하였다. 예제는 제품수 6개와 장치8개를 사용한 예제와 Jung 등[1]이 사용한 제품수 8개와 장치4개를 사용한 예제를 그대로 사용하였다. 모델식들은 GAMS를 사용하여 SUN/SPARCS station상에서 계산을 수행하였고, MILP모델식들은 OSL solver로, MINLP 모델식들은 DICOPT++ solver를 사용하여 계산하였다.

예제 1의 경우 NIS방침일 경우 제안된 MILP와 MINLP모델식이 같은 makespan값을 갖지만 UIS방침에서는 MINLP모델식이 269로 local optimum에 빠지는 것을 볼 수 있다. 또 NH을 통해 나온 sequence인 2-3-5-4-6-1을 초기해로 두고 Approximate MILP 모델을 계산한 경우 같은 값을 가지면서 CPU time이 줄어들었다. 이는 예제 2에서 더 현격히 나타난다. 또 기존의 heuristic인 NHES방안보다 훨씬 나은 준최적해를 찾아가는 것을 볼 수 있다.

Table 1. 예제 1의 각 모델식의 비교

	proposed MILP		MINLP		Approximate MILP		NHES
	uis	nis	uis	nis	uis	nis	uis	nis
makespan	265	271	269	271	265	271	288	297
sequence	5-2-3-6-1-4	5-3-2-6-1-4	5-6-1-4-2-3	5-3-2-6-1-4	5-2-3-6-1-4	5-3-2-6-1-4	2-3-4-6-5-1	3-2-6-4-5-1
CPU time	26.0901	29.1501	42.0301	41.8601	5.2001	4.8201

Table 2. 예제 2의 각 모델식의 비교

	proposed MILP		MINLP		Approximate MILP		NHES
	uis	nis	uis	nis	uis	nis	uis	nis
makespan	173	185	173	185	174	188	182	190
sequence	5-4-1-7-2-6-3-8	5-7-2-4-1-6-8-3	5-7-1-2-6-8-4-3	5-7-2-4-1-6-8-3	5-7-4-1-6-2-3-8	5-7-4-1-6-2-3-8	5-4-1-6-7-2-3-8	5-4-1-6-7-2-3-8
CPU time	395.2601	945.5601	120.68	154.55	10.5601	18.2201

5. References

1. Jae Hak Jung, In-Beum Lee, Dae Ryook Yang, Kun Soo Chang :

Institution of Chemical Engineers Symposium Series No.133 Publ

by Inst of Chemical Engineers, Rugby, Engl. p 79-86 (1994).

2. 김경숙, 조영상, 이현구 : 화학공학 32(3), 265 (1994).

Figure 1.   예제 1의 UIS방침

Figure 2.   예제 1의 NIS방침

Table 3. 예제 1의 processing time     Table 4. 예제 1의 transfer time

	U1	U2	U3	U4	U5	U6	U7	U8
P1	10	20	5	30	10	35	15	21
P2	15	8	12	10	23	22	17	28
P3	20	7	9	5	18	19	22	13
P4	13	7	17	10	24	7	18	14
P5	8	3	16	7	20	19	25	26
P6	6	9	22	7	10	5	15	18

	U0	U1	U2	U3	U4	U5	U6	U7	U8
P1	2	2	2	2	3	3	3	2	3
P2	3	3	3	3	1	2	2	3	2
P3	2	4	2	2	1	3	3	1	2
P4	2	2	1	4	2	2	1	2	1
P5	1	1	1	3	2	3	2	2	2
P6	3	3	2	2	2	2	1	3	4

Table 5. 예제 1의 setup time

(sequence oriented )

	P1	P2	P3	P4	P5	P6
P1	0	3	2	1	1	3
P2	4	0	1	3	3	1
P3	2	1	0	2	2	2
P4	4	1	3	0	1	3
P5	2	2	2	1	0	4
P6	1	3	4	2	2	0

(에제 2의 데이터는 References에 있는 예제이므로 생략)