###### tags: `ADA 8.4` `Scheduling to Minimize Lateness`
# ADA 8.4: Scheduling to Minimize Lateness

#### Input
| Job | 1 | 2 | 3 | 4 |
|:------------------- | --- | --- | --- |:--- |
| Process Time$(t_i)$ | 3 | 5 | 3 | 2 |
| Deadline$(d_i)$ | 4 | 6 | 7 | 8 |

#### Output
返還 late job 中，結束時間超過 deadline 的**最大差距**

### Greedy idea
* Shortest-process-time-first

#### Input
| Job | 1 | 2 |
|:---------------------- |:--- | --- |
| Processing Time$(t_i)$ | 1 | 2 |
| Deadline$(d_i)$ | 10 | 2 |
#### Output

通過假設一組 Job 並套用 Shortest-process-time-first 可發現並非 OPT

* Earlest-deadline-first

#### Pseudocode

#### Proof
* 假設此演算法並非 OPT
* 若 OPT 將 $a_i$ 放置於 $a_j$ 之後，而 $d_i \le d_j$，將 $a_i$ 與 $a_j$ 交換可得 OPT'
* 轉換後的 maximum latness 必須為相同或更少 => $L(OPT') \le L(OPT)$

1. $L(OPT') \le L(OPT)$
2. $max(L(OPT', i), L(OPT', j)) \le max(L(OPT, i), L(OPT, j))$
* 因 $d_i \le d_j$，$L(OPT, j) \le L(OPT, i)$
3. $max(L(OPT', i), L(OPT', j)) \le L(OPT, i)$
* 因 $L(OPT, i) \ge L(OPT', i)$
4. $L(OPT', j) \le L(OPT, i)$
* 若 $a_j$ 是 early task
$L(OPT', j) = 0$，$L(OPT', j) \le L(OPT, i)$ **proofed**
* 若 $a_j$ 是 late task
$L(OPT', j)$
$= f(OPT', j) - d_j∴$ 因交換後結束時間$(f(n))$不變
$= f(OPT, i) - d_j$ $∴ d_i < d_j$
$\le f(OPT, i) - d_i$ $∴f(OPT, i) - d_i = L(OPT, i)$
$\le L(OPT, i)$ **proofed**


### Concluding Remarks
貪婪演算法套用時機：
1. 問題必須是 optimal substructure
2. 問題需僅有一個子問題（否則解法更貼近於 Divide and conquer）
3. 常用於 optimization problem

貪婪演算法證明：
1. Optimal substructure
2. Greedy choice property