企业官网建设流程全解析

前言

多机调度问题（multiprocessor scheduling）的经典形式是：有n个作业和m台相同的机器，每个作业有一个处理时间，作业不可拆分、一旦开始就在某台机器上连续执行到结束，目标是最小化全部作业完成的时间，也就是最大完工时间（makespan）。这个问题在m >= 2时是 NP 难的，不存在已知的多项式时间精确算法。因此工程上普遍使用贪心近似：按某种规则给作业排序，再依次把作业放到当前负载最小的机器上。

最常见的误解有两个。第一，以为「每次挑当前最长的作业放到最空的机器」一定得到最优解。它只是一个有理论保证的近似算法，叫 LPT（longest processing time first），保证结果不超过最优解的4/3 - 1/(3m)倍，并不保证等于最优。第二，把贪心规则记反，按处理时间从短到长排序（SPT），那个顺序是为「最小化平均完成时间」服务的，用在最大完工时间上效果会明显变差。

本文讲清问题的难度来源、LPT 规则为什么合理、如何用std::priority_queue维护最小负载机器，并给出一份可直接改写复用的完整实现。所有复杂度结论按标准库容器与算法的约定分析，不给出任何未经测量的耗时数字。

一、为什么精确求解很难

把m台机器看成m个桶，把作业看成带重量的球，目标是把球分进桶里，使最重的桶尽量轻。这正是划分问题（partition problem）的多桶推广，而两机情形已经包含划分问题作为特例，后者是经典的 NP 完全问题。因此除非P = NP，否则不存在对所有输入都快速且精确的算法。

精确算法在实践中只有几类：作业数很小时用状态压缩动态规划或分支限界；m = 2时用伪多项式时间的子集和动态规划；作业数中等时用整数规划求解器。这些方法都超出了「贪心」的范围。理解这一点很重要：贪心的价值在于快速得到一个不错的可行解，而不是求最优。

二、LPT 规则与它的保证

LPT 的步骤只有两步：把所有作业按处理时间从大到小排序；依次取出作业，分配给当前累计负载最小的机器。直观理由是，长作业决定了最终的最大值，先安排它们可以避免「最后剩一个超长作业，只能堆在已经满载的机器上」的糟糕局面。

这个算法有一个被证明的近似比：设最优解的最大完工时间为OPT，LPT 得到的为LPT，则LPT <= (4/3 - 1/(3m)) * OPT。这是算法教科书里的经典定理，不是实验统计值。作为对比，如果完全不排序、按输入顺序把作业丢给最空的机器（list scheduling），保证是2 - 1/m倍。两者都是上界，实际差距可能远小于上界，也可能刚好取到上界附近的构造实例。

需要强调：近似比是「最坏情况」的保证，不能反过来理解为「通常只差多少个百分点」。写文档时不要把它说成平均误差。

三、用最小堆维护机器负载

每台机器只需要记录两个量：编号和当前累计负载。每一步要取出负载最小的那台，因此用最小堆。C++ 的std::priority_queue默认是最大堆，要得到最小堆，需要显式传入比较器std::greater，并且把元素类型写成std::pair<long long, int>。std::pair的比较是先比first再比second，正好符合「负载相同时按编号稳定取一台」的需求。

堆里始终保留m个元素，每分配一个作业就弹出一台、更新负载、再压回去。单个作业的处理是 O(log m)，总体是 O(n log n + n log m)，其中 O(n log n) 来自排序。累计负载用long long，避免多个较大的int相加溢出——有符号整数溢出是未定义行为（undefined behavior, UB），不是「回绕成负数」这么温和。

四、完整示例

下面的实现返回每台机器分到的作业下标与最终负载，并给出最大完工时间。作业时长为 0 是允许的，负值属于调用方错误，用异常拒绝。

// 适用于 C++17
#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <queue>
#include <stdexcept>
#include <vector>

struct Schedule {
std::vector<std::vector<int>> jobs; // 每台机器上的作业下标
std::vector<long long> load; // 每台机器的累计负载

long long makespan() const {
if (load.empty()) {
return 0;
}
return *std::max_element(load.begin(), load.end());
}
};

