\(n\) 個工作分給 \(m\) 台機器、最晚完工時間最短：近似演算法理論的誕生地（Graham 1966）

\(n\) 個工作，第 \(j\) 個需時 \(p_j\)；\(m\) 台相同機器，每台一次做一個工作、不可中斷。目標：分配工作使 makespan（最晚完工的機器的完工時間）\(C_{\max}\) 最小。\(m\geq 2\) 即 NP-Hard：\(m=2\) 就是 Partition（兩堆越平均 makespan 越小）。

廚房有 4 個爐子、14 道菜，每道菜火候時間不同。客人只在乎最後一道菜什麼時候出。怎麼分爐子？——這就是 makespan 排程，資料中心把批次任務丟給伺服器叢集時解的正是同一題。

兩個下界

任何排法都不可能低於： \[C_{\max} \;\geq\; \max\Bigl(\underbrace{\tfrac{1}{m}\textstyle\sum_j p_j}_{\text{平均負載}},\ \underbrace{\max_j p_j}_{\text{最長單一工作}}\Bigr)\]

演算法一：List Scheduling（Graham 1966）

規則

照任意順序把工作一個個丟給目前最空的機器。\(O(n\log m)\)、線上可用（工作到了就分派，不用預知未來）。

\(LS \leq \bigl(2 - \tfrac{1}{m}\bigr)\,OPT\)。

Proof. 設最後完工的機器上、最後放進去的工作是 \(j\)，它在時刻 \(s\) 開始。\(s\) 之前所有機器都忙（否則 \(j\) 會被丟去更空的機器），故 \(s \leq \frac{1}{m}\sum_{i\neq j} p_i\)。於是 \[C_{\max} = s + p_j \;\leq\; \frac{\sum_i p_i}{m} + \Bigl(1-\frac1m\Bigr)p_j \;\leq\; OPT + \Bigl(1-\frac1m\Bigr)OPT .\] 兩項分別用了上面的兩個下界。這是史上第一個帶證明的近似比，近似演算法這個領域由此開張。 ◻

弱點

到貨順序可以很壞：一堆小工作先來把機器墊得參差不齊，最後來一個大工作就慘了。

演算法二：LPT（Longest Processing Time first）

規則

先把工作由長到短排序，再跑 List Scheduling。直覺同 FFD：大石頭先放，沙子後撒。

\(LPT \leq \bigl(\tfrac43 - \tfrac{1}{3m}\bigr)\,OPT\)，且此界緊。

手算範例：緊例（\(m=2\)）

工作 \(\{3,3,2,2,2\}\)（總和 12，\(OPT = 6\)：如 \(\{3,3\}\) 和 \(\{2,2,2\}\)）。LPT 過程：

步驟 分派 M0 負載 M1 負載
3 \(\to\) M0 3 0
3 \(\to\) M1 3 3
2 \(\to\) M0（同載取編號小） 5 3
2 \(\to\) M1 5 5
2 \(\to\) M0 7 5

\(LPT = 7\)、\(OPT = 6\)，比率 \(7/6\) 恰等於 \(\frac43 - \frac{1}{3\cdot2}\)——理論界在五個小數字上就被打滿。

精確解：回溯 + 剪枝

小實例可回溯枚舉「每個工作放哪台」，三個剪枝讓它實用：(1) 工作先由大到小排（大工作的選擇最受限，先定）；(2) 對稱剪枝——負載相同的機器只試一台（機器可交換）；(3) 目前最大負載 \(\geq\) 已知最佳即砍，且用 LPT 當初始上界。本篇程式以此為 100 個隨機實例提供標準答案。

完整 C++ 程式

包含：List Scheduling、LPT、回溯精確解（LPT 上界 + 對稱剪枝）、下界計算、LPT 緊例、與 Partition 的關係展示、100 實例統計。編譯：

g++ -std=c++17 -O2 -Wall -Wextra -o job_scheduling job_scheduling.cpp

