우선순위규칙(Dispatching Rules)의 한계 (4)

우선순위규칙(Dispatching Rules)의 한계 (4)

우선순위규칙은 앞서 살펴본 바와 같이 직관적으로 이해하기 쉬울 뿐만 아니라, 구현하기도 쉽습니다. 엄밀히 따지고 보면, 전산화된 환경을 필요로 하는 것도 아니지요. 그러나, 우선순위규칙을 적용하기 곤란한 환경도 있을 뿐만 아니라, 우선순위규칙의 성능(performance)이 너무 떨어지기 때문에 보다 나은 방법을 찾는 것이 바람직한 환경도 있습니다. 도대체(?), 우선순위규칙은 최적화 방법 또는 근사 최적해를 구하는 방법에 비하여 얼마나 성능이 떨어지는 것일까요? 본 절에서는 학계에 잘 알려져 있는 데이터를 일부를 발췌하여 우선순위규칙의 한계에 대해 알아보도록 하겠습니다.

 구현하기는 쉽지만

우선순위규칙은 앞서 살펴본 바와 같이 많은 계산을 요구하지 않습니다. 사실, 우선순위규칙을 이용하여 스케쥴링을 하고자 한다면, 굳이 전산화를 해야 할 필요도 없습니다. 계산에 필요한 정보는 작업지시서와 라우팅 정보를 참조하면 모두 얻을 수 있기 때문이지요. 또, 우선순위규칙 기반의 스케쥴링 시스템을 만들고자 한다면 '제조현장의 데이터 수집(Shop-Floor Data Collection)'만 잘하면 되겠지요. 

그러나, 이런 우선순위규칙은 치명적인 단점을 몇 가지 가지고 있습니다. 첫번째 단점은 제조 시스템 특유의 제약조건이 있는 경우에 이를 반영하지 못한다는 것입니다. 일반적인 제조 시스템에서 흔히 대두되는 문제는 아니지만, 최악의 경우에는 feasible solution을 얻을 수 없다는 것입니다. 두번째 단점은 최적해나 근사 최적해와 비하여 우선순위규칙에 의해 얻은 해의 성능이 많이 떨어질 수 있다는 것입니다. 물론, 시스템 구성이 어떻게 되어 있는가 또는 시스템 구성을 어떻게 하는가에 따라서 우선순위규칙도 좋은 해를 산출할 수 있지만 일반적으로 우선순위규칙을 이용하여 얻은 해는 발견적 기법을 비롯한 근사 최적화 방법이나 최적화 방법에 의해 얻은 해에 비하여 많이 쳐지는 것이 사실입니다.

 우선순위규칙의 성능은 얼마나 쳐지는가?

사실 스케쥴링의 대상이 되는 시스템에 따라 스케쥴링의 목적도 다를 수 있기 때문에 획일적으로 어떤 방법이 어떤 방법보다 낫다거나 혹은 못하다거나 하는 결론을 짓는 것은 무리일 수 있습니다. 그러나, (별도의 검토나 다른 좋은 방법을 찾아보려는 노력 없이) 우선순위규칙을 사용하고 있거나, 신규 시스템을 대상으로 우선순위규칙을 사용하고자 하는 기업체의 경우에는 현 상태를 살펴보고, 그리고 또 평가해보고자 하는 노력을 기울여야 할 것입니다. 

본 절에서는 i2 Technology사 소속의 Irfan M. Ovacik 박사와 Purdue Univ. 산업공학과 Reha Uzsoy 교수가 공저한 "Decomposition Methods for Complex Factory Scheduling Problems"이라는 책 중에서 실험 결과의 일부분을 발췌하여 소개하도록 하겠습니다. 

1. 저자들은 (학계에 잘 알려져있는) Applegate & Cook (1991)의 Benchmark Problem을 대상으로 실험을 해 보았다고 합니다. 이 문제들은 Job Shop Scheduling Problem과 Flow Shop Scheduling Problem으로 구성되어 있습니다. 이들은 Adams(1988)가 제안한 SBP(Shifting Bottleneck Procedure)라는 알고리즘의 몇 가지 변형과 잘 알려진 10여 가지 이상의 우선순위규칙을 비교했다고 합니다. 자세한 비교결과는 양이 많아서 본 페이지에 올리기는 곤란하고요, summary된 결과를 보여드리도록 하지요. 


