###### tags: `ADA 8.3` `Task Scheduling`
# ADA 8.3: Task Scheduling

### Input
| Job | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| --------------- |:--- | --- | --- | --- | --- | --- | --- |
| Deadline$(d_i)$ | 1 | 2 | 3 | 4 | 4 | 4 | 6 |
| Penalty$(W_i)$ | 30 | 60 | 40 | 20 | 50 | 70 | 10 |

### Output
使超過 Deadline 的 Job 總和 Penalty 最小化

## Rethinking
#### 定義：
* late: a task which $f(H,i) > d_i$
* early: a task which $f(H,i) \le d_i$

將 late 搬移至最後的 $H'$ 的總 late Penalty 不變，因此可將問題變更為：
**如何選出 Penalty 最大的 early Penalty**


## Greedy idea
### Lagest-penalty-first
#### Proof
* 假設此演算法並非 OPT
* 若 OPT 中有 $a_i$ 且位於 $d_i$ 之後，將 early $a_j$ 與 $a_i$ 交換，得到 OPT'
* 因 $W_i \ge W_j$ , OPT' $\le$ OPT

#### Pseudocode
1. penalty 排序 *$O(nlog_n)$
2. 遍歷 job $i$ *$O(n)$
3. 找出 $d_i$ 內最靠後的 index $j$ *$O(n)?$
:::warning
worst case 下若 $d_i > n$ 複雜度為 $O(n)$ ，有較低複雜度作法？
若排序時將 deadline 加入排序使 $d_1 \le d_2...d_n$ 並由 0 ~ n 依次插入？
:::
4. 若 $j$ 存在 *$O(1)$
5. 紀錄 $i$ 為 early set
6. 將 $j$ 標記為已使用 *$O(1)$


### Earlest-deadline-first

#### Input
| Job | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| --------------- |:--- | --- | --- | --- | --- | --- | --- |
| Deadline$(d_i)$ | 1 | 2 | 3 | 4 | 4 | 4 | 6 |
| Penalty$(W_i)$ | 30 | 60 | 40 | 20 | 50 | 70 | 10 |

#### Output
##### 同 deadline 無視 penalty
| Schedule | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|:------------- | --- | --- | --- |:--- | --- | --- |:--- |
| Job index | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Total Penalty | 0 | 0 | 0 | 0 | 50 | 120 | 130 |

##### 同 deadline 高 penalty 優先
| Schedule | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|:------------- | --- | --- | --- |:--- | --- | --- |:--- |
| Job index | 1 | 2 | 3 | 6 | 5 | 4 | 7 |
| Total Penalty | 0 | 0 | 0 | 0 | 50 | 70 | 80 |

=> Earlest-deadline-first 非 OPT ?