Deadline Scheduling

Problem definition

  • N jobs: J1, J2, …, Jn
  • each Ji = (Di, Pi)
    • Di: deadline
    • Pi: profit
  • There are 1 hr time slots where you can schedule jobs
  • Each job takes 1 hr to finish
  • Example: {(2, 2), (3, 1), (1, 1)}

Assumptions

  • All deadlines are <=N (the number of jobs)
  • Jobs are given in nonincreasing order of profits
  • In an optimal schedule, no job appears after its deadline

Intuition/Algorithm

  • Schedule jobs with higher profit first
  • If there are no slots available for the current job, don’t schedule
  • If there are slots available for the current job, schedule as late as possible (뒷쪽에 있을수록 방해하는게 줄어들기 때문임!)

Correctness

다행히도 greedy 알고리즘의 standard(Prim, Kruskal)한 증명 패턴 - 답을 벗어나지 않는다는 것을 계속 보여주는 형식 - 을 따른다. 어떤 job이 어디에 있느냐까지 포함하기 때문에 약간 더 복잡할 뿐이다.

  • Let’s call the algorithm (partial) schedule A
  • Invariant: after deciding Ji, there is at least one optimal solution S such that the followings are true:
    • for j < i, Jj appears in A iff Ji appears in S
    • further, such Jj appears at the same slot in A and S

만약 이 invariant가 사실이면 알고리즘이 끝났을 때 정답이 찾아진다는 얘기가 된다. 알고리즘이 끝났을 때는 Jn을 고려한 이후로, for j<=n 은 결국 for all jobs 와 같은 의미이기 때문이다. 따라서 우리는 위 invariant가 참임을 증명하기만 하면 된다.

Proof of Invariant

수학적 귀납법으로 증명할 수 있다. base와 step이 참임을 증명해보자.

  • Base: i = 0, vacuously true
    • 아무것도 안 본 상태니까 A는 비어있다.
    • i보다 큰 job들은 다 빼니까 S도 비어있다.
  • Step: assume invariant is true for i, prove for i+1

아래와 같은 경우를 생각해보자. 현재 i까지 진행된 상태에서 Ji+1을 scheduling하려고 한다.

scheduling_1

A에 있는 것들은 S에서 전부 똑같은 위치에 있고 S에는 추가적으로 나중 job들이 있을 수 있다.

scheduling_2

이제 i+1번째를 고려해보자. A에 빈 slot이 있을 때와 없을 때 두 경우로 나눌 수 있다.

빈 slot이 없는 경우(알고리즘이 Ji+1을 버리는 경우)

A에서 deadline 이전 slot들이 꽉 차있었다는 의미이므로 S에서도 deadline 이전 slot들이 J1, J2, …, Jn의 일부로 가득 찼다는 것을 의미한다. 그러면 Ji+1이 만약 있다면 S에서 deadline 이후에 등장할 수 밖에 없다.

그런데 deadline 이후에 있는 건 의미가 없을 뿐 아니라 정답엔 deadline 이후에 있는 것은 없다고 가정했으므로 Ji+1은 정답에 등장하지 않는다. 따라서 Ji+1 not in S이므로 invariant가 성립한다.

빈 slot이 존재하는 경우 (알고리즘이 Ji+1을 x번째 slot에 배치하는 경우)

S의 x번째 slot에 무슨 값이 들어있냐에 따라 나눌 수 있다.

S에 Ji+1이 등장하지 않는 경우
  • S의 x번째 slot이 비어있는 경우
    • x에 Ji+1을 채운다. 이 값이 가장 좋은 답이므로 S가 최적이라는 가정에 모순이다.
  • S의 x번째 slot에 Jp가 배치된 경우
    • 이때 p > i+1이다. p <= i+1라면 A의 같은 번째 slot에 job이 할당되어 있었을 것이다.
    • Jn의 profit이 Jn+1의 profit보다 크거나 같으므로 Ji+1>Jp이다. 따라서 Jp를 버리고 그 자리에 Ji+1을 넣는 것이 전체 profit이 더 커질 것이다. 따라서 S가 최적이 아니므로 가정에 모순이다.
S에 Ji+1이 등장하는 경우

아래의 세 가지 경우가 가능하다.

  • S의 x번째에 Ji+1이 등장하는 경우: 정답

  • S의 y (y < x)번째에 Ji+1이 등장하는 경우
    • 교환한다. S에서는 x번째 slot이 비어있을 수도 있고 채워져 있을 수도 있다. 이때 Ji+1과 x번째 slot에 할당된 job(만약 있다면)을 swap한다.
    • swap하면 순서만 바뀌는 것이지 total profit의 값이 변하지 않으므로 여전히 정답이다.
  • S의 y (y > x)번째에 Ji+1이 등장하는 경우
    • 불가능하다. x는 deadline 앞쪽에서deadline과 가장 가까운 빈 slot이다. 즉, x이후와 deadline 사이에는 빈 slot이 없고 J1~Ji 사이의 값들로 차있다. 따라서 불가능하다.

Performance

  • If you do the scheduling naively, it takes O(N^2) time 대충 짜면 O(N^2). 빈 자리를 다 훑어보면 된다,,

  • Use balanced tree

    • Insert every slot initially
    • At each step with deadline Di, query the tree to find the maximum value in the tree less than or equal to Di
      • Delete the slot from the tree if scheduled
      • This results in O(NlogN) time

job이 들어간 자리들은 다 죽은 걸로 치고 살아있는 자리들 중에 얼마 이하인 것 중에 젤 큰 것을 빨리 찾는 방식이다. AVL이나 RB tree 같은 balanced tree로 구현하면 search와 insert를 log N 시간에 할 수 있다.

처음에는 다 살아있으니까 모든 값들을 tree에 다 집어넣는다.

그다음에 schedule이 되면 죽는거니까 tree에서 delete한다. 그러면 빈 자리들만 tree에 들어있는다. 이 과정은 balanced tree에서 log N 시간에 할 수 있다.

그럼 이제 “얼마 이하인 것” 중에 가장 큰 값을 찾는 과정을 보자. (binary search tree visualiser)

scheduling_3

14 이하의 값 중에서 가장 큰 값을 찾고 싶을 때는 트리를 타고 가면 14를 얻으므로 14가 답이다.

그러면 12 이하의 값 중에서 가장 큰 값을 찾을 때는 어떻게 할까? 14를 찾을 떄와 동일한 방법으로 트리를 타고 내려오면 11에 도착하게 된다. 12>11이므로 오른쪽으로 내려가야 하지만 11이 leaf 노드이므로 더 이상 내려갈 수 없다.

이 경우 가장 최근에 오른쪽으로 꺾은 곳, 즉 10이 답이다.

scheduling_4

아니면 각 노드마다 자신의 value와 subtree의 value range를 표기해 주는 방식도 있다.

scheduling_5