ZW 방안의 다품종 회분식 공정의

생산 일정계획을 위한 효율적인 MILP 모델식

。문성득(정), 박선원(정), 이원국(정)

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

An Efficient MILP Model for Scheduling of

Multiproduct Batch Processes Under ZW Policy

。Sungdeuk Moon, Sunwon Park and Won Kook Lee

Department of Chemical Engineering

Korea Advanced Institute of Science and Technology

1. Introduction

회분식 공정은 공정 및 운전상의 유연성을 모두 갖추고 있어서 다양한 원료와 수요를 충족시킬 수 있으며, 시장 동향에도 신속히 대응할 수 있으므로 회분식 공정에 관한 연구가 활발히 진행되고 있다. 회분식 공정의 최적화는 생산할 제품과 이들이 거쳐야 할 장치들과의 적절한 조합에 의하여 제품의 생산순서를 계획함으로써, 정해진 제품들을 최단시간 내에 생산하는 것이 그 목적이라 하겠다.

특히, 다품종 회분식 공정의 scheduling에서 고려하는 일반적인 형태는 N 개의 제품, 일련의 순서로 정렬된 M개의 장치들에서, 생산하여야 할 모든 제품들의 순서를 적절히 정하여 생산에 소요되는 총시간을 최소화 하는 것이다. 또한, 다품종 공정의 scheduling 방법에는 중간저장탱크를 이용하는 방안에 따라 여러가지로 구분될 수 있는데, 그 중에서 고분자나 정밀화학 분야 등에서의 제품들은 반응이 계속적 으로 진행되므로 조업간에 대기시간이 있으면 제품의 변질이 우려되므로 이때에는 대기 시간없이 바로 다음 장치로 이동시키는 ZW(Zero Wait) 방안의 scheduling을 고려해야 한다.

기존에 발표된 ZW방안의 다품종 회분식 공정의 scheduling에 대한 수학적 모델식은 일반적으로 Traveling Salesman Problem (TSP) 기법[1,3]을 이용하여 최소의 makespan을 갖는 최적의 순서를 구하는 MILP 방법과, 조업 완료시간(completion time)기법을 이용하여 makespan을 결정하는 해법[2]으로 구분될 수 있다.

Jung 등[2]은 조업 완료시간 결정에서 이진변수(binary variable) Xis를 도입하여 제품 i가 s번째 조업 순서에서 조업되도록 하여, 마지막 제품의 조업 완료시간을 최소화하여 makespan을 최소화하는 방법을 제안하였다. 그러나, 수송시간과 준비시간이 고려된 다품종 회분식 공정의 최적 생산계획을 수립하는 데 있어서 이진변수 Xis는 비선형성(non- linearity)을 유발하게 되어 모델식은 MINLP로 수식화 된다. 일반적으로, 이러한 MINLP 모델식은 최적의 해를 보장하기가 어렵고, 또한 상대적으로 계산시간이 많이 걸리는 단점이 있기 때문에, 비선형성을 제거한 MILP의 형태로의 수식화에 많은 연구가 진행되고 있다[1,3].

최근에 Moon 등[3]은 제품의 조업 순서에 따라 각 장치에서 제품들 사이에 존재하는 조업 지연시간(idle time)을 먼저 계산하고, TSP 기법을 도입하여 이러한 지연시간들을 최소화 시킴으로서 makespan을 최소화하는 효율적인 MILP 모델식을 개발하였다. 일반적으로 TSP문제는 한 위치에서 시작하여 다시 처음 위치로 돌아오는 cyclic solution을 얻게 되므로 makespan은 이 cycle을 깨뜨려야만 얻을 수 있다. 그러므로, 저자들은 makespan을 이루는 순서(sequence)를 구하기 위하여 head time과 tail time을 고려하여, 기존의 방법[1]보다 이진변수와 제한조건들의 수가 훨씬 적으면서도 보다 효율적인 해법을 제시하였다. 그러나 이러한 모델은 계산 수행 이전에 지연시간, head time, tail time등을 먼저 계산해야 하는 단점이 있다.

