우선순위규칙(Dispatching Rules) (1)

우선순위규칙(Dispatching Rules) (1)

스케쥴링 문제의 해법으로 가장 쉽게 사용할 수 있는 방법이 우선순위규칙(Dispatching Rule) 입니다. 우선순위규칙의 종류는 상당히 많습니다. 따라서, 우선순위규칙을 활용한다 하더라도 충분한 검토를 통한 선택이 요구됩니다. 본 절에서는 우선순위규칙의 기초에 대한 이해를 돕도록 하겠으며, 잘 알려진 몇 가지의 우선순위규칙을 소개하겠습니다. 그리고, 마지막으로 우선순위규칙을 몇 가지로 분류해보고, 우선순위규칙의 장단점에 대해 이야기해 보도록 하겠습니다.

우선순위규칙(Dispatching Rule)은 스케쥴링 문제의 해법으로 가장 널리 그리고 쉽게 이용되고 있는 방법중의 하나입니다. 계산량이 적기 때문에 소요 시간도 적고, 구현하기도 쉬울 뿐만 아니라 직관적으로 이해하기 쉽다는 장점이 있습니다. 우선순위규칙은 컴퓨터를 이용한 스케쥴링이 이루어지기 전부터 사람들에 의해 사용되던 방법입니다. 

 우선순위규칙이란? 


우선순위규칙이란 말 그대로 여러 개의 작업이 있을 때 어떤 작업을 먼저 할지를 결정하는 규칙입니다. 아래의 그림을 보면서 설명드리도록 하지요. 

 
작업자의 고민(?)
드릴링 공정을 맡고 있는 작업자가 있었습니다. 어떤 공정을 끝내고 나서 보니, 대기중인 작업물이 3개가 있군요. 어떤 것부터 먼저 해야 할까요? 만일, 대기중인 작업이 하나였다면 작업자는 고민없이 작업을 시작했을 것입니다. 대기중인 작업물 중에서 어떤 작업을 먼저 할 것인지를 선택하는 규칙이 바로 우선순위 규칙입니다. 본 절의 후반부에서 설명드리겠지만, 먼저 도착한 작업부터 먼저 가공을 해주는 FIFO(First In First Out) 규칙을 쓸 수도 있겠고, 그 반대로 LIFO(Last In First Out)라는 규칙을 쓸 수도 있겠습니다. 또, 가공이 짧게 끝날 것으로 예상되는 작업부터 처리해주는 SPT(Shortest Processing Time) 규칙을 쓸 수도 있겠고, 납기도 빠른 작업부터 처리해주는 EDD(Earliest Due Date) 규칙을 적용할 수도 있겠습니다. 우선 순위 규칙은 기계가 idle해지는 순간에 적용되는 규칙입니다. 만일 기계가 idle해졌는데, 대기중인 작업물이 없다면 어떻게 하시겠습니까? 작업물이 도착할 때까지 기다리면 되겠지요. ^_^

 우선순위규칙의 한계 


몇 가지 가정이 필요하기는 하지만, 단일기계 문제에서 우선순위규칙은 놀라우리만큼 좋은 성능을 보입니다. SPT를 사용하면, Makespan이나 Mean Flow Time을 최소화할 수 있습니다. 뿐만 아니라, Tardiness의 합도 최소화할 수 있지요. 그리고, EDD를 사용하면 Tardy Job의 수를 최소화할 수 있습니다. 언제가 설명드릴 기회가 있겠지만, 이 외에도 Longest Tail Heuristic과 같은 좋은 방법들이 많이 알려져 있답니다. 그런데, 우선순위규칙에는 어떤 문제점이 있을까요? 

작업장에는 대개 여러 대의 기계가 있고, 작업물은 이들 기계를 오가며 가공이 이루어지지요. (MRP 부분에서 routing을 설명드린 일이 있지요?) 다음의 그림을 함께 보시도록 하지요. 
근시안적인(Myopic) 우선순위규칙
왼쪽의 작업장(기계)에서 가공이 이루어진 작업은 다음 작업장(기계)으로 이동이 이루어지게 됩니다. 왼쪽의 작업장에서 막 가공이 이루어진 부품 A는 납기가 임박한 중요한 부품인데, 오른쪽의 작업장에서는 이런 부품이 있는지도 모른 상태에서 부품 D와 부품 E를 놓고 우선순위규칙을 적용하여 작업을 선택하게 되지요. 조금 더 멀리 내다보지 못하고, 당장의 작업부터 처리하는 근시안적인 의사결정이라고 할 수 있겠지요. 제조현장에 작업물이 많지 않은 경우(즉, 기계나 작업장내에 대기중인 작업이 적은 경우)에는 우선순위규칙도 좋은 성능을 발휘하지만, 대기중인 작업이 많은 경우와 특히 가공순서에 영향을 받는 셋업타임이 있는 경우(family setup을 비롯한 sequence dependent setup time)에는 우선순위규칙은 (매우) 좋지 않은 성능을 보입니다. 



 멀리볼 수는 없을까? 


