그리디 알고리즘(6)[작업 스케줄링 JobScheduling]

 

작업스케줄링은 아래의 4가지 정도의 그리디 알고리즘을 짜볼 수 있다.

• 빠른 시작시간 작업을 우선 배정
• 빠른 종료시간 작업을 우선 배정
• 짧은 작업을 우선 배정
• 긴 작업을 우선 배정

하지만 '빠른 시작시간 작업을 우선 배정' 알고리즘만 최적해를 구할 수 있다.

 

시간 복잡도는 O(nlogn) + O(mn)

---

< JobScheduling 슈도코드 >

 

입력: n개의 작업 t1, t2, ~ tn

출력: 각 기계에 배정된 작업 순서

1  시작시간의 오름차순으로 정렬한 작업 리스트를 L이라고 하자.

2  while(L  !=  ∅ ) { // 작업이 다 배정완료 될때까지 반복

3      L에서 가장 이른 시작시간을 가진 작업 ti를 가져온다.

4      if(ti를 수행할 기계가 있으면)

5          ti를 수행할 수 있는 기계에 배정한다.

6      else 

7          새로운 기계에 ti를 배정한다.

8      ti를 L에서 제거한다.

     }

9  return 각 기계에 배정된 작업 순서

 

 

작업들의 시간이 빠른 순서대로 각 기계에 작업들을 할당.

line4 : 다른 기계들보다 사용완료 시간만 빠르다면 같은 기계에도 다시 할당 가능하다.

line6~7 없다면 새로운 기계에 작업 ti를 할당.

 

---

line1 에서 오름차순 정렬에 O(nlogn)

line4~7 기계에 작업을 할당할 수 있는가 기계수 m만큼 들여다봄 O(m)

4~7을 작업수 n만큼 돌게됨. O(m) * O(n)

 

시간 복잡도는 O(nlogn) + O(mn)