[알고리즘] 작업 스케줄링 (Job Scheduling) 문제

작업 스케줄링 (Job Scheduling) 문제

• 작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제
• 학술대회에서 발표자들을 강의실에 배정하는 문제와 같다.
ex) 발표= ‘작업’, 강의실= ‘기계’

 

작업 스케줄링 문제에 주어진 문제 요소

• 작업의 수
 > 입력의 크기이므로 알고리즘을 고안하기 위해 고려되어야 하는 직접적인 요소는 아니다.
• 각 작업의 시작시간과 종료시간
• 작업의 길이
 > 작업의 시작시간과 종료시간은 정해져 있으므로 작업의 길이도 주어진 것

 

시작시간, 종료시간, 작업 길이에 대한 그리디 알고리즘

• 빠른 시작시간 작업 우선 (Earliest start time first) 배정
• 빠른 종료시간 작업 우선 (Earliest finish time first) 배정
• 짧은 작업 우선 (Shortest job first) 배정
• 긴 작업 우선 (Longest job first) 배정

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

 

pseudo code

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 각 기계에 배정된 작업 순서

t1=[7,8]
t2=[3,7]
t3=[1,5]
t4=[5,9]
t5=[0,2]
t6=[6,8]
t7=[1,6]

• [s, f]에서, s는 시작 시간, f는 종료 시간

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

 

 

 

 

시간 복잡도

- Line 1: 정렬 시간 O(nlogn)
- while-루프
   • 작업을 L에서 가져다 수행 가능한 기계를 찾아서 배정하므로 O(m) 시간 소요, 단, m은 사용된 기계의 수
   • while-루프가 수행된 총 횟수는 n번이므로, line 2~9까지는 O(m) x n = O(mn) 시간 소요

따라서 시간 복잡도: O(nlogn)+O(mn)