스케쥴링의 γ(감마)필드

이번 글은 스케줄링 문제에서의 기본 notation의 마지막 항목인 γ(감마)필드에 대한 글입니다. 그럼 γ(감마)필드에는 어떤 뜻이고 어떤 항목들이 있는지를 살펴보겠습니다. 

γ(감마)필드의 의미는 schedule문제에서 풀어야 하는 목적함수를 나타냅니다. Schedule 문제에서의 목적은 대부분 목적함수 부분인 γ를 최소화하려 합니다. Schedule 문제에서는 약간씩 컨셉은 다르지만 정해진 job을 최소한의 시간안에 끝내는 것이 목적이기 때문입니다. 문제에서는 보통 단순하게 하나의 목적함수를 최소로 하는 것을 목적으로 하지만, 현실 문제는 여러가지 목적을 동시에 최적화 하려는 경우가 현실입니다. 지금부터 γ(감마)필드에 들어가는 특성과 제약조건들에 대해 알아보겠습니다. 

 

 

γ필드에 들어갈 수 있는 항목

---

Makespan(Cmax): 작업의 종료 시점을 completion time이라고 하고, 총 공정에서 가장 마지막으로 끝난 작업의 completion time을 makespan이라고 합니다. makespan을 목적함수로 갖는 scheduling문제는 makespan을 최소로 하는것을 목적으로 두는 문제입니다.

 

※ Lateness와 Tardiness의 차이에 대해 먼저 집고 넘어가겠습니다. 둘다 사전적인 의미는 늦음,지각을 뜻합니다. Scheduling문제에서 두 단어의 차이는 마감일(due date)을 기준으로 양/음을 구분짓는가의 여부입니다. 예를 들어서 Lateness를 기준으로 마감일이 15일인 경우 20일에 작업이 완료되었으면 +5, 10일에 작업이 완료되었다면 -5로 계산합니다. 그렇기 때문에 Lateness는 두 작업이 각각 5일 늦게, 5일 일찍 끝났다면 총 Lateness값은 0이 됩니다. 하지만 Tardiness는 일찍 마무리 한 작업에 대해서 전부 0으로 처리합니다. 같은 예로 마감일이 15일인 두 작업에 대해 한 작업은 10일에, 다른 작업은 20일에 마무리 하게 되면 첫 번쨰 작업의 Tardiness는 0, 두 번째 작업의 Tardiness는 5이기 때문에 총 Tardiness는 5가 됩니다. ※

 

Maximum Lateness(Lmax): 마감일(due date)가 정해진 경우 마감일보다 늦어지는 날짜를 최소로 만드는 것이 목적입니다. Lateness는 일찍 마무리한 작업에 있어서 Lateness값에 음수 값을 부여하므로 일찍 마무리한 작업이 있다면 총 Lateness를 줄일 수 있습니다. 

 

Total weighted compelete time(ΣwjCj): 작업들마다 각자의 중요도(weight)가 있습니다. 예를 들어서 1학점짜리 공통교양 과제와, 3학점짜리 전공 수업의 과제는 아마 모든 학생들이 3학점짜리 전공 수업의 과제를 더욱 중요하게 생각할 것입니다.(물론 모든 과제는 중요합니다^^) 그래서 이 목적함수는 각 작업에 타당한 가중치를 주어 'ΣwjCj'로 계산합니다. 물론 ΣwjCj값을 최소로 하는 것에 목적을 가지고 있습니다. 

 

Total weighted tardiness(ΣwjTj): 마찬가지로 작업들에 중요도(weight)를 주어 'ΣwjTj'를 최소로 하는 것에 목적을 두고 있습니다. 

 

Weighted number of tardy jobs(ΣwjUj): 작업들에 중요도(weight)를 주어 'ΣwjUj'를 최소로 하는 것에 목적으로 두고 있습니다. 

 

 

γ(감마)필드를 마지막으로 Schedule Problem의 문제 Notation을 마무리하였습니다. 앞서 얘기했던 것처럼 γ(감마)필드에도 제가 글에서 소개한 것들보다 더 다양하고 복잡한 목적함수를 갖는 문제들도 존재합니다. 모든 현실의 공정은 각자의 제약과 목적이 있기 때문에 몇가지 카테고리로 제한 할 수는 없기 때문이겠죠. 그럼 이 글을 마지막으로 Notation을 마무리 하도록 하겟습니다.