10. deadline scheduling 문제 [4 2주차]

10. Deadline Scheduling 문제 [4-2주차]

2024년 1월 9일 화요일

오후 11:24

<Deadline Scheduling>

N개의 할 일 J₁, J₂, …, J_N 가 있다.

각각의 J_i = (D_i, P_i)

D_i : deadline. D가 5이면 5시 내에 그 일을 끝내야 한다.

P_i : 일을 끝냈을 때의 이익

 

각각의 일은 1시간이 걸린다.

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

(1, 3), (1, 4)를 모두 할 순 없다. 이익이 큰 (1, 4)를 하는 게 좋을 것이다.

 

 

N개의 슬롯에 최대한 이익이 크도록 job을 배치하자.

 

 

<가정>

1.     모든 deadline은 N 이하이다.

2.     일들은 이익이 큰 것부터 정렬되어 제공된다.

3.     deadline 이후에 일이 배치될 수 없다.

 

 

<알고리즘>

1.     이익이 큰 것부터 배치

2.     일을 배치할 수 있는 공간이 존재한다면, 최대한 늦은 시간대에 배치한다.

 

 

<증명>

알고리즘이 만들고 있는 스케줄을 A라 한다.

Invariant : J_i 를 배치한 뒤, 다음 2가지를 만족하는 정답 S가 존재한다.

a.     j<=i 일 때, J_j가 A에 존재 <=> J_j가 S에 존재한다.

b.     J_j는 A와 S에서 서로 같은 슬롯에 위치한다.

요약하면, A는 임의의 정답 S를 만들어 나가고 있다.

 

Base) i=0일 때, 당연히 참이 된다.

Step) i에서 invariant가 참이라고 가정하고, i+1일 때 참이 된다는 것을 증명하자.

1.     알고리즘이 J_i+1을 버리는 경우, A에서 deadline 이전이 가득 차 있을 것이다. invariant가 i까지 유지되므로, S도 deadline이전이 가득 차 있을 것이다. 따라서, S에 J_i+1이 존재할 수 없고, i+1에서 invariant가 참이 된다.

2.     알고리즘이 J_i+1을 A의 k에 배치하는 경우

• S에 J_i+1이 없다면

S에서 k는 빈 자리이거나 다른 job이 있을 것이다.

빈 자리라면 그 자리에 J_i+1을 배치하면 더 좋은 답이 나오므로 모순이 발생한다.

다른 job이 있다면 그 job의 번호는 i이하일 순 없다. i까지는 invariant가 성립하는데, A에서 i이하의 job은 k에 배치되지 않았기 때문. 따라서 그 job의 번호는 i+2이상일 것이다. 번호가 크므로, 이익이 J_i+1보다 작을 것이다. k에 J_i+1을 배치하면 더 좋은 답이 되므로 모순이다.

(이익이 J_i+1과 같다면, 중복 정답이 된다)

• S에서 J_i+1이 k보다 작은 k'에 위치한다면

k와 k'에 배치된 job의 위치를 서로 바꿔도 문제가 없다. J_i+1의 deadline은 k 이상이므로 k에 배치할 수 있고, job의 위치를 k에서 그보다 더 작은 k'으로 옮기는 것은 항상 가능하기 때문.

• S에서 J_i+1이 k와 deadline 사이의 k''에 위치한다면

알고리즘은 최대한 뒤에 배치하므로, J_i+1을 A의 k에 배치하지 않았을 것이다. A에 k''이 이미 차 있었다고 가정하면, S에서는 i+1을 배치하기 전까진 k''이 비어 있었을 것이므로, invariant가 i까지 유지된다는 가정에 위배된다.

 

 

<성능>

이진 탐색 트리에 슬롯 번호를 배치.

job을 배치할 때마다 deadline으로 이진 탐색하여 배치될 슬롯을 찾는다.

슬롯에 job이 배치되면 그 번호를 이진 탐색 트리에서 제거.

트리에서 각각 N번의 삽입, 탐색, 삭제 연산이 이루어진다.

AVL트리를 사용하면 연산 하나에 O(logN)이 걸리므로 시간복잡도는 O(NlogN)이다.

 

 

<다른 job scehduling 문제 (활동 선택 문제)>

job의 시작 시간과 종료 시간이 각각 정해져 있고, profit이 없는 경우, 어떻게 배치해야 가장 많은 job을 수행할 수 있는가?

종료 시간이 가장 빠른 것부터 배치.

 

 

증명 :

알고리즘이 집합 A = {J₁, J₂, … , J_i} 를 만들었고, A가 S의 부분집합이 되는 정답 S가 존재한다고 가정한다. A가 S에 없는 J_i+1을 추가해 A'이 되었다고 가정한다.

집합 S-A의 원소 중 가장 종료 시간이 빠른 작업을 J_k라 하면, S에서 J_k를 제거하고 J_i+1을 추가할 수 있다. 알고리즘이 J_i+1을 선택했기 때문에 J_i+1의 종료 시간이 J_k보다 빠를 것이고, S에서 J_k이전에는 집합 A의 원소만 존재하기 때문이다.

 

따라서 S에서 J_k를 제거하고 J_i+1을 넣으면, 이는 중복 정답이 된다. J_i+1이 S에 없다는 가정에 모순이 생긴다.

따라서 위 알고리즘은 항상 정답에 존재하는 job을 선택한다.

 

 

<Tape Storage>

N개의 데이터를 저장한다.

• L_i : 데이터의 크기. 테이프의 길이
• F_i : 해당 데이터를 읽을 확률. 자주 쓰는 정도.

 

어느 데이터를 읽기 위해서는 저장 공간의 처음부터 그 데이터 끝까지 읽어야 한다. 따라서 데이터 i가 k에 배치되었다면, 그 데이터를 읽는 데 걸리는 시간은 k + L_i 이다.

 

데이터 i를 읽는 데 걸리는 시간의 기댓값은 F_i * (k + L_i)이다. 전체 기댓값은 모든 데이터의 기댓값을 더하면 구해진다.

 

데이터 전체를 읽는 데 걸리는 시간의 기댓값이 최소가 되려면 데이터를 어떻게 배치해야 하는가?

 

-> F_i/L_i가 큰 순서대로 저장하면 된다.

 

증명

데이터가 1, 2, ..., i, i+1, … 순으로 배치되었을 때,

F_i/L_i < F_i+1/L_i+1 이라면 최적의 답이 아니라는 것을 증명하자.

데이터 i 를 데이터 i+1보다 먼저 배치한 경우 기댓값은

• F₁L₁ + F₂(L₁+L₂) + … + F_i(L₁+…+L_i) + F_i+1(L₁+…+L_i+L_i+1)

… (1)

그런데 i+1을 i보다 먼저 배치한다면

• F₁L₁ + F₂(L₁+L₂) + … + F_i+1(L₁+…+L_i-1+L_i+1) + F_i(L₁+…+L_i+L_i+1)

… (2)

(1)-(2) = F_i+1L_i - F_iL_i+1 = L_iL_i+1(F_i+1/L_i+1 - F_i/L_i) > 0

 

따라서 데이터 F/L 이 큰 값이 나중에 배치된다면 답이 될 수 없다. F/L이 큰 값을 먼저 배치해야 한다.