작업 스케줄링(Task Scheduling)

작업 스케줄링(Task Scheduling)

• 기계에서 수행되는 n개의 작업들을 수행 시간이 중복되지 않도록 가장 적은 수의 기계에 배정하는 문제이다.

  • 각 작업은 시작시간과 종료시간이 정해져있다.

  • 발표 시간이 정해진 학술대회에서 발표자들을 강의실에 배정하는 문제와 같다.

---

알고리즘

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

  • 빠른 시작 시간 작업 우선 (Earliest Start Time First)

  • 빠른 종료 시간 작업 우선 (Earliest Finish Time First)

  • 짧은 작업 우선 (Shortest Job First)

  • 긴 작업 우선 (Longest Job First)

  • 여기서는 최적해를 찾기 위해 첫 번째 방법을 선택한다.

• 빠른 시작 시간 작업 우선 (Earliest Start Time First)

  Pseudo Code

  JobScheduling(Task *arr)
  {
    Task list[] = arr를 시작 시간을 기준으로 오름차순 정렬한 배열
    while (list에 원소가 존재하면)
    {
      t_i = (가장 이른 시작 시간을 가진 작업);
      if (t_i를 수행할 기계가 존재하면)
        t_i를 해당 기계에 배정한다.
      else
        새로운 기계에 t_i를 배정한다.
      t_i를 list에서 제거한다.
    }
    return 각 기계에 배정된 작업 순서
  }

---

예제

• 시작 시간과 종료 시간을 [start time, end time]이라고 표기한다.

  t₁ = [7, 8]

  t₂ = [3, 7]

  t₃ = [1, 5]

  t₄ = [5, 9]

  t₅ = [0, 2]

  t₆ = [6, 8]

  t₇ = [1, 6]

• 시작 시간을 기준으로 오름차순 정렬하여 list에 저장하면 다음과 같다.

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

  

---

시간 복잡도

• 배열을 정렬할 때 O(nlogn) 시간이 걸린다.

• 사용된 기계의 수를 m이라고 하면, 루프 내부에서 기계를 찾을 때의 시간 복잡도는 O(m)이다.

  • 루프가 n번 반복되므로 총 O(mn)이다.

• 따라서 총 시간 복잡도는 O(nlogn) + O(mn)이다.