執行結果與解讀

=== Example 2: LPT worst case (m=2) ===
jobs {3,3,2,2,2}, machines = 2
LPT: makespan = 7    M0 [3,2,2] load 7 | M1 [3,2] load 5
exact makespan = 6   (LPT/OPT = 7/6, bound 4/3 - 1/6 = 7/6 -- tight!)

=== Example 3: scheduling on 2 machines IS partition ===
jobs sum = 74, machines = 2, perfect split would give makespan 37
exact makespan = 37  -> a perfect partition exists!
LPT: makespan = 37   M0 [14,9,8,6] load 37 | M1 [13,12,7,5] load 37

=== Example 4: average quality over random instances ===
100 random instances (14 jobs, p in 1..30, m=4):
avg List/OPT = 1.152  (guarantee 1.75)
avg LPT /OPT = 1.028  (guarantee 1.25)
LPT hit the optimum 34/100 times

Example 3 把「\(m=2\) 排程 = Partition」演給你看：總和 74 的八個工作恰好能對半分（37/37），LPT 這次也找到了完美分割。Example 4 的統計則是兩代演算法的成績單：排序這一步把平均誤差從 15% 壓到 3%，成本只是一次 \(O(n\log n)\)——在丟給貪心之前先排序，是排程界最划算的一行程式碼。

實務應用

  • 資料中心：MapReduce/Spark 把 task 分給 worker、K8s 的 Pod 調度——都是 makespan 的變形（真實版還帶資料親和性、搶佔等約束）。

  • 建置系統：CI 把測試分片到 \(m\) 台 runner，最慢的分片決定整條 pipeline 的時間——LPT 是最常用的分片策略。

  • 製造業：注塑機、CNC 的批次生產排程。

  • 多核心運算：OpenMP 的 schedule(dynamic) 本質是線上 List Scheduling；static 對均勻工作更好——理解本篇就理解了這個選項該怎麼選。

  • 理論意義：這是近似演算法理論的誕生地；後續有 PTAS（Hochbaum–Shmoys 1987）：任給 \(\varepsilon\)，可 \((1+\varepsilon)\) 近似，時間 \(O\bigl((n/\varepsilon)^{1/\varepsilon^2}\bigr)\) 級——多項式但 \(\varepsilon\) 小時天文數字，實務仍用 LPT。

練習題

  1. 手算：工作 \(\{5,4,3,3,2,2,1\}\)、\(m=3\)，分別跑 List（原順序）與 LPT，對照下界。

  2. 構造 \(m=3\) 的 LPT 緊例（提示：\(\{5,5,4,4,3,3,3\}\) 附近找，目標比率 \(4/3 - 1/9 = 11/9\)）。

  3. 把精確解的剪枝逐一關掉（不排序／不對稱剪枝／不用 LPT 上界），實測節點數各膨脹多少。

  4. 實作 Multifit（二分猜 makespan + FFD 裝箱驗證）——排程與裝箱的美妙互換，保證 \(1.22\,OPT\)。

  5. 挑戰：非等速機器（\(Q \parallel C_{\max}\)，每台有速度 \(s_i\)）——修改 LPT 使其分給「完工時刻最早」的機器，實測品質。

小結

方法 時間 保證 適用時機
List Scheduling \(O(n\log m)\) \((2-\frac1m)OPT\) 線上、工作陸續到達
LPT \(O(n\log n)\) \((\frac43-\frac{1}{3m})OPT\) 離線標準解
Multifit \(O(n\log n\log P)\) \(1.22\,OPT\) 要更緊的保證
回溯精確 指數 精確 \(n\lesssim 20\)
PTAS 多項式（巨大） \((1+\varepsilon)OPT\) 理論

延伸閱讀：Graham (1966, 1969) 兩篇開山之作；Hochbaum & Shmoys (1987) PTAS；Coffman, Garey & Johnson (1978) Multifit 分析。