多機調度問題：貪心算法實現最長處理時間優先策略（C語言完整代碼）

問題描述

給定 n 個獨立作業，需由 m 台相同機器並行處理。作業 i 的處理時間為 t[i]。任一作業可在任一機器上執行，但一旦開始不得中斷，亦不可拆分。目標是尋找一種調度方案，使所有作業在盡可能短的時間內完成（即最小化 makespan）。

算法分析：最長處理時間優先（LPT）貪心策略

針對此 NP-hard 問題，採用 最長處理時間作業優先（Longest Processing Time First, LPT） 的貪心策略可獲得較好的近似解。核心思想是：

1. 將所有作業按處理時間由大到小排序。
2. 依序取出作業，每次將其分配給當前總負載最小的機器。
3. 若機器數 ≥ 作業數（m ≥ n），則每台機器最多分一個作業，總耗時即為最長作業時間。
4. 若機器數 < 作業數（m < n），則需反覆執行「找最閒機器 → 分配作業 → 更新負載」的過程。

範例演示

假設 7 個作業處理時間為 {2, 14, 4, 16, 6, 5, 3}，3 台機器（M1, M2, M3）。排序後為 {16, 14, 6, 5, 4, 3, 2}。調度過程如下圖所示，最終總加工時間為 17。

C 語言完整實現

[cpp]
#include <stdio.h>
#include <stdlib.h>

#define N 7  // 作業數
#define M 3  // 機器數

int machine_load[M] = {0};  // 記錄每台機器已分配的總耗時

// 取陣列最大值
int get_max(int arr[], int len) {
    int max_val = arr[0];
    for (int i = 1; i < len; i++)
        if (arr[i] > max_val) max_val = arr[i];
    return max_val;
}

// 取陣列最小值的索引
int get_min_index(int arr[], int len) {
    int min_idx = 0;
    for (int i = 1; i < len; i++)
        if (arr[i] < arr[min_idx]) min_idx = i;
    return min_idx;
}

// 機器數 >= 作業數：每台機器分一個作業
int schedule_few_jobs(int jobs[], int n) {
    for (int i = 0; i < n; i++) machine_load[i] = jobs[i];
    return get_max(machine_load, n);
}

// 機器數 < 作業數：貪心分配
int schedule_many_jobs(int jobs[], int n) {
    for (int i = 0; i < n; i++) {
        int idx = get_min_index(machine_load, M);
        printf("作業 %d (耗時 %d) → 機器 %d (當前負載 %d)\n", i, jobs[i], idx, machine_load[idx]);
        machine_load[idx] += jobs[i];
    }
    return get_max(machine_load, M);
}

int main(void) {
    // 已按降序排列
    int jobs[N] = {16, 14, 6, 5, 4, 3, 2};
    int makespan = 0;

    if (M >= N)
        makespan = schedule_few_jobs(jobs, N);
    else
        makespan = schedule_many_jobs(jobs, N);

    printf("\n最短總完工時間（makespan）：%d\n", makespan);
    system("pause");
    return 0;
}

關鍵點總結

• 時間複雜度：排序 O(n log n) + 分配 O(n log m)（若用最小堆優化）或 O(n·m)（線性掃描）。
• 近似比：LPT 算法的最壞情況近似比為 4/3 - 1/(3m)，實際表現通常更優。
• 工程應用：適用於任務調度、負載均衡、雲計算資源分配等場景。