job_scheduling.cpp

// job_scheduling.cpp
// -----------------------------------------------------------------
// Job Scheduling（等同機台排程，目標：最小化 makespan）
// P || Cmax 是 NP-Hard（m>=2 時，因為 Partition 可歸約過來）
//   1. List Scheduling（Graham 1966）：任意順序丟給最空的機器
//      保證 <= (2 - 1/m)·OPT
//   2. LPT（Longest Processing Time first）：先排序再 List
//      保證 <= (4/3 - 1/(3m))·OPT
//   3. 精確解：回溯 + 剪枝（小實例）
//
// Compile: g++ -std=c++17 -O2 -Wall -Wextra -o job_scheduling job_scheduling.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>

using namespace std;

struct Schedule {
    vector<vector<int>> machineJobs;   // 每台機器分到的工時清單
    int makespan = 0;
};

// ---------- 1. List Scheduling ----------
Schedule listScheduling(const vector<int>& jobs, int m) {
    Schedule s;
    s.machineJobs.assign(m, {});
    vector<int> load(m, 0);
    for (int p : jobs) {
        int target = min_element(load.begin(), load.end()) - load.begin();
        s.machineJobs[target].push_back(p);
        load[target] += p;
    }
    s.makespan = *max_element(load.begin(), load.end());
    return s;
}

// ---------- 2. LPT ----------
Schedule lptScheduling(vector<int> jobs, int m) {
    sort(jobs.begin(), jobs.end(), greater<int>());
    return listScheduling(jobs, m);
}

// ---------- 3. 精確解：回溯 ----------
class ExactScheduler {
    vector<int> jobs;
    int m, best;
public:
    long long nodes = 0;
    int solve(vector<int> js, int m_) {
        jobs = std::move(js);
        sort(jobs.begin(), jobs.end(), greater<int>());   // 大工作先放
        m = m_;
        best = lptScheduling(jobs, m).makespan;           // LPT 當初始上界
        nodes = 0;
        vector<int> load(m, 0);
        dfs(0, load);
        return best;
    }
private:
    void dfs(int idx, vector<int>& load) {
        ++nodes;
        int cur = *max_element(load.begin(), load.end());
        if (cur >= best) return;                          // 剪枝
        if (idx == (int)jobs.size()) {
            best = cur;
            return;
        }
        for (int k = 0; k < m; ++k) {
            // 對稱剪枝：負載相同的機器只試一台
            bool dup = false;
            for (int k2 = 0; k2 < k; ++k2)
                if (load[k2] == load[k]) { dup = true; break; }
            if (dup) continue;
            load[k] += jobs[idx];
            dfs(idx + 1, load);
            load[k] -= jobs[idx];
        }
    }
};

static int theoreticalLB(const vector<int>& jobs, int m) {
    int total = accumulate(jobs.begin(), jobs.end(), 0);
    int lb = (total + m - 1) / m;                          // 平均負載
    lb = max(lb, *max_element(jobs.begin(), jobs.end()));  // 最大單工
    return lb;
}

static void show(const string& tag, const Schedule& s) {
    cout << tag << ": makespan = " << s.makespan << "\n";
    for (int k = 0; k < (int)s.machineJobs.size(); ++k) {
        int sum = accumulate(s.machineJobs[k].begin(), s.machineJobs[k].end(), 0);
        cout << "  M" << k << " [";
        for (size_t i = 0; i < s.machineJobs[k].size(); ++i)
            cout << s.machineJobs[k][i]
                 << (i + 1 < s.machineJobs[k].size() ? "," : "");
        cout << "] load " << sum << "\n";
    }
}

int main() {
    // ---- 範例 1：Graham 的經典壞例（List 被到貨順序坑） ----
    cout << "=== Example 1: arrival order hurts list scheduling ===\n";
    // m=3。順序 {2,2,2,2,2,2,3,3,3} vs 排序後
    vector<int> a = {2, 2, 2, 2, 2, 3, 3, 3, 3};
    int m = 3;
    cout << "jobs {2,2,2,2,2,3,3,3,3}, machines = 3, lower bound = "
         << theoreticalLB(a, m) << "\n";
    show("List (as-is order)", listScheduling(a, m));
    show("LPT  (sorted)     ", lptScheduling(a, m));
    ExactScheduler ex;
    cout << "exact makespan = " << ex.solve(a, m) << "\n\n";

    // ---- 範例 2：LPT 的著名反例（達到 4/3 界） ----
    cout << "=== Example 2: LPT worst case (m=2) ===\n";
    // {3,3,2,2,2}: LPT -> 7, OPT -> 6, 比率 7/6
    vector<int> b = {3, 3, 2, 2, 2};
    cout << "jobs {3,3,2,2,2}, machines = 2\n";
    show("LPT", lptScheduling(b, 2));
    cout << "exact makespan = " << ex.solve(b, 2)
         << "  (LPT/OPT = 7/6, bound 4/3 - 1/6 = 7/6 —— tight!)\n\n";

    // ---- 範例 3：與 Partition 的關係 ----
    cout << "=== Example 3: scheduling on 2 machines IS partition ===\n";
    vector<int> c = {8, 6, 5, 14, 13, 9, 12, 7};   // 總和 74
    cout << "jobs sum = " << accumulate(c.begin(), c.end(), 0)
         << ", machines = 2, perfect split would give makespan 37\n";
    int opt = ex.solve(c, 2);
    cout << "exact makespan = " << opt
         << (opt == 37 ? "  -> a perfect partition exists!" : "") << "\n";
    show("LPT", lptScheduling(c, 2));
    cout << "\n";

    // ---- 範例 4：隨機統計——兩個近似的實際表現 ----
    cout << "=== Example 4: average quality over random instances ===\n";
    unsigned seed = 424242;
    auto nextRand = [&seed]() {
        seed = seed * 1103515245 + 12345;
        return (seed >> 16) & 0x7fff;
    };
    int trials = 100;
    double listSum = 0, lptSum = 0;
    int lptOptimal = 0;
    for (int t = 0; t < trials; ++t) {
        vector<int> jobs;
        for (int i = 0; i < 14; ++i) jobs.push_back(1 + nextRand() % 30);
        int mm = 4;
        int ls = listScheduling(jobs, mm).makespan;
        int lp = lptScheduling(jobs, mm).makespan;
        int op = ex.solve(jobs, mm);
        listSum += (double)ls / op;
        lptSum += (double)lp / op;
        if (lp == op) ++lptOptimal;
    }
    cout << trials << " random instances (14 jobs, p in 1..30, m=4):\n";
    cout << "avg List/OPT = " << listSum / trials
         << "  (guarantee " << 2.0 - 1.0 / 4 << ")\n";
    cout << "avg LPT /OPT = " << lptSum / trials
         << "  (guarantee " << 4.0 / 3 - 1.0 / 12 << ")\n";
    cout << "LPT hit the optimum " << lptOptimal << "/" << trials << " times\n";
    return 0;
}