[알고리즘] 5. Deadline Scheduling

1. 문제 정의

N개의 Job $J_1, J_2, ..., J_N$이 있다. 각 Job은 $J_i=(D_i, P_i)$ 으로 구성되어 있고, $D$는 Deadline, $P$는 Profit을 의미한다. 1시간 단위의 타임 슬롯이 존재하고, 모든 일은 1시간이 소요된다고 가정하자. 이때 가장 Profit을 많이 얻을 수 있는 스케줄링 방법은 무엇일까?

• 모든 데드라인은 $N$ 이하라고 가정. ($\because N$보다 크면 $N$으로 바꿔 생각해도 아무 문제가 없음)
• Job들은 Profit이 큰 것부터 작은 순으로 내림차순 정렬되어 있는 상태라 가정.
• 최적 스케줄에선 데드라인 이후의 일은 안 나온다고 가정.

직관적으로, 높은 이익의 일들을 먼저 빈자리들 중 가장 뒤에 배치하는 것이 제일 효율적이라고 생각할 수 있다. (Greedy 알고리즘)

 

2. Invariant의 증명

Invariant: $i$번째 Job $J_i$를 처리한 직후, 아래 주장을 만족하는 적어도 하나의 optimal solution $S$ 가 존재한다.
- 스케줄링 알고리즘의 solution을 $A$라 하자. $i$보다 작은 $j$에 대하여, $J_i$가 $A$에 나오면 $J_i$는 S에도 나오며, 위치가 모두 동일하게 나온다.

 

• Base: $i=0$일 때: Vacuously True
• Step: 알고리즘 $A$가 $J_i$까지 처리한 시점에서 Invariant가 True라고 가정하자.
• Case 1: $A$가 $J_{i+1}$을 버리는 경우: $A$에서 $D_{i+1}$ 이전의 스케줄이 가득 찼고, 가정에 의해 $S$에서도 $D_{i+1}$ 이전도 $J_1, ..., J_n$ 들 중 일부들로 꽉 찼다는 뜻이다. 그러므로 $J_{i+1}$은 $S$에도 없다.
• Case 2: $A$가 $J_{i+1}$을 slot $K\ (K \leq N)$ 에 배치하는 경우: 아래와 같이 조금 더 케이스를 분류해야 한다.

---

• Case 2-1: $S$의 slot $K$에 $J_{i+1}$이 존재하는 경우: 위치가 동일하므로 Invariant가 성립한다.
• Case 2-2: $S$의 slot $K'\ (K' \leq K)$에 $J_{i+1}$이 존재하는 경우: $A$에서 slot $K+1$부터 $D_{i+1}$까지가 $J_1, ..., J_n$들 중 일부로 가득 찼고, 가정에 의해 $S$도 동일하다. $S$ 에서 slot $K$와 slot $K'$을 교환한 새로운 optimal solution $S'$을 생각하자. $A$와 $S'$이 모두 위치가 동일하므로 Invariant가 성립한다.
• Case 2-3: $S$에 $J_{i+1}$이 없는 경우: 
  • $S$의 slot $K$가 비어있는 경우: $S$가 정답이 아니므로 모순이 발생한다.
  • $S$의 slot $K$에 $J_x\ (x > i+1)$가 있는 경우: $P_x \leq P_{i+1}$이므로 해당 slot에 $P_{i+1}$로 바꿔도 된다.

 

3. Deadline Scheduling의 성능

균형 트리를 이용하여 $O(N\log N)$ 시간만에 구할 수 있다.