最小化遲到的排程（minimize lateness）

你有一台機器和一串工作，每個工作需要一些處理時間且各帶一個期限。你一個接一個地執行工作，中間沒有空檔。在期限之後才完成的工作就「遲到」，遲到量是它超出的時間；整個排程的遲到量是最嚴重的那一次超出。目標是排列工作的順序，使那個最大遲到量盡可能小。

貪婪規則簡單得令人愉快，且完全忽略處理時間：把工作依期限排序，最早期限優先，並依此順序接連執行。這稱為最早期限優先（EDF）。證明是教科書式的交換論證。定義逆序為一對期限順序顛倒的工作——期限較晚者排在期限較早者之前。主張：交換相鄰的逆序對絕不增加最大遲到量。被移到前面的工作只可能更早完成（對它有利），而被移到後面的工作現在於「這對工作原本整體完成的時刻」完成，但它有較早的期限，故其遲到量被另一工作原本的遲到量所界。反覆消除相鄰逆序，可把任何最佳排程變成依期限排序者而從不增加遲到量，故 EDF 最佳。追蹤工作 (時間, 期限) = (1,2),(2,4),(3,3)：依期限順序 (1,2),(3,3),(2,4) 於 1,4,6 完成，遲到量為 0,1,2——最大 2；其他順序不會更好。

最早期限優先是排程理論與即時系統中的基礎結果。富啟發性的意外是處理時間根本不進入排序——只有期限進入——在交換論證說服你之前，這感覺是錯的。提醒：這條規則對「單機、所有工作於時刻零皆可用、最小化最大遲到量」是最佳的。若改變目標（例如總延誤量，或遲到工作數），或允許不同的可用時間，可能需要不同規則，甚至動態規劃。