다목적 회분식 공정의 최적 조업완료시간결정 알고리듬

박상대, 김형준, 정재학

영남대학교 화학공학부

Completion time Algorithm for single train multi-purpose batch process

Sangdae Park, Hyung Joon Kim, Jae Hak Jung

School of Chemical Engineering and Technology

Yeungnam University

1. 서론

다품종 회분식 공정과 다목적 회분식 공정의 생산계획에 있어 그 목적함수가 무엇인지에 따라 다소차이는 있겠으나 우선 고려해야할 문제가 조업완료시간 알고리듬의 결정이다. 다품종 회분식 공정에 있어서는 그 동안 많은 연구가 진행되었고 논문으로서 보고된 사례([1][2][3][4][5]) 또한 많았다. 그러나 다목적 회분식 공정에 대해서는 minimax algebra를 사용하여 matrix연산에 의해 해석한 논문[6]등을 제외하고는 수식으로 조업완료시간 알고리듬이 발표된 논문이 없었다.

본 논문에서는 새로운 형태의 변수들-다품종 회분식공정에는 없는-을 도입하여 UIS(Unlimited Intermediate Storage)에 대한 다목적 회분식 공정의 조업완료시간 알고리듬을 소개하고, 두가지의 예로서 그 알고리듬의 타당성을 시험하고자한다.

2. 본론

본 연구에서는 다목적 회분식 공정중 같은 task의 장치가 여러개가 있는 Network형태의 구조보다 기존의 다품종 생산공정의 한 task 한 unit 공정에서의 다목적 형태조업에 초점을 두었다. 다목적 회분식 공정의 UIS에 대한 조업완료시간 알고리듬과 다품종 회분식 공정의 UIS에 대한 조업완료시간 알고리듬과의 차이점을 비교하면서 조업완료시간 알고리듬을 수식으로 유도하였다.

2-1. 총 경우의 수(Total_Case)

다품종 회분식 공정: Total_Case = ( Np! )

다목적 회분식 공정: Total_Case= (Np1!)×(Np2!)×……×(NpM!)

Np : 처리해야할 모든 제품수

Npj : 각 장치에서 처리해야할 제품수 ( j=1,2,3,…,M-1,M )

2-2. 불가능한 조업순서의 경우

다품종 회분식 공정에 있어서 각 장치에서의 제품생산수서가 모두 동일하므로 모든 경우에 대해 불가능한 경우가 생기지 않았지만 다목적 회분식 공정에서는 공정의 특성상 각 제품의 경로가 일정하지 않고 각 장치에 있어서도 제품의 순서가 일정하지 않기 때문에 불가능한 경우가 발생하였다. 그 불가능한 경우는 각 제품의 경로를 화살표로 표시하였을 때 흐름의 방향이 같은것과 다른 것 두가지 경우가 생긴다. 본 논문에서는 흐름의 방향이 같은 것은 정방향제품, 다른 것은 역방향제품이라 정의하였다. 그중에서 정방향제품과 역방향제품이 지나는 장치들에서는 그 제품들의 순서가 동일해야한다. 그렇지 않은 경우에 불가능한 경우가 생긴다. 그러한 경우에도 어떤제품이 그 장치들중에서 처음 시작하는 장치가 있다면 그 경우는 예외가 된다. 그러므로 다목적 회분식 공정에서 불가능한 경우는 정방향제품과 역방향제품이 지나는 장치들에서 그 제품들의 순서가 동일하지 않고 그 장치들이 그 제품들의 처음 처리되는 장치가 아닌 경우에 발생한다.

2-3. 새로운 변수 도입

다품종 회분식 공정의 UIS에서의 조업완료시간은

[eqn: C_ij``=``max(```C_i,j-1```,``` C_i-1,j```) + t_ij]	(1)

이다. 여기서 i는 제품이고 j는 장치이고 [eqn: C_{0``j}`=0``,`` C_{i``0}`=0]이다.

다품종 회분식 공정에서는 모든 제품의 경로가 같고 각 장치에서 제품의 순서가 같기 때문에 i와 j만으로 수식을 결정할 수 있지만 다목적 회분식 공정에서는 각 장치에서의 제품의 순서와 각 제품의 경로가 각기 다르기 때문에 이들 또한 변수가 되어야 한다.

