스케쥴링 문제의 분류

스케쥴링 문제의 분류

스케쥴링 문제는 매우 다양하기 때문에, 분류조차 쉽지 않은 것이 사실입니다. 그러나, 당면한 문제를 풀기 위해서는 최소한 우리가 접한 '문제의 유형'을 파악할 수 있어야, 기존의 연구결과를 활용하거나 개량하는 등의 접근을 할 수 있습니다.

서두에서 소개한 것처럼, 스케쥴링 문제는 매우 다양합니다. 앞서 간단히 소개한 바와 같이 스케쥴링 문제를 구성하는 핵심은 '자원', '작업', '목적'으로 구분지어 볼 수 있습니다. 이 3가지 핵심 요소들 내부에서도 복잡한 관계가 있을 수 있으며, 핵심 요소들간에도 복잡한 관계가 존재하기 때문에, 스케쥴링 문제는 분류조차 쉽지 않은 것이 사실입니다. 

대개 스케쥴링 교재에서는
• '단일기계 스케쥴링 문제(Single Machine Scheduling Problem)'
• '병렬기계 스케쥴링 문제(Parallel Machine Scheduling Problem)'
• '흐름시스템 스케쥴링 문제(Flow Shop Scheduling Problem)'
• '잡샵 스케쥴링 문제(Job-shop Scheduling Problem)'
• '프로젝트 스케쥴링 문제(Project Scheduling Problem)'
등으로 스케쥴링 문제를 나누어 다루고 있습니다. 이러한 구분은 설비의 구성 및 배치, 작업의 흐름에 따른 것이라 할 수 있습니다. 최근 (학계에서는) 이런 일반적인 구분보다 자세한 분류를 선호하는 경향이 있습니다. 간단히 어떻게 분류를 하고 있는지 설명드리도록 하겠습니다. 

스케쥴링 문제의 핵심은 '자원','작업','목적' 이라고 말씀드렸지요? '자원', '작업', '목적'을 기준으로 스케쥴링 문제를 구분지어 보도록 하겠습니다. (본 내용은 Scheduling Theory (by Brucker, 1995)에서 발췌했습니다.) 사실 많은 분류 방법이 있지만, 비슷한 부분도 많고, 또 스케쥴링에 생소한 분들이 접하시기에는 Brucker 교수의 분류가 좋지 않을까 싶어 소개합니다. 

 작업 

1. Preemption 허용 여부 : 어떤 작업(A)을 기계에서 진행 중인데, 그 작업 외에 긴급한 작업(B)이 있을 경우, A 작업이 종료되기 전에 작업을 중지하고, 다른 작업(예를 들어 B)을 수행하는 것을 허용하는지의 여부. Setup Cost가 상당히 큰 경우와 기술적인 문제가 있는 경우에는 Preemption이 허용되지 않겠지요?
2. Precedence Relation : MRP를 설명드리면서 Routing이라는 것을 설명드린 일이 있지요? 이런 라우팅은 공정의 진행 순서를 나타내는 데, 이런 순서가 선행관계를 나타냅니다. 예를 들어 면삭을 한 후에, 드릴링을 한다라고 하면, 면삭공정은 드릴링 공정의 선행공정이 됩니다. 스케쥴링을 할때에는 반드시 면삭공정이 끝난 후에 드릴링 공정에 들어갈 수 있는 것이지요. 선행관계가 없다는 것은 아무런 순서로 작업을 해도 상관이 없거나, 한 공정만으로 작업이 종료될 수 있는 경우를 뜻하겠지요? 이런 선행관계는 제조 뿐만 아니라 조립에도 적용됩니다.
3. Release Date : 작업은 아무때나 시작할 수 있는 것이 아니지요. 최소한 원자재의 구입이 마쳐지고, NC 프로그램을 비롯한 작업 준비가 끝나게 되야 작업이 시작될 수 있는 것이지요. 바로 작업을 시작할 수 있는 가장 빠른 시점이 Release Date입니다. 그리고, 참고로 Release Date를 조정함으로써 생산시스템의 운용효율을 조정할 수도 있답니다.
4. Processing Time : 작업의 수행시간(공정수행시간)을 Processing Time이라고 합니다. 대개는 고정된 상수값(determinstic value)으로 가정하는데, 이 값이 그 중요한 표준시간입니다. 그러나, 공정에 따라서는 Processing Time이 확률적인 값을 가질 수도 있습니다. 이 때에는 확률분포함수와 그 모수로 표현되지요.
5. deadline : 작업을 언제까지 마쳐야 할까요? 바로 납기라는 것이지요. 수주생산을 할 때에는 고객과의 협의를 통해 납기가 결정되지만, 계획생산을 하는 경우에도 내부적으로 납기를 설정하는 경우가 흔합니다. 완성품의 납기뿐만 아니라 반조립품이나 조립품에 대해서도 이런 납기를 설정할 수도 있지요. 전체공정시간이 긴 제품(비행기, 선박, 금형)을 생산할 때에나 프로젝트 스케쥴링에서는 Milestone이라 불리는 deadline을 중요 부품 또는 공정에 부여합니다.
6. Setup : 작업물이 바뀌게 되면, 기계를 다시 셋업해주어야 하는 경우가 있습니다. 또 이런 셋업시간은 공정순서에 독립적인 경우도 있으며, 공정순서와 종속적인 경우도 있습니다. 셋업시간과 관련된 문제가 들어가면, 아무리 쉽게 보이는 문제라 할지라도 아주 풀기 어려운 문제가 됩니다.
7. Batching : 한 기계에서 한 번에 한 작업물을 대상으로 작업이 수행되는 것이 보편적이지만, 기계에 따라서는 여러 작업물을 한 번에 가공하는 것이 가능합니다. 이런 기계를 Batching Machine이라고 하고요, 한 번에 작업할 작업물을 모으는 것을 Batching이라고 하지요. Batching이 아주 중요한 이슈로 다루어지는 곳이 반도체 생산 시스템입니다. 오븐에서 여러 chip을 한 번에 구을 수 있기 때문이지요. Matal Cutting Industry에도 이런 Batching을 볼 수 있는데요, 높이가 같은 작업물을 모아서 한 번에 면삭을 하기도 하거든요.

 자원 
