순서의존 준비시간을 고려한 순차적 다목적 회분식 공정에 대한 일정

계획

강진수1 , 복진광1 , 문성득2 , 박선원1 , 이태용1*

1 한국과학기술원 화학공학과,  2 McMaster Univ. Dept. of Chem. Eng

Scheduling of special multipurpose batch processes

with sequence dependent set-up times

Jinsu Kang1,Jin-Kwang Bok1,Sungdeuk Moon2,Sunwon Park1 and Tai-young Lee1*

1 KAIST, 2 McMaster Univ. Dept. of Chem. Eng

1. 서론

회분식 공정은 생산물에 요구되는 생산경로를 고려하여 분류된다. 모든 생산물이 같은 순서로 장치를 거친다면 그 회분식 공정은 다품종 회분식 공정으로 분류될 것이다. 다목적 회분식 공정은 방법에 있어서 다른 장치 순서를 따르는 여러 종류의 생산물을 생산한다. Voudouris와 Grossmann [1]에 따르면 다목적 회분식 공정은 순차적 조업(sequential)과 비순차적 조업(non-sequential)으로 구분될 수 있다. 순차적 다목적 회분식 공정에서는 모든 생산물의 생산 경로는 방법에 있어 같은 장치 순서를 따른다. 그러나 꼭 모든 장치를 포함할 필요는 없다. 비순차적 다목적 회분식 공정은 나머지 경우를 말한다. 이 논문에서는 순서의존 준비시간을 포함하는 순차적 회분식 공정의 단기 일정계획을 위한 새로운 수학적 모델(MILP)을 제안한다. 이 모델은 조업 순서를 결정하기 위해 사용되는 event slot의 정의에 기초해서 발전된다. 모든 제품의 회분은 event slot에 할당되고, 필요한 제품 수만큼의 event slot이 있다. Event slot의 정의를 사용하여 순차적 회분식 공정의 scheduling 은 single machine 문제로써 다룬다. 또한 순서의존 준비시간을 고려하여 좀 더 실제에 가까운 모델을 제안한다.

2. MATHEMATICAL MODEL

순차적 다목적 회분식 공정의 일정계획을 위한 MILP의 수학적 식이 여기서 제안된다. MPC에서 다목적 회분식 공정을 가정하고 중간저장 방식은 UIS 정책이라고 가정한다. 이진변수 [eqn: X_ikr]를 도입하여 제안된 모델의 주요 특징은 다음과 같이 정의된다.

(1) 최소의 makespan을 가진 조업 순서를 고르기 위해 event  slot을 사용

(2) 각각의 생산물을 위한 특정한 생산 경로의 선택

이진 변수 [eqn: X_ikr]은 다음과 같이 정의된다.

[eqn: X_ikr] =  1, 제품 i가 event slot k에 할당 되고, 생산 경로 r 을 통해 생산된다             0, 그 밖의 경우

4개의 생산물과(I=4) 4개의 장치(J=4)로 구성된 예를 생각해 보자. 생산물 i는 3개의 생산 stage(production stage)를 통해 생산된다고 가정하자. 생산물 i의 첫 번째 stage는 장치 1 또는 장치 2를 통해서 수행된다. 장치 3과 장치 4는 그림 1에서 보여지는 대로 두번째와 마지막 stage에서 각각 행해진다. 이 그림에서 생산물 i를 위한 두 개의 생산 경로(production  path)가 생긴다. 왜냐하면 두 개의 장치(장치 1과 장치2) 가 평행하게 수행되기 때문이다. production path 1은 장치 1, 3, 4로 구성되고 path 2는 장치 2, 3, 4로 구성된다. 생산물 i를 제조하기 위해서 이 두개의 path 중 하나가 선택되어야 한다. 제조되는 생산물들의 모든 회분이 포함되는 조업 순서에서 각각의 생산물은 하나의 event slot에 할당되어야 한다. path 1이 선택되었을 경우 그림 1에서 보여지듯, 생산물 i를 위한 회분에 event slot k가 할당되었다면 이진 변수 [eqn: X_ik1]은 1이 된다. 필요한 event slot의 수가 필요한 회분의 수, N과 같다는 사실에 주목하자. (예를 들면  [eqn: LEFT | K RIGHT |=N= SUM from { i }n_i])

단일장치 할당모델에 대한 준비시간 고려 모델을 생각해 보자. Sahinidis와 Grossmann[2]은 time slot k에 선행 생산물 i와 후행 생산물 i'의 할당을 나타내는 이진변수 [eqn: Z_ii'k]를 도입하였다. 각 생산물 i의 time slot k에 할당을 나타내는 이진변수 [eqn: X_ik]와의 관계를 나타내면 식 (1)과 같이 된다. 즉 생산물 i가 time slot k에 할당되고 생산물 i'이 바로 다음 time slot 인 k+1에 할당되었을 때, [eqn: Z_ii'k]가 1의 값을 지니게 되는 것이다. Event slot k에 있는 장치 j를 위한 시작 시간 [eqn: Ts_kj]와 끝나는 시간 [eqn: Te_kj]는 식(2)와 같이 정의될 수 있다.[eqn: P_ij]는 장치 j에서 생산물 i의 조업 시간이고 [eqn: R_ij]는 장치 j를 포함하는 생산물 i의 조업 path의 set을 나타낸다. 장치 2는 경로 1을 포함하지 않기 때문에 장치 2에서 생산물 i를 위한 시작 시간([eqn: Ts_kj])과 완성 시간([eqn: Te_kj])은 그림 1에서와 같이 0으로 맞춰진다.

