| 초록 |
다품종 소량생산이 중요성이 부각되면서 활기를 띄게 된 회분식 공정의 스케쥴링에 대한 연구는 70년대 이후 활발하게 진행되어오고 있다. 최근의 연구방향은 실제 공정에 적용을 위한 보다 엄격하고(rigorous) 효과적인 알고리즘 개발에 초점을 맞추어, 다루는 대상문제 정의도 다양화·복잡화 되어오고 있다. 모든 생산품이 동일한 생산 순서를 갖기 때문에 생산품의 조업 순서만을 결정하는 다목적(multiproduct) 회분식 공정의 스케쥴링은효과적인 수학적인 모델링을 이용한 방법이 지배적인 반면, 각 생산품이 각기 다른 조업과정을 거치게 되는 다목적(multipurpose) 회분식 공정에 대한 적용은 미비한 편이다. 이는다목적 공정에 대한 스케쥴링 문제를 수학식으로 모델링 할 경우 혼합정수계획법(mixed integer linear programming)으로 표현되고, 시간 domain을 나타내려면 다량의 이진변수가 불가피하기 때문이다. 이는 곧 알고리즘의 효율성을 따지는데 직결하는 계산시간(CPU time)과 직결된다. 이러한 난점을 해결하고자 제안되는 모델링 방식으로 연속시간표현법(continuous time representation)이 활발하게 연구되어오고 있다(Pinto, 1995; Bokand Park, 1997). 기존의 이산시간 표현법(discrete time representation)이 시간관점에서 각시간 interval에서 사건(event)의 발생여부를 결정하는 이진변수를 요구하는 반면, 연속시간표현은 사건관점에서 발생한 시작시간과 종결시간을 결정하기 때문에 훨씬 효과적인 모델링을 할 수 있다는 게 장점이다. 특히 multi stage process와 jobshop scheduling 같은 문제를 이산시간 표현법으로 나타내고자 할 경우 모델링을 풀 수 있는 효과적인 MILPsolver가 부재(不在)한 상태이다. Pinto (1995)가 제안한 연속시간 표현법은 효과적으로multi stage process에 적용되었지만 다목적 공정의 성격을 여전히 유지하고 있다. Bokand 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에 대한 정보를 나타냄으로써 이를 먼저 일어난 공정과 구별할 수 있기 때문이다. 순서 가지 방법이란 발생 가능한조업경로를 nod와 branch로 구성해서 가장 짧은 makespan을 갖는 경로를 찾는 알고리즘이다. 한 node는 순서쌍 (product, stage)로 표현되고, 이를 기본으로 해서 발생 가능한 사건을 다음 node로 표현한다. 이 경우 생성된 node들은 선행 node에 비해 depth의 크기가 1만큼 더 커지게 된다. node가 생성됨과 동시에 그 node에 해당하는 완성시간(completiontime)이 계산된다. 이들 각각에 대해 완성시간을 비교해서 가장 짧은 완성시간을 갖는node에서 다음 세대 node를 생성시키고 나머지는 휴지(休止)상태로 놔둔다. 만약 생성된새로운 node의 완성시간의 크기가 휴지상태 node보다 클 경우, 현재의 node는 휴지상태가되고 완성시간의 크기가 작은 node에 대해 다음 세대의 node를 생성시킨다. 한 stage에 참여할 수 있는 unit의 수는 여러 개이므로 이 중 해당 product를 수행했을 때 완료시간을 가장 줄일 수 있는 unit를 선택하게 되야한다. 이러한 작업은 모든 product의 생산경로가 종료될 때까지 계속된다. 실제로 이러한 방법만을 고려한 것은 발생 가능한 경우의 모든 node를 생성시키는 결과를 낳기 때문에 전체 스케쥴링 결과를 얻어내는데는 상당한 시간이 필요하게 된다. 이것은 Petri nets 알고리즘을 스케쥴링에 구현한 것의 하나인 A* 알고리즘(Pearl, 1984)과 유사한 결과를 만들어내게 된다. 여기서 계산할 node 수를 줄이고자 사용된heuristic이 있다. 목적함수, 즉 완료시간에 Weight x depth를 더해주는 것이다. 계산시간을줄이고자 depth가 큰 것에 그 만큼의 가중치를 주자는 알고리즘이다.
|
