작업 스케줄링

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

1. 작업 스케줄링문제를 구성하는 주요 요소

• 작업의 수
• 각 작업의 시작시간과 종료시간
• 작업의 길이(종료시간-시작시간)

2. 그리디 알고리즘 설계 방법

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

  위 방법 중 첫번째 방법을 제외한 세가지 방법은 항상 최적해를 찾지 못한다. 따라서 첫번째 방법을 사용하여 문제를 풀어보자

3. 알고리즘 수행과정

• Test Case
  

1) 시작 시간을 기준으로 오름차순 정렬

2) 가장 이른 시작 시간을 갖는 작업을 가져옴

3) 현재 기계중 작업을 수행할 기계가 있다면 배정, 없다면 새 기계를 배정

4) 해당 작업을 정렬한 작업에서 제거

5) 해당 과정을 반복

4. 시간복잡도

• 작업 리스트 정렬에 소요되는 시간: O(nlogn)
• while-루프가 모든 작업에 대해 한번씩 수행: n
• m개의 머신 중 작업 가능한 머신을 찾는 과정: O(m)
• 총 시간복잡도: O(nlogn)+O(mn)
  • logn과 m의 관계를 비교할 수 없으므로 + 로 표현