# 5.6. Scheduling: Minimizing Lateness

# Problem

• Let J = {1, 2, ..., n} be a set of jobs to be served by a single processor.
• The $i$th job takes t_i units of processing time, and is due at time d_i.
• When the $i$th job starts at time s_i, its lateness l_i = \max{0, s_i + t_i - d_i }.
• Goal: Find a schedule S so as to minimize the maximum lateness
  • L = \max{l_i}.

# Example

• S = {3, 2, 6, 1, 5, 4} → maximum lateness = 6 | Job | t_i | d_i | | ---- | ------ | ------ | | 1 | 3 | 6 | | 2 | 2 | 8 | | 3 | 1 | 9 | | 4 | 4 | 9 | | 5 | 3 | 14 | | 6 | 2 | 15 |

# Possible greedy approaches

• Sort jobs in nondecreasing order of processing time ti
  • Shortest Jobs First (?)
• Sort jobs in nondecreasing order of slack d_i - t_i :
  • Smallest Slack-Time First (?)
• Sort jobs in nondecreasing order of deadline d_i :
  • Earliest Deadline First (O)
  • An optimal schedule S = \{1, 2, 3, 4, 5, 6\}
    • → maximum lateness = 1 | Job | ti | di | | ---- | ------ | ------ | | 1 | 3 | 6 | | 2 | 2 | 8 | | 3 | 1 | 9 | | 4 | 4 | 9 | | 5 | 3 | 14 | | 6 | 2 | 15 |

# Correctness of “Earliest-deadline-first”-based algorithm

• 사실
  1. 만약 주어진 schedule에 inversion이 있을 경우, 최소한 연달아 schedule된 두 개의 inversion된 job이 있음.
     • Inversion이란 deadline 관점에서 봤을 때 서로 순서가 뒤 바뀐 두 개의 job의 쌍 을 말함.
  2. 연달아 있는 inversion 상태의 두 개의 job의 순서를 서로 바꿀 경우, maximum lateness를 증가시키지 않음.
• 증명
  1. $S$를 최소 개수의 inversion을 가지는 최적의 schedule이라 가정.
  2. 만약 $S$에 inversion이 없다면, 위의 방법으로 구한 schedule과 동일.
  3. 만약 $S$에 inversion이 있다면, 이 경우 연달아 있는 inversion된 두 job의 순서를 서로 바꾸면, 결과로 발생하는 schedule $S’$는 maximum lateness를 증가시키지 않음으로 역시 또 다른 최적의 schedule임.
  4. 그러나 $S’$는 S 보다 inversion의 개수가 적음. 이는 S에 대한 가정에 대한 모순. 따라서 $S$에는 inversion이 없고 따라서 이는 위의 방법으로 구한 schedule과 동일함.