[eqn: Z_ii'k >= SUM from {r} X_ikr +SUM from {r} X_i',k+1,r - 1~~~~~~~~~~~~~~FORALL {i,i' IN I},{k IN K-k*} ~~~~~~~(1)]

[eqn: Te_kj - Ts_kj = SUM from {{i} IN I} SUM from {{r} IN R_ij} X_ikr P_ij +SUM from {{i'}} SUM from {{i}} Z_ii'k S_ii'j~~~~~~~~FORALL k IN K, j IN J~~(2)]

k*는 마지막 event slot을 나타낸다.

그럼 순서의존 준비시간을 고려한 순차적 다목적 회분식 공정 모델을 예제에 적용시켜 봄으로써 그 유용성을 살펴보기로 하자.

3. 예제

MILP문제는 모델링 시스템 GAMS(Brooke et al.)[3]에서 MILP solver OSL(IBM, )[4]를 사용해서 SUN/SPARC 10 에서 풀었다. MILP의 성능을 증명하기 위해 Voudouris와 Grossmann(1996)[1]에서 예제 1로 보고된 순차적 다목적 회분식 공정의 일정계획 예제를 여기서 사용한다. 예제 1은 10개의(N = 10) 회분, 4 개의 다른 생산물 A-D 그리고 단계 당 하나의 장치를 가지는 5개의 장치로 구성되어 있다. 이 예제에서, 각각의 생산물을 위한 생산 경로는 하나이다. 예제 1의 MILP1은 240 개의 이진 변수, 361 개의 연속 변수, 521 개의 제약식으로 구성되어 있다. 해답을 얻는데 MILP solver OSL.를 사용하였을때는 88.97s, MILP solver CPLEX를 사용하여 풀었을 때는 54.33s의 시간이 걸렸다. 아래 Table 1-3은 예제에 대한 자료와 결과이고 Gant Chart를 그려보면 그림 2와 같다.

Table 1. Processing time of 예제

P(i,j)	1	2	3	4	5
A	8.0			5.0	3.0
B	7.0		3.0		4.0
C		6.0		9.0	3.0
D		4.0	6.0		4.0

Table 2. Sequence dependent set-up time of 예제

s(i,i',j)	1	2	3	4	5
B-A	2.0	2.0	2.0	2.0	2.0
C-A	1.0	1.0	1.0	1.0	2.0
D-A	1.0	1.0	1.0	1.0	2.0
A-B	1.0	2.0	2.0	2.0	1.0
C-B	3.0	3.0	3.0	2.0	1.0
D-B	2.0	3.0	3.0	2.0	2.0
A-C	1.0	1.0	1.0	1.0	1.0
B-C	2.0	2.0	3.0	3.0	3.0
D-C	3.0	2.0	1.0	2.0	1.0
A-D	1.0	1.0	1.0	1.0	1.0
B-D	2.0	2.0	2.0	2.0	3.0
C-D	3.0	3.0	3.0	3.0	1.0

Table 3. 일정계획 solution obtained from 예제

	N(A,B,C,D)	No. of constraints, variables (binary)	MS	Production sequence	CPU*(sec), OSL (No. of iteration )	CPU*, CPLEX (No. of iteration)
Ex.1	12 (3,3,3,3)	521, 361 (240)	74	D-D-D-A-A-B-C- B-C-B-C-A	88.970 (7796)	54.333 (12649)

4. 결론

이 논문은 MPC정책 아래 다목적 회분식 공정을 위한 MILP모델을 발전시켰다. 제안된 모델에서 주어진 생산물을 위한 적당한 생산경로의 선택과 event slot에 모든 생산물의 회분의 할당은 이진변수 [eqn: X_ikr]를 정의함으로써 얻어질 수 있었다. 또한 순서의존 준비시간을 고려함으로써 보다 실제에 가까운 모델을 얻을 수 있었다.

감 사

본 연구는 한국과학재단 지정 우수 연구센터인 공정산업의 지능 자동화 연구센터의 연구비 지원에 의하여 이루어진 것으로서, 연구비를 지원해 주신 연구센터에 감사드립니다.

참고도서

[1]Voudouris V.T. and I.E. Grossmann, MILP Model for 일정계획 and Design of     a sequential Class of Multipurpose Batch Plants. Computers Chem. Engng.          20(11), 1335 (1996).

[2]Sahindis, N.V., Grossmann, I.E. : Computers Chem. Engng. 15, 85(1991)

[3]Brooke A., D.Kendrich and A.Meeraus, GAMS-A user's guide (release 2.25). The    Scientific Press, San Francisco CA (1996).

[4]OSL, OSL, Guide and Reference (release 2). IBM, Kingston, NY (1991)