순서 가지 방법을 이용한 회분식 공정의 단기일정계획

복 진광, 이 승권, 박 선원

대전 유성구 구성동 373-1 한국과학기술원 화학공학과

Short-term scheduling of batch processes using SBM (Sequence Branch Method)

Jinkwang Bok, Seungkwon Lee, and Sunwon Park

Dept. of chemical engineering, KAIST

373-1, Taejon, Korea

서론

다품종 소량생산이 중요성이 부각되면서 활기를 띄게 된 회분식 공정의 스케쥴링에 대한 연구는 70년대 이후 활발하게 진행되어오고 있다. 최근의 연구방향은 실제 공정에 적용을 위한 보다 엄격하고(rigorous) 효과적인 알고리즘 개발에 초점을 맞추어, 다루는 대상문제 정의도 다양화·복잡화 되어오고 있다. 모든 생산품이 동일한 생산 순서를 갖기 때문에 생산품의 조업 순서만을 결정하는 다목적(multiproduct) 회분식 공정의 스케쥴링은 효과적인 수학적인 모델링을 이용한 방법이 지배적인 반면, 각 생산품이 각기 다른 조업과정을 거치게 되는 다목적(multipurpose) 회분식 공정에 대한 적용은 미비한 편이다. 이는 다목적 공정에 대한 스케쥴링 문제를 수학식으로 모델링 할 경우 혼합정수계획법(mixed integer linear programming)으로 표현되고, 시간 domain을 나타내려면 다량의 이진변수가 불가피하기 때문이다. 이는 곧 알고리즘의 효율성을 따지는데 직결하는 계산시간(CPU time)과 직결된다. 이러한 난점을 해결하고자 제안되는 모델링 방식으로 연속시간 표현법(continuous time representation)이 활발하게 연구되어오고 있다(Pinto, 1995; Bok and Park, 1997). 기존의 이산시간 표현법(discrete time representation)이 시간관점에서 각 시간 interval에서 사건(event)의 발생여부를 결정하는 이진변수를 요구하는 반면, 연속시간 표현은 사건관점에서 발생한 시작시간과 종결시간을 결정하기 때문에 훨씬 효과적인 모델링을 할 수 있다는 게 장점이다. 특히 multi stage process와 jobshop scheduling 같은 문제를 이산시간 표현법으로 나타내고자 할 경우 모델링을 풀 수 있는 효과적인 MILP solver가 부재(不在)한 상태이다. Pinto (1995)가 제안한 연속시간 표현법은 효과적으로 multi stage process에 적용되었지만 다목적 공정의 성격을 여전히 유지하고 있다. Bok and Park (1997)은 각 생산품이 각기 다른 공정경로를 거치고 또 재진입(reentrant) 공정이 있는 문제까지 표현할 수 있도록 발전시켰다. 하지만 수학적인 모델링이 가지는 근본적인 문제들, 즉 routing 유연성(flexibility)과 lot sizes 등을 모델식으로 나타내는데 어려움은 아직 해결하지 못한 상태이다. 이에 본 연구에서는 새로운 연구방법으로 순서 가지 방법(sequence branch method, SBM)을 제안하고자 한다.

본론

다루고자 하는 대상문제는 N개의 product i가 M개의 unit k를 각기 다른 조업방식으로 거치는 경우로 재진입이 있는 jobshop 스케쥴링 문제이다. product i가 unit k를 거치는 한 과정은 하나의 stage l로 표시될 수 있다. 재진입이 있는 관계로, 각 product i의 조업시간과 이동시간은 unit과 stage에 따라 결정된다. 이미 거쳐간 동일한 unit를 재 진입할 때, stage에 대한 정보를 나타냄으로써 이를 먼저 일어난 공정과 구별할 수 있기 때문이다.

그림 1. SBM의 개념도.