[eqn: U_ia] : i 제품이 a번째 처리되는 장치 ==> 각 제품의 경로

[eqn: P_jk] : j 장치에서 k번째처리되는 제품 ==> 각 장치에서의 제품순서

[eqn: S_ij] : i 제품이 j 장치에서의 순서

i=1,2,3,...,N , j=1,2,3,...,M , a=1,2,3,...,L , k=1,2,3,...,L

여기서 N은 제품수, M은 장치수, L은 max(Npj)이다.

2-4. 조업완료시간 알고리듬 유도

위의 세변수들이 각기 가지고 있는 값들을 살펴보면[eqn: U_ia]는 장치번호, [eqn: P_jk]는 제품번호, [eqn: S_ij]는 순서이다. 그러므로 식(1)에서 제품을 나타내는 i는 [eqn: P_jk]로, j는 [eqn: U_ia]로 바뀌고 다시[eqn: U_ia]는 [eqn: U_{P_jk, a}]로 바뀐다.

다품종 회분식 공정의 [eqn: C_ij]는 다목적 회분식 공정에서는 [eqn: C_{P_jk, j}]가 되고, [eqn: t_ij]는 [eqn: t_{P_jk, j}]가 된다. 그리고 [eqn: C_i-1,j]는 j장치에서 i제품보다 먼저 처리된 제품의 조업완료시간이므로 i-1대신 k-1번째로 j장치에서 처리된제품을 의미하는 [eqn: P_j,k-1]를 대입하면 [eqn: C_{P_j,k-1 `,` j}]이 된다. [eqn: C_i,j-1]은 i제품이 j장치로 전송되기전에 처리되었던 장치에서의 조업완료시간이므로 j-1대신 [eqn: U_{{P_jk} `,` {a-1}}]을 대입하면 [eqn: C_{P_jk `,` {U_{P_jk `,` a-1}}}]이 된다. 위의 과정을 종합해보면

[eqn: C_{P_jk `,` j} `=` max(`C_{P_j,k-1`,`j}``,``C_{P_jk `,` {U_{P_jk `,` a-1}}}``) + t_{P_jk`,`j}]	(2)

여기에서  변수 a대신 순서를 의미하는변수 [eqn: S_{P_jk`,`j}]를 대입하면 (2)식은 다음과 같이 된다.

[eqn: C_{P_jk `,` j} `=` max(`C_{P_j,k-1`,`j}``,``C_{P_jk `,` {U_{P_jk `,` {S_{P_jk``,``{j}}-1}}}}``) + t_{P_jk`,`j}]	(3)

유도과정에서 변수 k, a를 따로 지정한 것은 문제가 주어지면 [eqn: U_ia]와[eqn: S_ij]는 고정되는 상수들이지만 [eqn: P_jk]는 각 경우마다 변하기 때문이다. 초기 유도과정에서 다품종 회분식 공정에서의 변수( i, j )가 다목적 회분식 공정에서는 i, j, k, a의 네 개로 증가했지만 결국 j, k의 두변수로 되었음을 볼 수 있다.

2-5. 불가능한 조업순서의 경우에 대한 제거 방법

앞서 설명한 바와 같이 불가능한 경우에 대해 제품수와 장치수가 조금만 증가하여도 수작업으로 일일이 검사하기란 쉬운일이 아닐 것이다. 그래서 컴퓨터로 작업할 때 용이한 식이 (3)식이다. 다품종 회분식 공정에서는 각 제품의 각 장치에서의 조업완료시간이 순차적으로 계산되지만 다목적 회분식 공정에서는 순차적으로 계산이 되는 경우는 총 경우의수 중에서 극히 일부분이다. 그러므로 컴퓨터 작업시 다목적 회분식 공정의 조업완료시간은 전체과정을 수차례 반복함으로서 구할 수 있다. 이 과정에서 주어진 반복횟수내에 모든제품의 조업완료시간을 구하지 못하는 경우를 불가능한 경우가 될 것이다. 결국 다품종 회분식공정과 다목적 회분식공정의 makespan의 차이는 다음과 같다.

