4. 贪心算法进阶：加权最短处理时间（WSPT）、最小化最大延迟（Hodgson算法）
好，咱们继续往下聊。上一节我们聊了基础贪心，这一节要上点强度了。加权最短处理时间（WSPT）和最小化最大延迟（Hodgson算法），这两个名字听起来挺唬人，但说白了，就是解决两个非常实际的问题：
- 任务有轻重缓急，怎么排最划算？ —— 这就是 WSPT 要干的。
- 任务都有截止时间，怎么排才能让「迟到」最不严重？ —— 这就是 Hodgson 算法要干的。
我在项目里遇到过好几次，排产排得乱七八糟，要么是重要客户的小单子被大单子挤到后面，要么是某个任务晚交了几天，整个项目链都崩了。嗯，这两个算法就是专门治这些毛病的。
4.1 加权最短处理时间（WSPT）
先说说 WSPT。你想想看，如果所有任务都一样重要，那按处理时间短的先做（SPT规则）肯定没错。但现实世界哪有这么简单？客户 A 的单子利润高，客户 B 的单子量大但利润薄。这时候，我们就得给每个任务加个「权重」wᵢ。
WSPT 的规则极其简单： 按照 wᵢ / pᵢ 的比值从大到小排序。pᵢ 是处理时间，wᵢ 是权重（可以理解为优先级或单位时间价值）。
为什么会这样？我个人的理解是：这个比值衡量的是「单位时间能创造的价值」。你想想，一个任务每分钟能赚 100 块，另一个每分钟只能赚 10 块，傻子都知道先做哪个。
核心公式：
目标：最小化 ∑ wᵢ · Cᵢ （加权完成时间之和）
排序规则：按 wᵢ / pᵢ 降序排列
我在项目中遇到过这样一个场景：一个工厂有 5 个订单，每个订单的利润（权重）和加工时间都不一样。一开始他们按先来后到做，结果利润最高的订单被拖到最后，客户差点流失。后来我帮他们改成 WSPT 排序，同样的产能，利润提升了 18%。
来看个具体例子：
| 任务 | 处理时间 pᵢ | 权重 wᵢ | wᵢ / pᵢ |
|---|---|---|---|
| A | 3 | 5 | 1.67 |
| B | 5 | 3 | 0.60 |
| C | 2 | 4 | 2.00 |
| D | 4 | 2 | 0.50 |
按 wᵢ / pᵢ 降序排列：C → A → B → D。就这么简单。
// WSPT 排序伪代码
function wsptSort(tasks):
// tasks: [{id, processingTime, weight}]
return tasks.sort((a, b) => {
return (b.weight / b.processingTime) - (a.weight / a.processingTime);
});小提示： 如果两个任务的 wᵢ / pᵢ 比值相等，我建议按处理时间短的优先。虽然理论上不影响总加权完成时间，但实际中短任务先做完，能释放资源，心理上也舒服些。
4.2 最小化最大延迟（Hodgson算法）
好，接下来聊 Hodgson 算法。这个算法解决的是另一个经典问题：每个任务都有截止时间 dᵢ，我们想尽量减少「最大延迟」Lmax。
什么叫最大延迟？就是所有任务中，完成时间超过截止时间最多的那个差值。说白了，就是「最晚的那个任务晚交了多久」。我们的目标，就是让这个「最晚」尽可能小。
Hodgson 算法的思路很有意思，它分两步走：
- 先按截止时间排序（EDD规则） —— 截止时间越早的越先做。这是基础。
- 如果发现某个任务会延迟，就把它前面的「最长处理时间」的任务踢出去 —— 踢出去的任务标记为「延迟任务」，放到最后做。
嗯，这里要注意：被踢出去的任务，我们就不再考虑它的延迟了。说白了，我们允许它「无限晚交」，只要保证其他任务不延迟就行。
Hodgson 算法核心思想：
1. 按截止时间 dᵢ 升序排列（EDD）
2. 遍历任务，如果当前任务会导致延迟，则从已排任务中剔除处理时间最长的那个
3. 被剔除的任务标记为「延迟」，放到序列末尾
我曾经在一个软件开发项目中用过这个思路。当时有 8 个功能模块要上线，每个都有硬性截止时间。一开始按功能重要性排，结果好几个模块都延期了。后来我改用 Hodgson 的思路，先按截止时间排，发现某个大模块会拖垮整个计划，果断把它拆成两个迭代。最后只有一个小功能延期了，整体交付质量大幅提升。
来看代码实现：
// Hodgson 算法实现
function hodgsonAlgorithm(tasks):
// tasks: [{id, processingTime, dueDate}]
// 1. 按截止时间排序
tasks.sort((a, b) => a.dueDate - b.dueDate);
let scheduled = [];
let delayed = [];
let currentTime = 0;
for (let task of tasks) {
scheduled.push(task);
currentTime += task.processingTime;
// 2. 检查是否有延迟
if (currentTime > task.dueDate) {
// 找到 scheduled 中处理时间最长的任务
let maxTask = scheduled.reduce((max, t) =>
t.processingTime > max.processingTime ? t : max
);
// 3. 剔除最长任务，放到延迟列表
scheduled = scheduled.filter(t => t !== maxTask);
currentTime -= maxTask.processingTime;
delayed.push(maxTask);
}
}
return { scheduled, delayed };避坑指南： 我曾经犯过一个错误——在剔除任务时，只考虑当前导致延迟的任务，而没有检查前面的任务。记住，剔除的是「已排序列中处理时间最长的」，不一定是当前这个。因为把那个「大块头」挪走，后面的所有任务都能受益。
4.3 两种算法的对比与选择
这两个算法虽然都是贪心，但解决的问题完全不同。我整理了个对比表：
| 维度 | WSPT | Hodgson |
|---|---|---|
| 优化目标 | 最小化 ∑ wᵢ · Cᵢ | 最小化最大延迟 Lmax |
| 排序依据 | wᵢ / pᵢ 降序 | dᵢ 升序（EDD）+ 剔除策略 |
| 适用场景 | 任务有不同优先级/价值 | 任务有硬性截止时间 |
| 时间复杂度 | O(n log n) | O(n²) 或 O(n log n) 优化版 |
| 是否允许延迟 | 允许，但尽量让高权重任务早完成 | 允许部分任务无限延迟 |
你想想看，实际项目中怎么选？我个人习惯是：
- 如果客户说「这几个订单必须按时交付，其他的可以商量」—— 用 Hodgson。
- 如果客户说「每个订单都有利润，我想让总利润最大化」—— 用 WSPT。
- 如果两者都要考虑？嗯，那就需要更复杂的算法了，比如结合分支定界法。但那是后话了。
实战技巧： 我在做排产系统时，经常把 WSPT 和 Hodgson 结合起来用。先用 WSPT 排出一个初始序列，保证高价值任务优先；然后检查是否有任务会严重超期，如果有，再用 Hodgson 的思路微调。这样既保证了利润，又控制了风险。
好了，这一节的内容就到这。贪心算法虽然简单，但 WSPT 和 Hodgson 这两个变体，在实际工程中非常实用。下次你遇到排程问题，不妨先想想：是权重重要，还是截止时间重要？想清楚了，算法自然就出来了。