순서 가지 방법이란 그림1에서와 같이 발생 가능한 조업경로를 nod와 branch로 구성해서 가장 짧은 makespan을 갖는 경로를 찾는 알고리즘이다. 한 node는 순서쌍 (product, stage)로 표현되고, 이를 기본으로 해서 발생 가능한 사건을 다음 node로 표현한다. 이 경우 생성된 node들은 선행 node에 비해 depth의 크기가 1만큼 더 커지게 된다. node가 생성됨과 동시에 그 node에 해당하는 완성시간(completion time)이 계산된다. 이들 각각에 대해 완성시간을 비교해서 가장 짧은 완성시간을 갖는 node에서 다음 세대 node를 생성시키고 나머지는 휴지(休止)상태로 놔둔다. 만약 생성된 새로운 node의 완성시간의 크기가 휴지상태 node보다 클 경우, 현재의 node는 휴지상태가 되고 완성시간의 크기가 작은 node에 대해 다음 세대의 node를 생성시킨다. 한 stage에 참여할 수 있는 unit의 수는 여러 개이므로 이 중 해당 product를 수행했을 때 완료시간을 가장 줄일 수 있는 unit를 선택하게 되야하고 이는 다음 수식으로 표현할 수 있다.

[eqn: C_ij = { min} atop {k } left{{C_ij-1 + (P_ijk +T_ijk ) } right}]	for  i, j	(1)

이러한 작업은 모든 product의 생산경로가 종료될 때까지 계속된다. 실제로 이러한 방법만을 고려한 것은 발생 가능한 경우의 모든 node를 생성시키는 결과를 낳기 때문에 전체 스케쥴링 결과를 얻어내는데는 상당한 시간이 필요하게 된다. 이것은 Petri nets 알고리즘을 스케쥴링에 구현한 것의 하나인 A* 알고리즘(Pearl, 1984)과 유사한 결과를 만들어내게 된다. 여기서 계산할 node 수를 줄이고자 사용된 heuristic이 있다. 목적함수, 즉 완료시간에 Weight x depth를 더해주는 것이다. 계산시간을 줄이고자 depth가 큰 것에 그 만큼의 가중치를 주자는 알고리즘이다. 결국 각 node에서 비교하게 되는 목적식은 다음과 같다.

[eqn: O_ij = C_ij + omega TIMES depth]	for i, j	(2)

예제

SBM을 이용해서 반복생산을 특징으로 하고 있는 반도체 공정에 적용해보았다. 문제에 필요한 데이터는 Moon and Park (1996)에 의거해서 다음과 같다.

Table 1. Processing time for example

route	stage 1	stage 2	stage 3	stage 4
1	10	20	5	30
2	15	8	12	-
3	20	7	-	5
4	-	7	17	10

Table 2. Computation results for example

performance	number of product
	7		15		30
	Moon	STM	Moon	STM	Moon	STM
CPU (sec)	381	25	-	129	-	130
makespan	604.5	435*	-	866*	-	1788**

*weighting factor 6, **weighting factor 10

SBM 알고리즘을 적용해서 풀어낸 결과는 표2에 나타나 있다. 수학적인 알고리즘을 이용해서 풀었을 경우(Moon and Park, 1996), 제품의 수가 7이 넘어가면 풀어내지 못한 반면, 본 알고리즘을 이용했을 경우는 이의 2배수의 문제도 어렵지 않게 풀어내는 것을 볼 수 있다. 다만, node의 depth를 고려했기 때문에 MILP에 의한 최적해와는 다소 차이를 볼 수 있다. 실제 공정 문제 규모에 적용할 경우 비록 최적해를 보장하지는 못하지만 적용가능한 해를 짧은 시간 내에 얻을 수 있는 것을 볼 수 있다.

결론

기존의 수학적인 모델식으로 구성되어왔던 복잡한 회분식 공정의 단기일정계획 문제에 적용하고자 순서 가지 방법을 제안하였다. node생성 방법으로 각 product의 process 순서를 결정하였고 보다 빠른 시간에 해를 얻어내고자 목적함수에는 진행된 depth를 고려하였다. 수학식으로 풀지 못했던 큰 규모의 문제에 대해 빠른 시간 내에 해를 발견할 수 있다는 장점을 보였다. 최적해에 접근할 수 있는 heuristic에 대한 연구가 계속 중이다.

감사의 글

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

참고문헌

J. Bok, S. Park, □연속 시간 표현법을 이용한 배관 없는 공장에 대한 스케줄링□, KIChE Meeting, Fall, 1997

S. Moon, S. Park , □Scheduling Models in the Semiconductor Industries", '96 KACC, Pohang, Korea, October 24 ∼ 26, 1996

J. Pearl, "Heuristics: Intelligent Search Strategies for Computer Problem Solving, Reading, MA: Addison-Wesley, 1984

J. M. Pinto, "Mixed integer and logical based optimization techniques for scheduling of multistage chemical processes"; PhD Thesis in Carnegie Mellon Uni., 1995.