Job Scheduling

Job Scheduling 문제

• 작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 저근 수의 기계에 배정하는 문제
  학술대회에서 발표자들을 강의실에 배정하는 문제와 같음

Job Scheduling 문제에 주어진 문제 요소

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

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

• 그리디 알고리즘을 적용하기 위해서는 Earliest start time first 방법을 제외하고는 최적해를 찾을 수 없다.

Pseudo Code

JobScheduling
입력: n개의 작업 t_1,t_2,...,t_n
출력: 각 기계에 배정된 작업 순서

1. 시작시간으로 정렬한 작업 리스트: L
2. while L != NULL
3.    L에서 가장 이른 시작 시간 작업 t_i를 가져온다.
4.    if t_i를 수행할 기계가 있으면
5.        t_i를 수행할 수 있는 기계에 배정
6.    else
7.        새 기계에 t_i를 배정
8.    t_i를 L에서 제거
9. return 각 기계에 배정된 작업 순서

여기서 't_i를 수행할 기계가 있으면' 을 자세하게 풀어보자면,
시작시간 기준으로 정렬한 작업 리스트가 있을 때, 순서대로 처리되므로, 현재 처리중인 기계의 작업 종료시간보다 t_i의 시작시간이 더 늦다면 배정이 가능하므로 기계에 배정한다.
또는 배정할 수 없는 경우, 기계의 리스트를 탐색하여 배정할 수 있는 기계에 배정한다.

수행 과정

$t_1=[7,8], t_2=[3,7], t_3=[1,5], t_4=[5,9], t_5=[0,2], t_6=[6,8], t_7=[1,6]$
이라는 작업이 주어질 때 ([시작,종료]) 시작시간에 따라 정렬하면
$L={[0,2],[1,6],[1,5],[3,7],[5,9],[6,8],[7,8]}$로 주어진다.

시간 복잡도

1. 정렬 시간 $O(nlogn)$
2. while 루프: 작업량을 순회하므로 m번 소요, 그리고 내부에서 기계의 리스트를 또 탐색하므로 n번 소요된다. 따라서 $O(mn) or O(n^2)$
3. 최종 시간복잡도: $O(mn(n^2))+O(nlogn)$