위의 결과는 makespan을 대상으로 분석된 것입니다. 맨 오른쪽의 BEST DSPT라는 것은 12 종류의 우선순위규칙을 적용한 결과 중에서 가장 좋은 결과를 기준으로 비교한 것입니다. 표를 보시면, 잘 디자인된 발견적 기법(heuristics)은 우선순위규칙보다 좋은 결과를 보여주고 있음을 알 수 있습니다. 그러나, 본 분석에 사용된 문제의 크기는 Job의 수가 10-30개, 기계의 수가 5-20개로 현실적인 문제에서 볼 수 있는 크기라 하기에는 작습니다. 

2. 저자들은 앞의 문제보다 큰 Taillard(1993) Benchmark Problem을 대상으로 실험을 했답니다. 역시, 문제의 유형은 Job Shop Scheduling 였고요, 문제의 크기는 작업(N)의 수가 10-100개, 기계(M)의 수가 15-20여개였습니다. 비교의 기준으로는 Makespan을 사용했습니다. 실험 결과를 정리하여 간략히 표로 나타내면 다음과 같습니다. 

위의 결과는 makespan을 대상으로 분석된 것입니다. 위의 실험에 사용된 문제는 학계에서 다루어지는 문제들에 비해 상당히 큰 편입니다. 사실 Job의 수가 10여개를 넘고, 기계의 수가 10여개를 넘는 문제들에 대해서는 최적해를 구하기 매우 힘들기 때문에, 비교의 대상으로는 Taillard가 제시했던 Tabu search의 적용결과를 이용했답니다. 잘 살펴보시면, 문제의 크기가 커짐에 따라서 잘 디자인된 발견적 기법이 우선순위규칙보다 더 좋은 결과를 보여주고 있습니다. 바꾸어 말하면, 우선순위규칙은 점점 좋지 않은 결과를 보여주고 있는 셈이지요. 

3. (실제 제조업체에서 스케쥴링의 목적으로 makespan을 사용할까요? 단일 project를 수행하는 경우라면 그럴 수 있겠지만, 대부분의 제조업체에서 가장 중요한 기준은 납기의 준수입니다. Make-to-Order, Assemble-to-Order, Engineer-to-Order 환경의 제조업체는 물론이고, Make-to-Stock이라 할지라도 내부적으로 설정된 납기일이 있기 때문에 이 납기를 지키는 것은 매우 중요하지요.) 저자들은 여러가지 measure를 이용하여 발견적 기법과 우선 순위 규칙을 비교해 보았습니다. 실험에 사용된 문제는 Job의 수가 최대 50여개에 이르고, 기계의 수가 최대 20여개에 이르는 정도의 크기였습니다. 이런 문제에 대해 최적해를 구하는 것은 정말 힘들기 때문에 실험에 사용된 방법들간의 차이를 비교하는 방법을 취했습니다. 비교에 사용된 meaure는 다음과 같이 정의하였다고 합니다.


이런 measure를 가지고 실험결과를 분석한 결과는 다음의 표와 같습니다. 


자, 이 문제를 보시면 재미있는 결과를 보실 수 있습니다. Makespan(Cmax), Maximum Lateness(Lmax), Flow Time, Tardiness의 합, Tardy Job의 수와 같은 모든 척도에서 잘 디자인 된 발견적 기법이 우선순위규칙에 비해 좋은 결과를 보여주고 있지요. 또 하나 특이한 점은 Flow Shop 문제에서는 Dispatching Rule도 상대적으로 나쁘지 않은 결과를 보여주고 있는 것이지요. 이렇게, 어떤 발견적 기법이라도 모든 상황에서 좋은 결과를 보여주지 못하는 것처럼, 우선순위규칙을 적용하는 경우에 좋은 결과를 보여주는 상황과 나쁜 결과를 보여주는 상황을 나누어볼 수 있답니다. 다음 절에서는 이런 이야기를 하도록 하지요. 

본 페이지는 1998년 5월 1일에 작성되었습니다.