다품종 회분식 공정 : [eqn: makespan ``=`` C_NM]

다목적 회분식 공정 : [eqn: makespan ``=`` max(``C_ij``)]

3. 적용예

예제 1)

총경우의 수 : Total_case = (Np1)!×(Np2)!×(Np3)! = 2!×3!×2! = 24

Pjk	Uia	Sij

	1st	2nd	3rd			1st	2nd	3rd			U1	U2	U3
U1	A	B			A	U1	U2	U3		A	1st	2nd	3rd
U2	A	B	C		B	U1	U2			B	1st	2nd
U3	A	C			C	U3	U2			C		2nd	1st

예제 2)

총 경우의수 : Total_case = (Np1)!×(Np2)!×(Np3)!×(Np4)!

= 2!×3!×3!×3! = 432

Pjk	Uia	Sij

	1st	2nd	3rd	4th			1st	2nd	3rd	4th			U1	U2	U3	U4
U1	A	C				A	U1	U2	U3	U4		A	1	2	3	4
U2	A	C	D			B	U4	U3				B			2	1
U3	A	B	C			C	U3	U2	U1			C	3	2	1
U4	A	B	D			D	U2	U4				D		1		2

4. 결론

회분식 공정은 그 공정의 특수성을 가장 크게 반영하는 다품종 소량생산에 보다 유연히 대처하는 다목적 공정으로의 전환이 두드러지고 있으나 기존의 다품종 회분식 공정을 다목적 공정으로 사용하는 운전방식과 최적조업의 연구가 미비하였다. 본 연구는 이러한 다목적 공정의 최적조업을 가능케하는 다목적 공정에서의 조업완료시간결정 알고리듬을 보다효과적으로 구하였다. [6]의 연구에 비해 보다 알고리드믹하며, 또 큰 문제에서도 최적해의 계산 가능성을 보여주는 결과이기도하여 향후 연구결과가 기대된다. (3)식으로 조업완료시간을 구하는 과정은 다품종 회분식공정에서처럼 한번의 iteration으로 조업완료시간을 구할 수 있는 것은 아니다. 앞서 언급한것처럼 다목적 회분식 공정에서는 그 진행순서가 일정하지 않기 때문에 여러번의 iteration이 필요하다. 이번 연구에서는  그 iteration수를 [eqn: P_jk]의 component수로 정하였다. 그러나 그것이 최적 iteration수라 말할수 없기 때문에 최적 iteration수를 결정하는 것, set-up time 및 transfer time를 고려한 알고리듬 결정하는 것, SA, GA등의 최적알고리듬을 이용하여 최적생산계획을 하는 것, 다른 중간저장조에서의 알고리듬결정등이 앞으로의 과제일 것이다.

5. 감  사

본 연구는 포항공과대학교 공정산업의 지능자동화연구센터를 통한 한국과학재단 우수연구센터 지원금에 의한 것입니다.

6. 참고문헌

1. W. Wiede Jr and G. V. Reklaitis, "Determination of completion times for serial multiproduct process-2. A multiunit finite intermediate storage system", Computers chem. Engng., Vol. 11, pp. 345(1987)

2. D. Rajagopalan and I. A. Karimi, "Completion times in serial mixed-storage multiproduct processes with transfer and set-up times", Computers chem. Engng., Vol. 13, pp. 175(1989)

3. D. B. Birewar and I. E. Grossmann, "Efficient optimization algorithms for zero wait scheduling of multiproduct batch plants", Ind. Eng. Chem. Res., Vol. 28,  pp. 1333(1989)

4. Jung, J. H., Lee, H., Yang, D. R. and Lee, I., "Completion times and optimal scheduling for serial multi-product processes with transfer and set-up times in zero wait policy", Computers chem. Engng, Vol. 18, pp. 537-544, (1994)

5. 정재학, □다품종 회분식 공정의 최적생산계획 및 자동화모델□, (1994)

6. E. C. Yamalidou, E. P. Patsidou and J.C. Kantor, "Modeling Discrete-event Dynamical Systems for Chemical Process Control-A Survey of Several New Techniques", Computers chem. Engng. Vol. 14, No. 3, pp. 281-299,(1990)