Job Scheduling and Tape Storage

Job Scheduling

• 문제 정의
  • N개의 일들이 있다. $J_{1}, J_{2},, ... J_{n}$으로 정의한다.
  • 각각의 일 $J_{i} = (S_{i}, T_{i})$
    • $S_{i} = 시작 시간(Deadline)$
    • $T_{i} = 끝나는 시간(Profit)$
  • 얼마나 많은 일을 할 수 있는가?

해결

• 끝나는 시간을 기준으로 넣으면 된다.
• 현재 시간보다 $S_{i}$가 높거나 같은 일들 중 $T_{i}$가 가장 낮은 일을 골라서 넣으면 된다.
• 기준에 충족하는 $J_{i}$를 넣을 때, 아직 들어가지 않은 일 $J_{k}$의 경우는 다음과 같다.
  • $S_{i}$가 현재 시간보다 낮음 : 고려 대상이 아님
  • $S_{i}$가 현재 시간보다 높고, $T_{i}$가 높음 : $J_{i}$의 끝나는 시간과 $J_{k}$의 끝나는 시간의 차이가 있으므로, 그 시간만큼 손해를 봄.
  • $S_{i}$가 현재 시간보다 높고, $T_{i}$가 낮음 : $J_{k}$를 넣으면 됨. 다른 말로 모순임(우리 알고리즘을 수행한 게 아님)

참고

Tape Storage

• 문제 정의
  • N개의 데이터가 있다. 매개변수 $L_{i}$, $F_{i}$가 있다.
    • $L_{i} = 데이터의 양(테이프의 길이)$
    • $F_{i} = 사용 빈도$
• 읽기와 쓰기
  • 쓰는 건 한번뿐이다.
  • 읽는 건 여러번 할 수 있다.
  • 읽을 때는 무조건 처음부터 읽는다.

알고리즘

• $L_{i}$가 크면 뒤에 있어야 한다. 앞에 있으면 많이 읽히므로 데이터 소모가 크다.
• $F_{i}$가 크면 앞에 있어야 한다. 자주 사용되기 때문에 빨리 끝나기 때문이다.

그러므로 $\frac {F_{i}} {L_{i}}$이 큰 순서로 앞에서부터 배치한다. 별 문제가 없어보인다. 하지만 다른 대안들이 여러가지가 있다.

• $\frac {F_{i}^2} {L_{i}^2}$
• ${F_{i}} - {L_{i}}$
• ...

Correctness

• $\frac {F_{i}} {L_{i}} < \frac {F_{i+1}} {L_{i+1}}$

테이프의 i 와 i+1을 교환 후 기댓값
$F_{1}L_{1} + ... + F_{i}(L_{1} + ... + L_{i}) + F_{i+1}(L_{1} + ... + L_{i} + L_{i+1})$
$F_{1}L_{1} + ... + F_{i+1}(L_{1} + ... + L_{i-1} + L_{i+1}) + F_{i}(L_{1} + ... + L_{i-1} + L_{i+1} + L_{i})$
서로 빼면 사라지고
$F_{i+1}L_{i} - F_{i}L_{i+1}$
= $L_{i}L_{i+1}(\frac{F_{i+1}}{L_{i+1}} - \frac{F_{i}}{L_{i}}) > 0$
$(\frac{F_{i+1}}{L_{i+1}} - \frac{F_{i}}{L_{i}}) > 0$

이 말이 의미하는 것은 $\frac {F_{i}} {L_{i}}$는 i가 증가할수록 커진다는 의미이며 데이터 소모량이 증가한다는 의미와도 같다.