우선순위규칙이 근시안적이라는 것은 앞에서 설명드렸지요. 그러면, 멀리 보는 방법은 없을까요? 스케쥴링에서 멀리 본다는 것은 현재 대기중인 부품 뿐만 아니라, 앞으로 도착할 작업들까지를 고려해서, 의사결정을 취하되 그 의사결정이 미치게 될 영향까지를 분석해 본다는 의미가 되겠습니다. 그러나, 멀리보기 위해서는 많은 계산이 필요하기 때문에, 스케쥴링의 수행시간이 길어지는 단점이 발생하고, 얼마나 멀리 보는 것이 필요한지에 대해서도 생각해 보아야 합니다. 스케쥴링 문제가 어렵고 복잡해진 가장 큰 원인은 Disjunctive Constraint 때문인데, 멀리 보기 위해서는 Disjunctive Constraint 별로 여러 가지 조합을 다 고려해야 하기 때문에 어려워지는 것이지요. 어떤 스케쥴링 방법이 얼마나 멀리 바라보고 있는가를 구분짓는 기준은 사실 없습니다. 굳이 나눈다면, Partial Look-ahead 부류와 Global Look-ahead 부류로 나누어 볼 수 있겠지요. 발견적 기법들은 대개 전자에 속한다고 할 수 있고요, 최적화 방법들은 후자에 속한다고 할 수 있습니다. Look-ahead의 정도에 대해 잘 분류를 해 놓고 있는 것이, CSP(Constraint Satisfaction Problem) 분야의 Consistency인데요. CSP에 관해 설명드릴 기회가 있을때, Look-ahead에 대해서도 보충설명을 드리도록 하지요. 

Look-ahead feature를 갖는 스케쥴링 방법을 만들고자 한다면, 스케쥴링 방법의 개발 이전에 선수요건이 있습니다. 당장, 눈앞에 놓여있는 작업물 외에 앞으로 도착될 작업물을 예상할 수 있어야 하고요, 작업장을 떠나게 되는 작업물이 앞으로 어떤 공정을 더 거쳐서 완성될 것인지를 파악할 수 있어야겠지요. 결국, 생산 현장의 상황 또는 데이터를 실시간으로 수집하여 가공해주는 시스템이 필요하겠지요. 데이터를 정확하게 수집하는 일은 이런 이유로 매우 중요합니다. 바코드, 카드리더 또는 단말기 등을 이용하여 데이터를 실시간으로 수집하고 정리해줄 수 있는 시스템이 존재할 때에만 Look-ahead feature를 갖는 스케쥴링 시스템을 제대로 구축할 수 있습니다. 현장에서 어떤 일이 벌어졌는지 또는 벌어지고 있는 지에 대한 정보를 얻을 수 없다면(제 아무리 Look-ahead feature를 갖추었다 하더라도), 현실과는 동떨어진 스케쥴을 만들게 될 것이고, 현장에서 따를 수 없게 될 것입니다.


 우선순위규칙의 종류 


앞서 언급한 바와 같이 우선순위규칙은 매우 다양합니다. 동일한 상황이라 하더라도, 적용되는 우선순위규칙에 따라 생성된 스케쥴은 매우 상이할 수 있습니다. 따라서, 공장이나 작업장에 적합한 우선순위규칙을 찾는 것은 매우 중요한 일이라고 할 수 있습니다. 일단 좋은 우선순위규칙을 찾기에 앞서, 어떤 우선순위규칙이 있는 지를 알아야겠지요. 어떤 우선순위규칙이 있고, 각각의 장,단점은 어떤지, 또 어떻게 분류할 수 있는지에 대해서는 내일 알아보도록 하지요. (너무 길어졌네요... ^_^)


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