Single Machine Scheduling - Minimizing Number of Tardy Jobs

這裡介紹如果一系列工作有著不同的Due date跟Process Time。

因為我懶得附圖跟例子所以大家可以參考演算法筆記的工作排程問題(其實他也講得很詳細，只是如果有人不懂為什麼他那樣可以保證新加入的工作不會超時可以繼續讀下去)。

那麼要如何排序才能讓我們的Tardy Job最少(超時的工作最少，也就是在期限內完成最多工作)
首先將所有工作依照Earliest Due Date (EDD)做排序，然後從Due Date最早的工作開始加入行程。
一旦新加入的工作無法在期限內完成，就砍掉行程中最耗時的工作。
如此一來最後得到的結果就是完成最多工作的情況。
證明；
假設當前的狀態沒有任何超時，在加入新工作時可以分為兩種情況

1. 沒超時，工作量+1
2. 超時，剔除耗時最大的工作，加入這個新工作。工作量+1-1維持不變，但是因為剔掉了耗時最大的工作使得總工作時間變短，未來加入的工作將更不易超時。

這裡有人可能會有一個疑問就是，怎麼確保當我們砍掉耗時最大的工作時，新加入的工作一定不會過期?
重點在於，所有的工作是照著EDD做排序的!!!!
假設新加入的工作X是最耗時的工作，那麼他就被砍掉不加入，所以不影響。
假設新加入的工作X不是最耗時的工作，也就是說有一個工作L耗時更大 => PL > PX
因為 PL在所有工作裡面  而這一系列的工作沒有超時。因此當一系列的工作砍掉長度較長的L後，再加入長度較短的X，一定也不會超出原本的期限Deadline1。而X的期限DeadlineX因為照著EDD做排序，所以會在Deadline1之後，所以這樣操作一定可以保證X會在期限內完成。