알고리즘 - 작업 스케줄링 알고리즘(JobScheduling)

작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제

대학 수업에서 강의실을 배정하는 문제와 같다.

강의실 = "기계"

강의 = "작업"

 

주어진 요소

- 작업의 수

- 각 작업의 시작시간과 종료시간

- 작업의 길이

 

알고리즘

다음과 같은 그리디 알고리즘이 존재한다.

- 빠른 시작시간 작업 우선(Earliest start time first)배정

- 빠른 종료시간 작업 우선(Earliest finish time first)배정

- 짧은 작업 우선(Shortest job first)배정

- 긴 작업 우선(Longest job first)배정

 

위 4가지중 첫 번째 알고리즘을 제외하고 나머지 3가지는 항상 최적해를 찾지 못한다.

 

빠른 시작시간 작업 우선(Earliest start time first)배정 알고리즘

예제)

t = [s, f]

s는 시작시간, f는 종료시간

t1 = [7, 8]

t2 = [3, 7]

t3 = [1, 5]

t4 = [5, 9]

t5 = [0, 2]

t6 = [6, 8]

t7 = [1, 6]

 

시작시간을 오름차순으로 정렬한다.

L = {[0, 2], [1, 6], [1, 5], [3, 7], [5, 9], [6, 8], [7, 8]}

 

시작시간에 따라 정렬된 순서대로 배정을 하는데, 먼저 생성된 기계 순서대로 t가 배치될 수 있는지 확인하고, 배치될 수 있는 기계가 없을 때 기계를 생성한다.

L = {[1, 6], [1, 5], [3, 7], [5, 9], [6, 8], [7, 8]}

 

L = {[1, 5], [3, 7], [5, 9], [6, 8], [7, 8]}

다음 순서인 [1, 6]이 배치될 수 있는 Machine이 없으므로 생성.

L = {[3, 7], [5, 9], [6, 8], [7, 8]}

Machine 생성

L = {[5, 9], [6, 8], [7, 8]}

[3, 7]은 Machine1에 들어갈 수 있다.

L = {[6, 8], [7, 8]}

[5, 9]는 Machine3에 들어갈 수 있다.

L = {[7, 8]}

L = {}

 

시간복잡도

m = 사용된 기계의 수

n = 작업의 개수

O(n log n) + O(mn)