Deadline Scheduling

0. 문제 정의

N개의 job이 있다. J1, J2 ... JN

각각의 job은 Ji = (Di, Pi) deadline과 profit을 갖는다. 

각 job은 한시간의 slot을 차지한다. 

이때 최대 profit을 얻는 scheduling을 구하라. 

 

1. 해결 알고리즘 제시

- profit을 기준으로 오름차순 정렬을 한다. 

- 현재의 job에게 가능한 slot이 존재할 때, 가능한 늦게 배치하자. 

 

2. 정확성 증명

[proof by loop invariant]

가설: 알고리즘에 따르는 schedule 경우 A와 정답 S가 있을때, Ji는 A와 S에 있으면 둘 모두 있고, 각각 같은 자리에 있다. 

 

위 가설이 모든 J에 대해 항상 성립한다. (terminate 에서 성립한다면, A는 S, 정답과 동일한 상태가 되는 것이므로 알고리즘의 정확성이 증명된다.)

Base : i = 0일때, 

Step : Ji에 대하여 참일때, Ji+1에 대하여 참임을 보이자. 

Ji는 참인 상황이다.

Ji+1이 A에 scheduling 되는 상황은 아래의 경우 내에서 존재한다. 

 

Case 1. A 가 Ji+1을 scheduling 하지 못했다. 

Ji+1을 배치하지 못한 경우는 Di+1 (deadline) 이전의 slot이 모두 "나보다 높은 profit"의 job들로 가득 차 있다는 의미이다. 

이는 Ji가 참이라는 가정에 의해 S도 동일한 배치를 가지고 있음을 알 수 있다. 

그러므로 Invarianat 가설을 깨지 않는다. (문제가 없다.)

Case 2. A가 Ji+1을 scheduling 했다. 

A가 Ji+1을 배치한 자리를 k라고 하자. S가 Ji+1을 배치한 자리를 t라고 하자.

case 2-1. k = t

-> A는 Ji+1을 올바른 위치에 배치했다. (알고리즘에 문제될 상황이 아니다.)

case 2-1. k != t

-> A는 Ji+1을 S와 완전히 똑같은 올바른 위치에 배치하지 않았다. (알고리즘에 반하는 상황이 발생했다.)

그렇다면, S의 k 자리에는 Ji+1이 아닌 무엇이 있는가?

------> 1. k에는 Pi+1보다 profit이 작은 값이 존재한다. (Ji가 참이므로 profit이 더 큰 job들의 위치는 이미 A와 S가 동일함.)

-------------->  1.1 [t자리 .... k 자리 ....]인 경우 : S는 k자리에 빈 곳이 있는데도 불구하고 앞서는 t 자리에 Ji+1을 넣었다. 이 경우는 k자리에 존재하는 job과 t 자리에 존재하는 job의 위치를 바꾸어 주면 된다. 둘 모두 deadline 이전의 자리이기 때문이다.

--------------> 1.2 [k자리 .... t 자리 ....]인 경우 : A는 t자리에 Ji+1을 배치할 수 있음에도 불구하고 k 자리에 배치했다. 이는 알고리즘을 따랐다는 가정에 모순이다. 알고리즘을 따랐다면 이 경우는 존재할 수 없다. (모순)

--------------> 1.3 [S는 Ji+1을 배치 하지 않은] 경우 :: 빈자리라면 Ji+1을 넣어주고, 누군가가 있다면, 분명 자신보다 작은 profit일 것이므로 바꾸어 넣어주면 된다. 

 

------> 2. k에는 job이 존재하지 않는다.  

-------------->  2.1 [t자리 .... k 자리 ....]인 경우 : 바꾸어 넣어주면 된다. 

--------------> 2.2 [k자리 .... t 자리 ....]인 경우 : 

 

3. 회의실 배정 문제

"같은 회의 목록을 가지고 더 적은 타임에 많은 회의를 넣는것이 가능할까? 당연히 불가능하다."라는 말이 가장 이해하기에 와닿았다. 

시작하는 시간은 중요하지 않다. 종료하는 시간만 중요하다. 

왜나면, 종료하는 시간(t < t') 에 대해서는 남은 시간이 확정된다. (L > L')

L > L' 인경우에, 우리는 L 또는 L' 내부에서 같은 회의 목록을 확용하여 배치해야 한다. 

그러므로, t < t'가 더 많은 회의를 배정할 수 있음을 알 수 있다.