그러므로, 본 연구에서는 조업 완료시간 결정법에 TSP의 개념을 도입하여 기존의 MINLP형태가 아닌 새로운 MILP의 형태로 수식화 하면서, 사전에 지연시간, head time, tail time 등을 계산절차를 거칠 필요가 없이 최소의 makespan을 갖는 최적의 조업순서를 결정하는 새로운 방법을 제시하고자 한다. 또한 기존의 방법들[2,3]과의 결과들을 비교하여 본 연구에서 제시된 방법이 우수하다는 것을 여러개의 예제를 통하여 비교하여 볼 것이다.

2. Mathematical Formulation for Minimizing the Makespan

ZW방안의 다품종 회분식 공정에서 수송시간(transfer time)과 준비시간(set-up time) 등을 고려할 때, 수송시간 Tik는 제품 i를 장치 k에서 k+1로 이동키는데 걸리는 시간이며, 준비시간 Sijk 는 장치 k에서 제품 i다음에 제품 j를 생산하기 위해 필요한 세척시간이나 준비시간을 말한다.

조업 완료시간 기법에서 이진변수 Xis는 제품 i가 s번째 조업순서에서 생산될때 1의 값을 갖고 그렇지 않을 때에는 0의 값을 갖도록 하고 있다. 그러나 이러한 정의 하에서는, 준비시간과 같은 순서에 의존하는 변수들이 모델식에 존재하게 되면 항상 비선형성이 나타나게 된다. 그러므로 TSP기법을 도입하여 이진변수 Xij를 제품 i 다음에 제품 j가 조업이 될 때를 1이 되도록 정의하게 되면 이러한 비선형성을 제거할 수 있다. 그러므로, 이진변수 Xij는 다음과 같이 정의하도록 하자.

