動機
一組工作需要分配到若干部相同機器上,目標是令最後一項工作盡早完成。一個簡單的線上規則是:把每項到達的工作分配給當前負載最小的機器。該規則無需知道後續工作,但其最終完工時間始終不超過最優值的兩倍。
更精細的分析給出 部機器時的精確因子 ,並給出達到該因子的例子。證明的思路是找出最後完成的那項工作,並結合最優完工時間的兩個不同下界。
定義
定義 7.6.1
(排程實例與完工時間)
設 為相同機器的數目。共有 項工作,其處理時間為非負數 。工作按給定次序分配,並且是不可中斷的;每部機器依次處理分配給它的工作。機器的負載是其所有工作處理時間之和;完工時間(makespan)是最大負載。記 ,並記 為所有分配方案中可能的最小完工時間。對於空的工作列表,約定 。
定義 7.6.2
(列表排程)
列表排程(list scheduling)從所有負載為零開始。對於按次序到來的每項工作,把它分配給當前負載最小的一部機器,出現平手時任意選擇。該規則在作出決定時無需看到後續工作。若沒有工作,則返回空排程,其完工時間為零。
定理
定理 7.6.3
(列表排程的近似比)
對於每個輸入,
其中 是列表排程所產生的完工時間。
定理 7.6.4
(該因子的緊性)
對於每個整數 ,存在一個有序工作列表,使得列表排程的完工時間為 ,且與它如何在負載相同的機器之間處理平手無關。
若所有處理時間均為零,則保證式兩邊都為零。該結果以不等式的形式陳述,並不需要除以 。
證明
最優值的兩個下界
引理 7.6.5
(最優值的兩個下界)
對每個實例, 且 。
證明
(平均負載與最長工作)
每個分配方案的機器總負載都是 ,所以其最大負載至少為 。另外,包含工作 的機器必須完整處理該工作,所以其完工時間至少為 。因此
第一個下界是平均負載論證;第二個是單項工作論證。下面的證明同時需要這兩個下界。在此模型中,單項工作不能拆分到多部機器上。
分析最後完成的工作
證明
(把關鍵的開始時間記到較早的工作上)
假設至少有一項工作的處理時間為正,並選取一項在其所在機器上於最終完工時間完成的工作 。設 為工作 被分配之前該機器的負載。則 ;同一部機器上不可能還有之後的正長度工作,否則會超過最終完工時間。其後的零長度工作不改變該等式。
在分配 的時刻,列表排程選擇了一部負載最小的機器。因此每部機器的負載都至少為 。在 之前被分配的工作的總處理時間至少為 。由於 包含這些工作以及工作 ,
於是
最後一步分別應用了平均負載下界與單項工作下界。定理得證。該論證對零長度工作和任意平手處理方式都成立,因為它只使用了關鍵分配時刻的最小負載性質。
證明透視
把關鍵開始時間歸於先前的工作量
當最後完成的工作被放置時,所有機器已經至少具有它的開始負載。因此先前的工作合計至少貢獻了 的工作量。該工作自身的長度由最優值獨立地界定,與平均負載界無關。
關鍵工作不等式的含義
對具體例子而言,估計式 強於最終的近似因子。若關鍵工作相對於平均負載較小,則排程接近平均負載下界。若該工作較大,則最長工作下界補償其貢獻。兩個下界各自不必是緊的;它們對同一個未知的最優值都成立。
該證明是回顧式的:它在排程構造完成之後,才選取最後完成的工作。算法無需預測這項工作。當有多項工作在同一最大負載處完成時,選取其所在機器上正長度工作中最後的任意一項。它之前的負載與最小負載性質仍然給出該不等式。
同樣的推理適用於工作列表的每個前綴。若輸入在某次分配之後停止,就把該前綴視為一個完整例子,並把它的排程與該前綴的最優排程比較。因此該保證不依賴於事先知道工作的最終數目。該陳述針對的是在分配列表中線上揭示工作長度的情形;它並不對任意的實際釋出時間或依賴於機器的處理速度建模。
緊例子為何平衡
從相等的負載出發,把一項單位工作分配給負載最小的機器,會使其中一個最小負載增加一。每經過一組 項單位工作之後,每部機器的負載恰好增加一:在當前較小負載的所有機器都得到一項工作之前,已經增加過的機器負載較大,不會再次被選中。對 組作歸納,得到長工作之前的負載向量為 。這一論證與組內如何處理平手無關。
離線排程利用了對長工作的了解,為它單獨保留一部機器。由該工作給出的下界證明沒有任何排程能做到小於 的完工時間。結合所構造的離線排程,這就精確地確定了最優值,而不僅僅是其上界。因此列表排程的完工時間 證明了所聲稱的最壞情形比值。
匹配的下界例子
證明
(單位工作之後接一項長工作)
固定 。給列表排程 項單位長度工作,隨後是一項長度為 的工作。在這些單位工作之後,所有負載都是 :最小負載規則使機器均勻填充,且單位工作的數目是 的倍數。最後一項工作被分配到任意一部機器,使其負載升至 。
最優的離線排程把長度為 的工作單獨放在一部機器上,並把 項單位工作均勻分配到其餘 部機器上,每部 項。其完工時間為 。最長工作下界同樣給出 ,所以該排程是最優的。比值為 。
在這些單位工作之後,每一種平手處理方式都得到同樣平衡的負載向量,因此該例子證明的是所述規則本身的緊性,而不是某一種特定平手約定下的緊性。
複雜度與實現
以機器當前負載為鍵的最小優先佇列,可以透過取出負載最小的機器並以更新後的負載重新插入來支援每次分配。使用二元堆時,除了儲存輸出排程之外,這些分配需要 次比較以及 個機器條目。計入建立初始堆的 時間,總時間為 。
若 ,則把每項工作分配給不同的機器即為最優,其完工時間等於最長的處理時間。直接處理這種情形,可以避免當 以二進制給出且大於工作數目時分配大量的空機器記錄。對於非平凡情形 ,堆的大小受顯式工作數目所界定。精確的有理數處理時間需要精確的加法與比較;運算次數本身並不是完整的位元複雜度界。
該證明適用於所給定的工作次序。在列表排程之前對工作排序可以改進某些排程,但這會改變線上行為,並且對任何聲稱的更強因子都需要另行分析。此處的結果不假設輸入已排序。
反例模式
貪心排程可能不是最優的
在兩部機器上,依次處理工作 。兩項單位工作給出負載 ;隨後最後一項工作產生負載 。離線排程把長度為二的工作放在一部機器上,把兩項單位工作放在另一部機器上,完工時間為二。貪心的比值為 ,恰為 。
邊界約定與輸出
排程可以透過列出每部機器上按分配次序排列的工作來表示。當所有工作都可用時,讓每部機器的工作連續開始、沒有閒置時間,則所述負載就等於完成時間。在此模型中,刻意插入閒置時間不可能改善最大完成時間,所以負載表述刻劃了最優值。
零處理時間不造成任何困難。它們可以在不改變負載的情況下被分配,僅由零長度工作構成的例子其完工時間為零。證明在選取正的關鍵工作之前,先把該情形單獨分出。若 ,則因子恰為一,且工作量下界取等號。處理這些情形時,不應除以可能為零的最優值。
例題詳解
例題 7.6.6
(兩部機器)
對於工作長度 ,列表排程把 和 分配到不同的機器,然後把 分配到負載為 的機器。最終負載為 ,所以完工時間為三。由於 ,該排程是最優的。
例題 7.6.7
(一部機器)
當 時,每項工作都必須在唯一的機器上運行,所以列表排程與最優排程的完工時間都是 。因子 等於一。
例題 7.6.8
(三部機器的緊例子)
對於 ,給出六項單位工作,隨後是一項長度為三的工作。六項單位工作產生負載 ,最後的工作使其中一個負載變為五。最優方案把長工作單獨放置,並在其他每部機器上放三項單位工作,完工時間為三。比值為 。
例題 7.6.9
(機器多於工作)
對於處理時間 和五部機器,把兩項工作分配到不同的機器。完工時間為四,達到最長工作下界,因此是最優的。其他機器可以保持閒置。
常見錯誤
常見錯誤
(當前負載與最終負載)
接收關鍵工作的機器,在該工作被分配時具有最小的當前負載。它的最終負載不一定仍然最小。證明是把該開始時間歸於已經分配的工作量,再加上關鍵工作的長度。
常見錯誤
(單靠平均負載下界控制不了最後一項工作)
僅有不等式 不足以界定最後一項工作的貢獻。單項工作可能遠長於平均負載,因此單獨的下界 是必不可少的。
常見錯誤
(該規則並不需要最優值)
最後,該保證是把結果與知道全部工作的離線最優值作比較。列表規則本身不需要該最優值,也不需要未來工作的長度。離線算法在某個具體輸入上可能做得更好,這與近似界並不矛盾。
總結
列表排程把每項工作放到負載最小的機器上。在最後完成的工作被分配時,每部機器至少已累積了其開始負載。把這一工作量界與最長工作下界結合,即得 近似,而一列單位工作後接一項長工作的例子顯示該因子是緊的。
練習
快速檢查
(給出用總處理時間與單項工作表示的 的兩個一般下界。)
一個下界與平均有關,另一個與單一工作有關。
解答 · 答案
,因為最大負載至少是平均值;,因為工作不能被拆分到多部機器上。
快速檢查
(對工作 在兩部機器上運行列表排程,並與最優分配比較。)
逐項工作執行此規則,再試把兩項單位工作放在一起。
解答 · 答案
前兩項工作給出負載 ;最後一項工作產生 (機器名稱可互換)。把兩項單位工作放在一起,最優方案的負載為 ,所以比值為 。
快速檢查
(為甚麼當 時列表排程是最優的?)
工作分配到機器只有一種可能。
解答 · 答案
所有工作都必須分配給唯一的機器,每個排程的完工時間都是 。因此列表排程與最優值相等。
快速檢查
(對於 ,描述一個達到比值 的工作列表。)
回想緊例子:先是單位工作,最後是一項長工作。
解答 · 答案
使用六項長度為一的工作,隨後是一項長度為三的工作。列表排程得到的完工時間為五;把長工作單獨放置,並在其他每部機器上放三項單位工作,得到最優值三。