사실 자원의 속성은 상당히 다양합니다. 특히, 프로젝트 스케쥴링 문제(RCPSP : Resource Constrainted Project Scheduling Problme)를 접하게 되면, 대단히 복잡하고 다양한 유형의 자원을 보실 수 있는데, 아래에서는 일반적인 기계 자원이나 인력 자원의 배치나 구성 정도로 생각하시면 되겠네요. 자원에도 Renewable Resource(기계자원, 노동력), Non-renewable Resource(돈)과 같은 것들이 있고요. 그 중간 정도의 속성을 가진 자원들도 있거든요. 사실 아래의 구분은 조합이 매우 중요한데, 그 설명은 생략하기로 하지요.
1. o : 단일 기계(Single Machine)를 나타냅니다.
2. P : 병렬 기계(Identical Parallel Machine)를 나타냅니다. 병렬 기계라 함은 여러 대의 동급기계가 있기 때문에, 이런 기계중에서 하나를 선택해서 작업을 하면 되는 구성을 뜻합니다. 본 분류에서는 기계들의 능력이 동일하다고 봅니다. 즉, A라는 기계에서 가공을 하나, B라는 기계에서 가공을 하나 소요시간은 같다고 봅니다.
3. Q : 병렬 기계 시스템(Uniform Parallel Machine)이기는 하나, 기계에 따라 능력이 다르다고 봅니다. A라는 기계는 B라는 기계에 비해 2배의 능력이 있다고 하면, B에서 10시간 걸린 작업은 A에서 5시간 걸린다는 것이지요.
4. R : 병렬 기계 시스템(Unrelated Parallel Machine)이며, 기계에 따라 능력이 다를 뿐만 아니라 이런 능력의 차이는 작업물과도 관련이 있다는 것이지요. 일률적으로 어떤 기계가 다른 기계보다 항상 뛰어난 성능을 보이는 것은 아니라는 것이지요.
5. G : 일반적인 잡샵을 나타냅니다.
6. F : 흐름 생산 시스템(Flow shop)을 나타냅니다.
7. O : Flow shop인데, 공정간에 선행관계가 없는 경우를 나타냅니다. 저자는 Open Shop이라고 부르고 있습니다.
8. X : 저자는 Job-shop과 Open Shop이 혼재한 형태를 X라고 부르고 있습니다.

 목적 
학계의 연구에서는 대개 목적 함수를 단순하게 두지만, 현실은 그렇지 않은 경우가 많습니다. 여러 목적을 동시에 최적화하려고 하는 것이 현실이지요. 뿐만 아니라, 최적해 또는 근사 최적해를 구하는 것만이 목적이 아니라 가능해(feasible solution)를 구하는 것을 목적으로 하는 스케쥴링 문제가 사실 많습니다. 우선 학계에서 주로 다루는 목적함수들을 간단히 살펴보기로 하지요.
• C : 작업의 종료시점을 Completion Time이라고 합니다. Completion Time을 줄이는 것을 목적으로 삼기도 하지요. 특히, 가장 늦은 Completion Time을 Makespan이라고 합니다. 모든 작업의 Completion Time을 더하여 평균치를 낸 것을 Mean Flow Time이라고 합니다. 그리고, 작업에 따라 가중치를 부여하여 가중 평균을 내는 방법을 이용하기도 합니다.
• L : 작업의 종료시점에서 납기일(Due Date)을 빼준 것을 Lateness라고 합니다. 납기보다 늦게 끝나면 양의 값을 갖고, 일찍 끝나면 음의 값을 갖지요.
• E : 납기일에서 작업의 종료시점을 빼서, 양의 값이 나오면 취하고, 음의 값이 나오면 버리는 것을 Earliness라고 합니다.
• T : 작업의 종료시점에서 납기일을 빼서, 양의 값이 나오면 취하고, 음의 값이 나오면 버리는 것을 Tardiness라고 합니다. Tardiness의 합을 최소화하거나, Tardiness의 최대값을 최소화하는 방법을 사용하기도 하지요.
• U : 작업이 납기보다 늦어졌는지 아닌지 만을 구분합니다. 모든 작업에 대해서 구분해보면, 납기보다 지연된 작업수를 구할 수 있겠지요. 이렇게 납기가 지연된 작업의 수를 최소화하는 것을 목적으로 삼기도 합니다.
• D : 작업의 종료시점과 납기일의 차이에 대해 절대값(absolute value)을 취해준 것을 Absolue Deviation이라고 합니다.


이런 분류외에도 생성된 스케쥴의 특성에 따른 분류도 가능하며, 스케쥴링 시스템에 대한 요구사항도 추가로 분류에 포함될 수 있습니다. 이상의 분류만 보시더라도, 얼마나 방대한 영역을 다루고 있으며, 얼마나 분류가 복잡하고 힘들지 상상하실 수 있을 것입니다. 

오늘은 상당히 딱딱한 내용이었는지 모르겠지만, 여러분이 스케쥴링 문제를 접했을때 이런 분류를 하실 수 있다면, 기존의 연구를 활용하여 스케쥴링 시스템을 구성하는데 많은 도움을 받으실 수 있으실 것입니다. 

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