[eqn: X_ij = CASES {&1~ rm if`` pro duct`` it i ``rm followed`` by`` pro duct ``it j #&0~ rm otherwise}]

그리고, 이진변수들에 대한 TSP 기법에서의 제한조건식들은 다음과 같다.

[eqn: SUM from { { i}=0} to N X_ij ~=~ 1],	[eqn: j `=` 0, CDOTS , N `]	(1)

[eqn: SUM from { { j}=0} to N X_ij ~=~ 1]	[eqn: i `=` 0, CDOTS , N`]	(2)

[eqn: SUM from { { i}=0} to N X_ii ~=~ 0]	(3)

위의 식(1)과 (2)는 각각의 제품이 한 번씩만 조업되도록 하는 제한조건들이며, 식(3)은 같은 제품을 다시 조업해서는 안된다는 제한조건식이다. 여기에서 제품 0는 처음으로 조업되는 제품과 마지막으로 조업되는 제품을 얻기위해 모델식에 추가된 가상적인 제품이다. 예를 들어, X03 = 1 이라면 처음으로 조업되는 제품은 제품 3이 된다. 또한 X10 = 1 이라면 마지막으로 조업되는 제품은 제품 1이 되는 것이다. 그리고, 나머지 N-2개의 제품들은 제품 3과 제품 1사이에서 모두 조업되어야 하는 것이다.

조업 완료시간 결정기법에서는 연속적으로 조업되는 두 제품들 사이에서 존재하게 되는 지연시간을 계산하기 위하여, 각 장치들에서 두 제품들을 조업하는 시간 중에서 가장 큰 시간을 기준으로 하여 각 장치에서의 지연시간들이 결정된다. 이러한 개념은 그림 1에서 나타내었다. 이 그림에서는 두 개의 제품이 4개의 장치에서 연속적으로 조업이 이루어 져 생산된다고 가정한다. 그림 1(a)에서는 두 제품 A, B가 ZW방안으로 연속적으로 조업이 이루어 질 때, 가장 긴 조업시간은 4번째 장치에서 나타나게 된다. 결국 제품 A 다음에 제품 B가 조업이 이루어 질 떄에는 94의 단위 조업시간을 갖게 되는 것이다. 즉, 4번째 장치 이외의 장치에서는 총 조업시간을 4번째 장치에 맞추어서 조업을 수행하여야만 ZW방안을 유지하며 조업을 수행할수 있다. 그러므로, 4번째 장치에서는 그때의 준비시간이 지연시간으로 되지만 나머지 3개의 장치에서는 준비시간 이외에, 조업 방식이 ZW 방안에서 조업되기 때문에 어쩔 수 없이 쉬어야 하는 지연시간이 필요하게 된다. 그림 1(b)에는 이러한 지연시간을 포함한 ZW방안의 조업에 대한 Gantt chart를 보여주고 있다.

그림 1(a)에서 처럼 연속적으로 조업되는 두 제품 i와 j에 대하여 가장 큰 조업시간을 Di라고 할 때, 이 값은 Jung 등[2]의 completion time algorithm에서와 같은 개념을 이용하여 다음과 같은 식으로 쉽게 얻어질 수 있다.

[eqn: D_i ~>=~ SUM from { { k}=0} to m T_ik `+` SUM from { { k}=1} to m P_ik `+` SUM from { { j}=0} to N LEFT ( S_ijm `+` SUM from { { k}=m-1} to M T_jk `+` SUM from { { k}=m} to M P_jk RIGHT ) X_ij]

[eqn: i `=` 0, CDOTS , N `], [eqn: m `=` 1, CDOTS , M `]	(4)

식(4)에서 Di는 제품 i에 대한 정보만 포함하고 있고 제품 j에 대한 정보는 단지 이진변수 Xij에만 포함되어 있다. 그러므로, Di가 가장 작은 값을 갖도록 하기 위하여 적절한 제품 j가 결정되고 그때 Xij = 1이 되는 것이다. 결국, 이렇게 하여 결정된 이진변수들은 제품의 조업순서를 포함하는 것이다.

그러나, 구하고자 하는 makespan은 Di의 형태에서는 구할 수 없으므로 다음과 같은 연속변수들을 정의하여야 한다. 즉, 장치 m에서 제품 i의 수송시간 및 조업시간과 제품 j사이에서 존재하는 지연시간의 합인 Cim은 다음과 같이 나타낼 수 있다.

[eqn: C_im ~=~ D_i ~-~ SUM from { { j}=0} to N LEFT ( SUM from { { k}=m-1} to M T_jk `+` SUM from { { k}=m} to M P_jk `+` SUM from { { k}=0} to m-2 T_ik `+` SUM from { { k}=1} to m-1 P_ik RIGHT ) X_ij]

[eqn: i `=` 0, CDOTS , N`], [eqn: m `=` 1, CDOTS , M`]	(5)

변수 Cim은, 그림 1(b)에 나타난 것처럼, 각각의 장치에 대하여 다른 값을 갖게 된다. 또한 본 연구에서 사용한 가상제품을 포함한 모든 제품들에 대한 값들이 계산되므로, 모든 제품에 대한 Cim의 합을 각각의 장치에 대하여 구할 수 있고, 그중에서 가장 큰 값이 바로 makespan, MS이 되며, 다음과 같은 식으로 표현될 수 있다.

[eqn: MS ~>=~ SUM from { { i}=0} to N C_ik]	[eqn: m `=` 1, CDOTS , M`]	(6)

결국, 목적함수는 makespan, MS를 최소화 하는 것이다.

min MS	(7)

목적함수 (7)은 ZW방안의 다품종 회분식 공정의 makespan을 최소로하는 조업순서를 결정하기 위하여, 식(1)부터 식(6)까지의 제한조건들을 만족하여야 한다. 본 연구에서 제안한 MILP모델식에서, 제한조건은 (2N+3)(M+1)+1이 존재하며, 연속변수(continuous variable)는 (N+1)(M+2)+1개, 이진변수는 (N+1)2개가 존재하는, 아주 작은 크기의 모델식으로 이루어져 있다.

3. Results and Discussion

다품종 회분식 공정에서 ZW방안으로 조업이 이루어지는 두 개의 예제를 통하여, completion time 기법[2]에 의한 MINLP 모델식과, Moon 등[3]이 제안한 MILP 모델식과, 본 연구에서 제안한 MILP 모델식의 결과들을 비교하여 새로운 MILP 모델식의 효율성을 입증하고자 하였다. 예제 1은 4개의 장치를 사용하여 4개의 제품을 생산하는 경우를 고려한 것이고, 예제 2는 4개의 장치를 사용하여 8개의 제품을 생산하는 경우를 고려한 것이다. 각각의 예제에 대한 data들은 Jung 등[2]이 사용한 것을 그대로 사용하였다. 모델식들은 GAMS를 사용하여  SUN/SPARCS station상에서계산을 수행 하였고, 특히 MILP 모델식들은 OSL solver로, MINLP 모델식은 DICOPT++ solver를 이용하여 계산되었다.

예제 1에 대한 결과 비교는 표 1에 나타내었다. 표 1에서 나타난 것처럼, MINLP는 MILP에 비교하여 makespan이 큰 값으로 나타났다. Moon 등[3]이 제안한 MILP 모델식의 결과에서는 최소의 makespan을 얻을 수 있었지만, 계산시간에 지연시간, head time, tail time 등의 계산시간등이 포함되어져 있어 상대적으로 계산시간이 많이 소모되었다. 본 연구에서 제안된 새로운 MILP모델식에 의한 결과를 살펴보면, 다른 두 개의 모델식과 비교하여 이진변수와 연속변수들의 개수가 많기는 하지만 최소의 makespan을 갖는 최적의 조업 순서를 제시하였고 계산시간은 가장 작게 소모되었다.

마찬가지로 예제 2의 결과를 표 2에 나타내었다. 보다 큰 규모의 예제에서 MINLP는 상당히 큰 계산시간이 필요하였다. 그러나 두 MILP 모델식에 의한 결과는 모두 만족할 만한 계산시간이 필요하였다. Moon 등[3]이 제안한 MILP 모델식의 결과에서 예제 2에 대한 해에는 subcycle이 존재하여 subcycle elimination constraint[1]를 추가하여 재 계산된 결과가 계산시간에 함께 포함되어 있다. 하지만 제안된 모델식의 결과에서는 subcycle이 존재하지 않는 해를 단 한 번에 얻을수 있었다. 그러므로, 본 연구에서 제안된 MILP 모델식은 기존의 MILP 모델식 보다도 효율적으로 최적해를 찾아 가는 것을 알수 있고, 또한 기존에 발표된 다른 모델식들[2,3] 보다 더 우수한 결과를 얻을수 있었다.

Reference

1.	Birewar, D.B. and Grossmann, I.E., □Efficient Optimization Algorithms for Zero Wait Scheduling of Multiproduct Batch Plants.□ Ind. Engng. Chem. Res., 28, 1333 (1989).

2.	Jung, J.H., Lee, H., Yang, D.R., and Lee, I., □Completion Times and Optimal Scheduling for Serial Multiproduct Processes with Transfer and Set-up Times in Zero-Wait Policy.□ Comput. Chem. Engng., 18, 537 (1994).

3.	Moon, S., Park, S., and Lee, W.K., □New MILP Models for Scheduling of Multiproduct Batch Plants under Zero-Wait Policy.□ Ind. Engng. Chem. Res., (1996) in press.

Acknowledgment

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

Table 1. Comparison of results obtained from proposed model and others for

Example 1 : 4 products and 4 units[2]

	Proposed MILP	MINLP[2]	MILP[3]
Optimal sequence	1-4-2-3	2-4-1-3	1-4-2-3
Optimal unit time	130	134	130
No. of Constraints	56	73	19
No. of Continuous variables	31	21	1
No. of Binary variables	25	16	24
CPU time□	0.55 sec	1.79 sec	2.08 sec

□the time to solve two MILP models using the OSL solver and one MINLP model

using the DICOPT++ solver through the GAMS on SUN/SPARCS station.

Table 2. Comparison of results obtained from proposed model and others for

Example 2 : 8 products and 4 units[2]

	Proposed MILP	MINLP[2]	MILP[3]
Optimal sequence	5-1-6-3-7-4-2-8	5-4-8-7-2-1-6-3	5-1-6-3-7-4-2-8
Optimal unit time	195	198	195
No. of Constraints	96	241	40
No. of Continuous variables	55	73	1
No. of Binary variables	81	64	80
CPU time□	3.47 sec	201.9 sec	6.41 sec

□the time to solve two MILP models using the OSL solver and one MINLP model

using the DICOPT++ solver through the GAMS on SUN/SPARCS station.