動機
區間排程把每項活動的開始與結束時刻作為輸入。另一類問題則要求完成所有工作,並容許我們決定它們甚麼時候開始。一台機器同一時刻只能處理一項工作。把某項工作放在前面會幫助它,卻會推遲後面所有工作。因此,最好的次序取決於這些延遲究竟如何計入目標。
兩個常見目標會導出不同的貪心規則。為了控制相對於到期日的最大延誤,應先處理到期日較早的工作。為了最小化加權完成時間之和,應比較處理時間與權重的比值。這裏更值得掌握的是規則的發現與證明方法:固定其餘安排,只比較兩項相鄰工作的次序。
定義
定義 2.6.1
(工作、排程與延誤)
有 項工作。工作 的處理時間為 ,到期日為 ;討論加權目標時,還給定權重 。所有工作從時刻零起就可處理。可行排程為每項工作指定開始時刻 ,使區間 兩兩不重疊。處理是不可搶佔的:工作一旦開始,就連續運行至完成。記
定義 2.6.2
(目標:最大延誤與加權完成時間)
是完成時間, 是延誤, 是拖期。延誤容許為負,表示提前完成;拖期只計算超過到期日的部分。我們分別研究
所有權重取一時,後者就是完成時間之和。空輸入可直接返回空排程,加權代價為零;下面關於最大延誤的結論只針對非空輸入,以確保最大值有定義。
為甚麼可以先消除閒置
對任意可行排程,保持工作的先後次序,讓第一項從時刻零開始,以後每項緊接前一項開始。每項工作的開始和完成都不會比原來晚。所有工作在零時刻已經可用,因此這樣左移仍然可行。各項延誤不會增加;由於權重非負,各項 也不會增加。
所以只需考慮沒有閒置的排程。這樣的排程完全由工作排列 決定,而且
排列只有有限多個,故兩個目標都能取得最小值。這一步既證明最優解存在,也消除了不必要的開始時間決策。如果某項工作要等到較晚才釋出,左移便可能不合法。
定理
定理 2.6.3
(按最早到期日排序最小化最大延誤)
在上述單機、全部工作從零時刻可用、不可搶佔的假設下,任何按到期日非遞減次序執行且沒有閒置的排程,都在所有可行排程中最小化 。到期日相同時可任意排序。同一排程也最小化最大拖期 。
定理 2.6.4
(處理時間與權重之比的排序規則)
在相同假設下,先將正權重工作按 非遞減排序,再任意排列零權重工作,連續執行所得排程最小化 。正比值相同時可任意排序。特別地,按處理時間從短到長執行,能最小化無權的完成時間之和。
這些結論給出最優排程的充分條件,並不聲稱每個最優排程都必須具有上述次序。有些逆序交換不會改變目標,零權重還可能產生更多並列最優解。
證明:交換到期日逆序
證明
(交換到期日逆序)
設兩項相鄰工作原本依次為 ,且 。令這段兩工作區間從時刻 開始。交換前,它們的完成時間為 和 ;交換後, 在 完成, 在 完成。
兩項工作的總處理時間不變,所以其他工作的完成時間不受影響。變化的兩項滿足
以及
兩個新延誤都不超過某個舊延誤,因此這對工作的新最大延誤不超過舊最大延誤。加上未變化的其他工作,整個排程的 不會增加。
從一個最優的無閒置排程出發,反覆交換相鄰的到期日逆序。每次嚴格逆序交換都會減少逆序對數,有限次後得到到期日有序的排程,而且仍然最優。若到期日相同,兩種次序的最大延誤都由該工作對的最後完成時間決定,因此任意交換都不影響結論。
對非空有限工作集,
右邊隨 非遞減,故最早到期日排程也最小化最大拖期。反過來未必成立:多個排程可能都提前完成所有工作,從而最大拖期全為零,但它們的負最大延誤仍可不同。
證明透視
哪個舊工作能同時控制兩個新延誤?
在到期日逆序中, 的到期日較早,卻排在後面。把它移到前面會提前完成;把 移到後面,只讓它取得這對工作原來的最後完成時間,而它的到期日又比 晚。因此, 原來的延誤同時控制兩個新延誤。只說「較早到期的工作更緊急」,並沒有給出這個定量比較。
證明:加權目標的兩工作差值
證明
(加權目標的兩工作差值)
仍比較從 開始的相鄰工作 。其餘目標項不變,而這兩項在不同次序下的貢獻之差為
兩權重都正時,把 放在 前面不更差,當且僅當 。開始時刻完全消去,所以這項偏好不依賴這對工作處於排程的哪個位置。交換相鄰的比值逆序,便能在不增加代價的情況下排好所有正權重工作。
如果 而 ,差值為 。把 移到前面會嚴格降低代價:零權重工作自身何時完成不收費,但它佔用機器會推遲需要收費的工作。不斷交換這樣的逆序,就把零權重工作移到最後。兩個零權重工作的貢獻在兩種次序下都為零。由此可把任意最優無閒置排程變成定理所述次序。正比值相等時差值為零,說明並列可任意處理。
權重全為一時,差值化為 ,所以短工作優先最優。還可以寫成
較早工作的處理時間會反覆計入許多完成時間。短工作優先把較大的重複次數分配給較小的處理時間;交換證明使這一直覺成為嚴格論證。
概念視角組合
加權成本的逐對描述
把 寫成工作 本身及排在它前面所有工作的處理時間之和,便得到 ,其中 表示 排在 之前。第一個和與次序無關。每一對無序工作 ,若 在前則貢獻 ,若 在前則貢獻 ,所以成本是每對工作各出一項的和。互換兩項相鄰工作只改變其中一對,因此交換差值是 ,比值檢驗也就是逐對的比較。
例題
例題 2.6.5
(到期日次序與另一個目標)
令 的 分別為 、、。最早到期日次序為 ,完成時間為 ,延誤為 ,所以 。最短處理時間次序 的完成時間為 ,延誤為 ,最大延誤反而為二。
若最小化加權完成時間,比值次序則為 ,對應 。完成時間為 ,故 。到期日次序的加權代價卻為 。同一次序可以對一個目標最優,卻對另一個目標明顯較差。
例題 2.6.6
(相同比值與零權重)
工作 的 分別為 、、。正比值均為 。次序 的加權代價為 ,次序 也給出 。若把 放在最前,次序 的代價增至 。零權重並不表示它推遲其他工作時沒有影響。
例題 2.6.7
(最大延誤不是總拖期)
取 的 , 的 。最早到期日次序 的延誤為九和九,最大延誤為九,總拖期為十八。次序 的延誤為 和十,最大延誤更差,但總拖期只有十。最大延誤定理並不保證拖期之和最小。
例題 2.6.8
(釋出時間為甚麼改變問題)
設 在零時刻可用,處理需四單位,到期日為一百。 在時刻一才釋出,處理需一單位,到期日為二。立即運行當前可用的 ,會讓 在時刻五完成,最大延誤為三。若主動閒置到時刻一,先把 做到時刻二,再把 做到時刻六,最大延誤便為零。消除閒置的論證不適用於這個釋出時間模型,上面的證明也就不能直接沿用。
實作與代價
兩種規則都先排序,再用一次前綴和掃描計算完成時間。共需 次比較和 次算術運算,包括求目標值。儲存工作次序、完成時間及目標值需 個字;排序實作另外需要的工作空間仍須計入。
正權重時,偏好 等價於 ,可避免近似除法的捨入問題。實際排序比較器應使用嚴格判斷 ,相等時再按固定且唯一的工作編號打破並列;直接使用非嚴格比較並不是合法的嚴格排序比較器。零權重必須單獨處理,不能除以零。只有數值模型支援時,精確比較與算術才能視為單位代價。若整數輸入各至多有 位,交叉乘積可需 位,累積完成時間可需 位。因此,對任意大整數,字操作界並不是常數位操作代價的聲明。
常見錯誤
反例模式
貪心規則必須對應一個目標
斷言:既然最早到期日對最大延誤最優,同一次序也使加權完成時間之和最小。取第一個例題的三項工作, 分別為 、 和 。到期日次序 的完成時間為 ,成本 ;但次序 的完成時間為 ,成本只有 。反過來,最短處理時間優先的次序 的最大延誤為 ,而到期日次序的最大延誤為 。修正方法是先說明目標:每個目標都有各自的交換不等式,一條規則只對它的兩工作差值所排序的那個目標成立。
常見錯誤
(要求每項工作都變好)
相鄰交換不必讓每項工作都更好。在到期日證明裏,一項工作交換後完成得更晚,但它的新延誤仍被舊的最壞延誤控制。在加權證明裏,一項貢獻可以增加,只要另一項減少的量至少一樣大。把整體改善誤認為逐項改善,會排除證明所需的關鍵交換。
常見錯誤
(在模型之外套用同一規則)
假設也不能省略。釋出時間可能令左移不可行,先後依賴約束可能令交換非法,多台機器則會改變可行排程集合。只照搬相同的排序規則,並不能處理這些不同模型。
最早到期日與最短處理時間在一般情形下都不能取勝,而且問題是 NP 困難的。
自然延伸的下一個問題
總拖期有交換規則嗎?
最早到期日與最短處理時間在一般情形下都不能取勝,而且問題是 NP 困難的。
對總拖期 ,工作 偏向最短優先:總拖期為 ,按到期日排則為 。工作 則偏向按到期日排: 對 。最小化 是 NP 困難的,不過存在偽多項式的動態規劃,所以不能指望用成對交換規則解決它。
小結
在全部工作從零時刻可用的單機問題中,消除閒置把排程化為排列。交換到期日逆序不會增加工作對的最壞延誤;加權目標的差值 則導出比值次序。反覆進行相鄰交換能到達有序排列,同時保持可行且不惡化指定目標,從而得到全局最優性證明。
練習
快速檢查
( 的 分別為 。求一個最早到期日次序、各完成時間及 。)
按到期日排序,再累加處理時間。
解答 · 答案
到期日次序為 ,完成時間為 ,延誤為 ,故 。定理保證此值最小;短工作不一定先做。
快速檢查
( 的 分別為 。求加權完成時間最小的次序及目標值。)
計算正權重工作的 ,並把零權重工作放在最後。
解答 · 答案
的正比值為 , 的為二,故取 。完成時間為 ,加權和為 。
快速檢查
(數出每項處理時間出現多少次,證明無權完成時間之和的公式。)
數一數每個處理時間出現在多少個完成時間中。
解答 · 答案
出現在第 項完成時間中,共 次。交換兩個有限求和的次序即得公式。
快速檢查
(說明最大拖期最小的排程為甚麼未必令最大延誤最小。給出兩項到期日充裕的工作,並解釋為甚麼在無閒置排程中,把它們的到期日設為相同不能構成這種反例。)
試取足夠大的到期日,使每項工作都提前完成。
解答 · 答案
給一單位工作到期日十,三單位工作到期日二十。短工作優先的延誤為 ,最大值為 ;長工作優先的延誤為 ,最大值為 。兩者最大拖期都為零。若到期日同為 ,任何無閒置次序中,最後工作的延誤最大且均為 ,就無法這樣區分兩個目標。
快速檢查
(加權排程中,相鄰正權重工作 滿足 。不論這段何時開始,交換次序會使目標減少多少?)
使用兩工作差值 。
解答 · 答案
原目標減新目標為 。周圍工作與開始時刻均消去,目標減少十四。
快速檢查
(增加必須先做 再做 的約束,其中 、。準確指出比值排序證明在哪一步不能用於這個模型。)
先看比值規則偏好哪個次序,再檢查它是否可行。
解答 · 答案
比值規則希望 在 前,因為 ,但這個次序違反依賴約束。證明中的交換不再是可行操作;本例只有 這個合法次序。比較兩個目標值的公式,並不能保證兩個候選次序都合法。