[Greedy Algorithm] Deadline Scheduling

Problem Definition

• N Jobs, \(J_1\), \(J_2\). ..., \(J_N\)
• Each \(J_i\) = (\(D_i\), \(P_i\)) > \(D_i\) : Deadline, \(P_i\) : Profit
• There are time slots where you can schedule jobs
• Each job takes 1 slot to finish

profit은 이익, deadline 전에 끝내야한다. 

 

어떠한 1차원 배열이 있다고 생각하고, 어떤 job가 slot에 들어가는지 생각해보자

 

ex) {(2,2), (1,3), (1,1)}

deadline이 1인게 2개 있기 때문에, 그 중 하나밖에 할 수 없다. 최대 profit은 5가 된다. 

 

Assumption

• All deadlines are ≤ N
  Job을 놓을 수 있는 slot을 N까지만 생각해도 된다.
  만약 어떤 Job이 N 뒤에 deadline 이면, 앞으로 땡겨오면 된다. (앞으로 땡겨오는 것은 아무런 문제가 되지 않음)
  앞에 빈자리가 반드시 있다. 
• Jobs are given in nonincreasing order of profits
  profit이 큰 것부터 주어진다.
  큰 것부터 주어지지 않는다고 하더라도 그냥 sorting을 통해서 하면 된다. 
• In an optimal Schedule, no job appears after its Deadline
  최적화된 스케줄링에서, 데드라인 뒤에 job이 나오지 않는다. > profit을 얻을 수 없으므로 빼버려도 상관 없음

 

Intuition / Algorithm

• Schedule Higher Profit First
• If there are Slots available for Current Job, Schedule as late as possible

profit이 큰 것부터 넣는데, 데드라인을 기준으로 가장 가까이 뒤쪽에 넣을 수 있는 곳에 job을 할당함.

만약, 나중에 profit이 적은 것이 넣을 자리가 없다고 하더라도 높은 profit이 오는 것이 이득이다. 

 

Correctness 

Let's call the algorithm (partial) Schedule A

현재 스케줄을 만들고 있는 것이 A (job이 할당되는 등)

 

Invariant : After Deciding \(J_i\), there is at least one optimal solution S such that the followings are true

job \(J_i\)까지 보면 optimal solution이 존재한다. (mst의 invariant와 비슷하다)

*mst와 같이 답이 여러개 존재할 수 있다 (profit이 다 같다면)

1. For j ≤ i, \(J_i\) appears in A iff J \(J_i\) appears in S (이미 입력한 job들은 S에도, A에도 그대로 존재해야한다.)
2. Further, such \(J_j\) appears at the same slot in A and S 

proof by invariant

base 

i = 0, vacuously True

step

Assume invariant is True for i, prove for i +1

 

case1 :

Algorithm does not sechdule \(J_{i+1}\) : no empty slot at or before \(D_{i+1}\) 

데드라인 이전에 넣을 자리가 없기 때문이다.

so, the slots are filled with jobs 즉, 데드라인 \(D_{i+1}\) 전에는 전부 \(J_1\), \(J_2\) .. 으로 채워져있음.

invariant에 따르면, A와 S는 \(J_i\)까지 동일하므로, A와 같이 S에도 전부 채워져있을 것이다.

따라서 S도 \(J_{i+1}\)을 버릴것이다. 

 

case 2 : 

Algorithm schdules \(J_{i+1}\) at t

t라는 자리에 \(J_{i+1}\)을 넣는 경우

 

case 2-1 ) no \(J_{i+1}\) in S 

case 2-1-1) slot t empty in S : S에 \(j_{i+1}\)을 t에 추가하면 더 이득이다. 더 좋은 솔루션이다. -> 모순

case 2-1-2) slot t has \(J_x\) in S -> x > i+1이다. 그 이유는 i까지의 job들은 모두 S와 A가 같기 때문이다. 

x> i+1 이므로 \(P_x\)≤\(P_{i+1\)이다. 

만약, profit이 같으면 같은 답과 마찬가지므로 \(J_x\)를 \(J_{i+1}\)로 바꾸면 되고

profit이 x가 더 작다면 모순이다.

 

case 2-2) \(J_{i+1}\) is at t' in S

case 2-2-1) t' = t이면 결국 같은 자리에 있는 것이므로 가능하다

case 2-2-2) t' > t -> impossible 
알고리즘이 t에 두었다는 것은 데드라인까지 뒤쪽이 다 꽉 차있기 때문이다. 이것은 S,A가 동일하다. 따라서 뒤에 놓을 수 없다. 

case 2-2-3) t' < t -> swap slots t and t' in S

t'이 앞에 있다면, 바꾸는 것이 상관 없다. deadline 전에 오는 것은 전부 profit을 가진다. 

만약 t'이 앞에 있는데, t의 자리로 (뒤로) 가더라도 profit을 얻을 수 있고, 

만약 t에 자리에 어떤 job이 있는데, t'의 자리로 (앞으로) 가더라도 무조건 deadline 앞이기 때문에 profit을 얻는다. 

 

Performance

If you do the schduling naively it takes O(\(N^2\)) time

 

Use Balanced Tree

• Insert every Slot initially
• At each step with deadline \(D_i\), query the Tree to find 
• Maximum value in Tree less than or equal to \(D_i\)
• Deleate the slot from Tree if scheduled

나의 등수를 알 수 있다. 왼쪽 오른쪽에 얼마나 있는 것을 보고 알 수 있다. 

큰것을 포기하고 바로 앞에 있는 것을 확인할 수 있음

>> O(N log N) time

 

Another Job Scheduling Problem

Problem Definition

• N Jobs
• Each \(J_i\) = (\(S_p\), \(T_i\)), smae profit
• \(S_i\) : Start time
• \(T_i\) : End time
• No Two jobs can run simultaneously

Solution

Sork by End time 가장 빨리 끝나는 job을 넣음

going through jobs, schedule if possilbe, that is greedly schedule earlist-ending job

가장 많은 개수의 job을 스케줄링 할 수 있다. 

 

 Proof

알고리즘을 만들어 나가는 것을 A

정답을 S

알고리즘이 첫번째 job을 배치를 하고, 정답이 S라고 하자

알고리즘이 어떤 job을 버림 -> S도 해당 job을 버림 (A에서 배치된 job은 S에서도 배치됨)

 

invariant는 알고리즘이 지금까지 배치한 job은 solution S에도 똑같이 배치가 되어있음

S-A에서 endtime이 가장 빠른 job를 가져옴

즉, 새로 가져오는 것은 무조건 endtime이 전에 온 것들보다 뒤이다. 

 

job이 있는데, 두 개가 일부분 겹친다. 이는 바꿀 수 있음 -> profit이 같음

job가 있는데, 만약 3개가 일부분 겹친다면 이는 profit이 다르기 때문에 바꾸지 않는다. 

 

 

>> O(n)