\(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 timesExample 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。
練習題
手算：工作 \(\{5,4,3,3,2,2,1\}\)、\(m=3\)，分別跑 List（原順序）與 LPT，對照下界。
構造 \(m=3\) 的 LPT 緊例（提示：\(\{5,5,4,4,3,3,3\}\) 附近找，目標比率 \(4/3 - 1/9 = 11/9\)）。
把精確解的剪枝逐一關掉（不排序／不對稱剪枝／不用 LPT 上界），實測節點數各膨脹多少。
實作 Multifit（二分猜 makespan + FFD 裝箱驗證）——排程與裝箱的美妙互換，保證 \(1.22\,OPT\)。
挑戰：非等速機器（\(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 分析。