前言多机调度问题multiprocessor scheduling的经典形式是有n个作业和m台相同的机器每个作业有一个处理时间作业不可拆分、一旦开始就在某台机器上连续执行到结束目标是最小化全部作业完成的时间也就是最大完工时间makespan。这个问题在m 2时是 NP 难的不存在已知的多项式时间精确算法。因此工程上普遍使用贪心近似按某种规则给作业排序再依次把作业放到当前负载最小的机器上。最常见的误解有两个。第一以为「每次挑当前最长的作业放到最空的机器」一定得到最优解。它只是一个有理论保证的近似算法叫 LPTlongest processing time first保证结果不超过最优解的4/3 - 1/(3m)倍并不保证等于最优。第二把贪心规则记反按处理时间从短到长排序SPT那个顺序是为「最小化平均完成时间」服务的用在最大完工时间上效果会明显变差。本文讲清问题的难度来源、LPT 规则为什么合理、如何用std::priority_queue维护最小负载机器并给出一份可直接改写复用的完整实现。所有复杂度结论按标准库容器与算法的约定分析不给出任何未经测量的耗时数字。一、为什么精确求解很难把m台机器看成m个桶把作业看成带重量的球目标是把球分进桶里使最重的桶尽量轻。这正是划分问题partition problem的多桶推广而两机情形已经包含划分问题作为特例后者是经典的 NP 完全问题。因此除非P NP否则不存在对所有输入都快速且精确的算法。精确算法在实践中只有几类作业数很小时用状态压缩动态规划或分支限界m 2时用伪多项式时间的子集和动态规划作业数中等时用整数规划求解器。这些方法都超出了「贪心」的范围。理解这一点很重要贪心的价值在于快速得到一个不错的可行解而不是求最优。二、LPT 规则与它的保证LPT 的步骤只有两步把所有作业按处理时间从大到小排序依次取出作业分配给当前累计负载最小的机器。直观理由是长作业决定了最终的最大值先安排它们可以避免「最后剩一个超长作业只能堆在已经满载的机器上」的糟糕局面。这个算法有一个被证明的近似比设最优解的最大完工时间为OPTLPT 得到的为LPT则LPT (4/3 - 1/(3m)) * OPT。这是算法教科书里的经典定理不是实验统计值。作为对比如果完全不排序、按输入顺序把作业丢给最空的机器list scheduling保证是2 - 1/m倍。两者都是上界实际差距可能远小于上界也可能刚好取到上界附近的构造实例。需要强调近似比是「最坏情况」的保证不能反过来理解为「通常只差多少个百分点」。写文档时不要把它说成平均误差。三、用最小堆维护机器负载每台机器只需要记录两个量编号和当前累计负载。每一步要取出负载最小的那台因此用最小堆。C 的std::priority_queue默认是最大堆要得到最小堆需要显式传入比较器std::greater并且把元素类型写成std::pairlong 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 是允许的负值属于调用方错误用异常拒绝。// 适用于 C17#include algorithm#include functional#include iostream#include numeric#include queue#include stdexcept#include vectorstruct Schedule {std::vectorstd::vectorint jobs; // 每台机器上的作业下标std::vectorlong 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::vectorlong 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_caststd::size_t(m));result.load.assign(static_caststd::size_t(m), 0);std::vectorint 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::pairlong long, int; // (负载, 机器编号)std::priority_queueItem, std::vectorItem, std::greaterItem 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_caststd::size_t(machine)].push_back(id);result.load[static_caststd::size_t(machine)] duration[id];heap.push(Item{result.load[static_caststd::size_t(machine)], machine});}return result;}int main() {std::vectorlong 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 号机负载 42 落到 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_queueItem heap;每次弹出的是负载最大的机器贪心方向完全相反。✅ 显式写全三个模板参数std::priority_queueItem, std::vectorItem, std::greaterItem并包含functional与queue。三、每次线性扫描找最空机器❌ 在外层循环里用for扫一遍所有机器找最小值复杂度退化为 O(n·m)。✅ 用最小堆每次 O(log m)m很大时差别显著且代码并不会更复杂。四、按处理时间升序排序❌ 照搬「短作业优先」的直觉return duration[a] duration[b];。✅ LPT 要求降序。短作业优先优化的是平均完成时间不是最大完工时间。五、宣称贪心结果就是最优❌ 在注释或文档里写「本算法求出最短完工时间」。✅ 写「近似解最坏情况不超过最优的4/3 - 1/(3m)倍」并在需要最优时说明要用精确算法。六、用int累加负载❌std::vectorint load;大量作业累加后溢出属于 UB。✅ 全程用long longstd::accumulate也显式给0LL初值。七、忽略m n的情形❌ 认为机器数多于作业数时堆里会残留空机器导致错误于是特判掉。✅ 堆里保留全部m台机器多余机器负载保持 0makespan()取最大值不受影响无需特判。八、作业时长为负或机器数为 0 未校验❌ 直接进入循环m 0时堆为空heap.top()对空容器调用是 UB。✅ 入口处校验m 0与每个时长非负用std::invalid_argument明确报错。总结策略排序方式分配规则近似比上界时间复杂度列表调度不排序放到最空机器2 - 1/mO(n log m)LPT处理时间降序放到最空机器4/3 - 1/(3m)O(n log n n log m)短作业优先处理时间升序放到最空机器无此方向的经典保证O(n log n n log m)精确算法视方法而定视方法而定1最优指数级或伪多项式多机调度是「问题本身很难所以用贪心换速度」的典型例子。写这类代码时把排序规则、堆的比较器、累计值的类型三处盯紧基本就不会出错至于结果离最优有多远应当引用定理给出的最坏情况界而不是凭感觉描述。