1. 调度算法概述：调度问题的定义、分类与性能指标

大家好，我是你们这门课的老朋友。今天咱们聊聊调度算法——说白了，就是怎么把有限资源在正确的时间分配给正确的任务。我做了这么多年优化，发现很多同学一上来就撸代码调参数，结果连问题属于哪一类都没搞清楚。嗯，这其实是个大坑。

1.1 调度问题的定义

调度问题，本质上是一个资源-任务-时间的三元组匹配问题。你想想看，我们有一堆机器（资源），一堆工件（任务），每个工件有若干道工序，每道工序需要特定机器加工一段时间。调度的目标就是决定：哪个工件、在哪个机器上、什么时候开始加工。

我在项目中遇到过最典型的例子：一个芯片测试厂，每天几千片晶圆要测，测试机只有十几台。每片晶圆有几十道测试项，每项测试时间还不一样。如果不做调度，现场工程师全靠经验排，结果就是有的机器闲得发慌，有的机器排队排到下班。这就是典型的调度问题。

1.2 调度问题的分类

调度问题种类很多，但咱们做优化的人，一般按机器数量和加工路径来分。我习惯把它们分成四大类：

1.2.1 单机调度

最简单的情况——只有一台机器。所有工件都得排队在这台机器上加工。听起来简单对吧？但加上截止日期、权重、准备时间这些约束后，单机调度也能变得很复杂。比如，你是先做紧急的小订单，还是先做利润高的大订单？

1.2.2 多机调度（并行机调度）

多台机器，功能相同。每个工件只需要在一台机器上加工一次。问题变成了：把工件分配给哪台机器？以及在这台机器上排什么顺序？

我记得有一次做云计算资源调度，几百台虚拟机要分配任务。每台VM性能差不多，但网络延迟、磁盘IO有差异。这就是典型的并行机调度，只不过机器换成了虚拟机。

1.2.3 流水车间调度

所有工件都走同样的加工路线——先到机器1，再到机器2，再到机器3……就像流水线一样。每个工件在各机器上的加工时间可能不同。

这里有个经典问题叫Flow Shop。我当年做汽车零部件生产线优化时，就是流水车间调度。一条产线十几道工序，任何一道堵了，整条线都得停。嗯，那段时间真是被折磨得够呛。

1.2.4 作业车间调度

最复杂的一类。每个工件有自己的加工路径，可以各不相同。比如工件A需要先车后铣再磨，工件B需要先铣后热处理再车。机器之间没有固定的顺序关系。

这就是著名的Job Shop问题，也是NP-hard中的NP-hard。我见过很多工厂，调度员每天光排第二天的计划就要花两三个小时，还经常排不好。

1.3 性能指标

调度做得好不好，总得有个评判标准。不同的场景关注不同的指标。我一般把它们分成三类：

1.3.1 完工时间相关

• 最大完工时间（Makespan）：最后一个工件完成的时间。说白了就是总工期。工厂老板最关心这个，因为工期越短，产能越高。
• 总完工时间（Total Completion Time）：所有工件完工时间之和。这个指标反映的是平均效率。

1.3.2 延迟相关

• 最大延迟（Maximum Lateness）：所有工件中，完工时间超过截止日期最多的那个。客户最恨这个。
• 拖期工件数（Number of Tardy Jobs）：有多少个工件没按时交付。这个指标很直观，老板一看就懂。
• 加权延迟和（Total Weighted Tardiness）：每个工件延迟时间乘以它的权重。权重高的客户优先保证。

1.3.3 能耗相关

这几年越来越重要了。特别是数据中心、制造业，电费是一笔大开销。

• 总能耗：所有机器运行期间消耗的总电量。
• 峰值功率：同时运行的机器最大功率。这个指标决定了你的变压器容量和电费单价。
• 能效比：单位能耗产出的工件数量。说白了就是每度电能干多少活。

1.4 知识体系总览

说了这么多，咱们用一张图把调度问题的知识体系串起来。我习惯用这种结构图来理清思路：

1.5 小结

这一章咱们把调度问题的底子打好了。说白了，调度就是在正确的时间，把正确的任务，分配给正确的资源。分类上记住四个：单机、多机、流水车间、作业车间。指标上记住三个维度：完工时间、延迟、能耗。

我个人习惯，拿到一个调度问题，先问自己三个问题：

1. 几台机器？——确定是单机还是多机。
2. 加工路径固定吗？——确定是流水车间还是作业车间。
3. 老板最关心什么？——确定优化目标。

这三个问题问完，问题类型基本就定了。后面咱们再针对每种类型，讲具体的优化算法。嗯，到时候你会发现，很多算法其实都是相通的。

---

公众号:蓝海资料掘金营，微信deep3321