---
# System prepended metadata

title: 'ADA 8.4: Scheduling to Minimize Lateness'
tags: [Scheduling to Minimize Lateness, ADA 8.4]

---

###### 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 的**最大差距**
![maximum latness](https://i.imgur.com/NxJNv9p.png)

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

#### Input
| Job                    | 1   | 2   |
|:---------------------- |:--- | --- |
| Processing Time$(t_i)$ | 1   | 2   |
| Deadline$(d_i)$        | 10  | 2   |
#### Output
![Shortest-process-time-first](https://i.imgur.com/ojJjL91.png)

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

* Earlest-deadline-first 

#### Pseudocode
![Earlest-deadline-first](https://i.imgur.com/viLngpx.png)

#### 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**
	
![Shortest-process-time-first](https://i.imgur.com/HmllbJR.png)

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

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