Job Scheduling

- unit time에 실행가능한 job들이 존재.

- 시간 d(i) 이전에 job i를 수행하면 이익 P(i)

- job은 이익으로 내림차순 정렬되어 있다.

- S(k) = i 는 job i가 k시간에 끝나도록 schedule했다는 의미.

- deadline이 n보다 큰 job은 없다고 가정

 * 구조

- 첫번째 job부터 시작하여 d(i)보다 작고 S(k)=0 인 가장 큰 k에 대해 S(k) = i

 " 알고리즘이 최적의 solution을 얻는다. "

- feasible : deadline을 위반한 job이 없는 schedule

- promising : feasible하면서 최적 solution으로 "확장"될 수 있는 schedule

- 확장 : job i+1, job i+2, ........ job n 들 중에서만 job을 추가함

 " 알고리즘의 모든 단계에서 S는 promising 하다 "

base) 최초에 S는 promising하다. 모든 k에 대해서 S(k) = 0이기 때문이다.

step) 알고리즘이 i-1번째 job을 추가했을때 promising 하다면, i번째 job을 추가했을때 promising 한가?

- 최적 solution 중 하나를 Sopt라 하자.

- 알고리즘은 job i를 가지고 두가지 동작을 할 수 있다. job i를 버리거나, job i를 k에 추가하는 것이다.

1) 알고리즘이 job i를 버렸다는 것은, deadline 앞에 빈 칸이 없을 때이다. 이런 경우의 Sopt에는 i가 없다.

따라서 여전히 promising하다.

2) 알고리즘이 job i를 k번째에 추가했다고 하자. 이 때에도 두 가지 경우가 생긴다.

- i를 추가한 S를 S'라 하자. 즉, S'(k) = i

 2-1) job i가 Sopt에서 k'에 schedule되어 있음. 즉, Sopt(k') = i

k' = k 일 경우, S'는 promising하다.

k' < k 일 경우, Sopt(k)와 Sopt(k')를 교환한다. 조건에 위배되는것이 없으므로, 여전히 promising하다.

k' > k 일 경우는 불가능하다. 알고리즘에서 deadline과 k 사이에는 빈칸이 없기 때문이다.

 2-2) job i가 Sopt에 없을 경우

- 최소한 Sopt(k)는 0이 아니라는 것을 알 수 있다. Sopt(k)를 x라 하자.

- x는 i 보다 더 나중에 나오는 job이다. 따라서 이익이 더 작거나 같다. 따라서 S'opt(k)를 i로 교체한다.

- 그래서 S'는 promising 하다.