---
# System prepended metadata

title: 'ADA 8.3: Task Scheduling'
tags: [ADA 8.3, Task Scheduling]

---

###### 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 最小化
![Minimized Tasks](https://i.imgur.com/lfy0bci.png)

## 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**

![early first](https://i.imgur.com/pHw85kA.png)	

## Greedy idea
### Lagest-penalty-first
#### Proof
* 假設此演算法並非 OPT
	* 若 OPT 中有 $a_i$ 且位於 $d_i$ 之後，將 early $a_j$ 與 $a_i$ 交換，得到 OPT'
![Largest-penalty](https://i.imgur.com/U4uJ01Z.png)
* 因 $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)$

![pseudocode](https://i.imgur.com/AXkIwV5.png)

### 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 ?