// duration[i] 是第 i 个作业的处理时间，m 是机器数
Schedule lptSchedule(const std::vector<long long>& duration, int m) {
if (m <= 0) {
throw std::invalid_argument("machine count must be positive");
}
for (long long d : duration) {
if (d < 0) {
throw std::invalid_argument("negative job duration");
}
}

Schedule result;
result.jobs.resize(static_cast<std::size_t>(m));
result.load.assign(static_cast<std::size_t>(m), 0);

std::vector<int> order(duration.size());
std::iota(order.begin(), order.end(), 0);
// 按处理时间降序；相等时不关心先后，比较器仍是严格弱序
std::sort(order.begin(), order.end(), [&duration](int a, int b) {
return duration[a] > duration[b];
});

using Item = std::pair<long long, int>; // (负载, 机器编号)
std::priority_queue<Item, std::vector<Item>, std::greater<Item>> heap;
for (int i = 0; i < m; ++i) {
heap.push(Item{0, i});
}

for (int id : order) {
Item top = heap.top();
heap.pop();
int machine = top.second;
result.jobs[static_cast<std::size_t>(machine)].push_back(id);
result.load[static_cast<std::size_t>(machine)] += duration[id];
heap.push(Item{result.load[static_cast<std::size_t>(machine)], machine});
}
return result;
}

int main() {
std::vector<long long> duration{7, 5, 4, 3, 2, 2, 1};
Schedule s = lptSchedule(duration, 3);
for (std::size_t i = 0; i < s.jobs.size(); ++i) {
std::cout << "machine " << i << " load=" << s.load[i] << " jobs:";
for (int id : s.jobs[i]) {
std::cout << ' ' << id;
}
std::cout << '\n';
}
std::cout << "makespan=" << s.makespan() << '\n';
return 0;
}

按标准语义推演：作业按 7、5、4、3、2、2、1 的顺序处理。7 落到 0 号机，5 落到 1 号机，4 落到 2 号机；接着 3 落到当前最空的 2 号机（负载 4），2 落到 1 号机（负载 5），另一个 2 落到 0 号机（负载 7），最后的 1 落到 2 号机。三台机器负载分别为 9、7、8，最大完工时间为 9。这个推演只依据代码逻辑，未经编译运行核对。

常见坑点

一、排序比较器写成>=

❌return duration[a] >= duration[b];相等元素互相「小于」，违反严格弱序，传给std::sort是 UB，可能越界访问。

✅ 写return duration[a] > duration[b];，相等时返回false，构成合法的严格弱序。

二、把最小堆写成默认的最大堆

❌std::priority_queue<Item> heap;每次弹出的是负载最大的机器，贪心方向完全相反。

✅ 显式写全三个模板参数：std::priority_queue<Item, std::vector<Item>, std::greater<Item>>，并包含<functional>与<queue>。

三、每次线性扫描找最空机器

❌ 在外层循环里用for扫一遍所有机器找最小值，复杂度退化为 O(n·m)。

✅ 用最小堆，每次 O(log m)；m很大时差别显著，且代码并不会更复杂。

四、按处理时间升序排序

❌ 照搬「短作业优先」的直觉，return duration[a] < duration[b];。

✅ LPT 要求降序。短作业优先优化的是平均完成时间，不是最大完工时间。

五、宣称贪心结果就是最优

❌ 在注释或文档里写「本算法求出最短完工时间」。

✅ 写「近似解，最坏情况不超过最优的4/3 - 1/(3m)倍」，并在需要最优时说明要用精确算法。

六、用int累加负载

❌std::vector<int> load;大量作业累加后溢出，属于 UB。

✅ 全程用long long，std::accumulate也显式给0LL初值。

七、忽略m > n的情形

❌ 认为机器数多于作业数时堆里会残留空机器导致错误，于是特判掉。

✅ 堆里保留全部m台机器，多余机器负载保持 0，makespan()取最大值不受影响，无需特判。

八、作业时长为负或机器数为 0 未校验

❌ 直接进入循环，m = 0时堆为空，heap.top()对空容器调用是 UB。

✅ 入口处校验m > 0与每个时长非负，用std::invalid_argument明确报错。

总结

多机调度是「问题本身很难，所以用贪心换速度」的典型例子。写这类代码时，把排序规则、堆的比较器、累计值的类型三处盯紧，基本就不会出错；至于结果离最优有多远，应当引用定理给出的最坏情况界，而不是凭感觉描述。