POJ 2751 雙機調度 Johnson 算法：貪心策略最小化完工時間

Johnson 算法規則

1. 將任務分為兩組：
   　Group A：t1_i ≤ t2_i（M1 時間較短）
   　Group B：t1_i > t2_i（M2 時間較短）
2. Group A 按 t1_i **非遞減**排序（短任務優先）。
3. Group B 按 t2_i **非遞增**排序（長任務優先）。
4. 最終順序：Group A 接 Group B。

直觀證明

相鄰交換論證：對任意相鄰任務 i, j，若違反上述規則則交換後不劣。完整證明見《調度理論》教材。

代碼實現

struct Task { int t1, t2; };
bool cmpA(Task a, Task b) { return a.t1 < b.t1; }
bool cmpB(Task a, Task b) { return a.t2 > b.t2; }

int main() {
    int n; while (cin >> n, n) {
        vector A, B;
        for (int i=0;i>t1>>t2;
            if (t1 <= t2) A.push_back({t1,t2});
            else B.push_back({t1,t2});
        }
        sort(A.begin(), A.end(), cmpA);
        sort(B.begin(), B.end(), cmpB);
        vector seq = A; seq.insert(seq.end(), B.begin(), B.end());
        int t1_end = 0, makespan = 0;
        for (auto& t : seq) {
            t1_end += t.t1;
            makespan = max(makespan, t1_end) + t.t2;
        }
        cout << makespan << "\n";
    }
}

複雜度

排序 O(n log n)，模擬 O(n)。n ≤ 10000 輕鬆通過。

擴展：三機器及以上

三機器問題已證為 NP-hard，無多項式精確算法，需啟發式或近似算法。