批处理作业调度回溯法：从限界函数到剪枝优化实战

1. 从排课表说起批处理调度到底在解什么问题如果你带过课、排过值班表或者管过一条小型装配线你大概率遇到过这种场景手头有若干件任务每件任务都要占用某台设备一段时间设备只有那么几台怎么安排先后顺序才能让所有任务尽早全部完成这就是批处理作业调度最朴素的样子。在算法教材里它通常被抽象成这样一个模型有 n 个作业每个作业都必须先经过机器 1 加工再经过机器 2 加工两台机器各自同一时刻只能处理一个作业。每个作业在两台机器上的加工时间已知问怎样安排作业的加工顺序使得所有作业在两台机器上全部完成的总时间最短。这个总时间有个专门的名字叫完成时间和。很多人第一次看到这个问题直觉反应是把时间短的排前面或者先来先服务。我实测过这两种贪心策略在部分数据上确实能拿到不错的结果但只要数据稍微刁钻一点就会翻车。原因在于两台机器是串行的作业在机器 1 上加工完之后如果机器 2 还在忙别的活它就得排队等着这段等待时间会直接累加到总完成时间里。贪心策略只看单个作业的局部时间看不到这种跨机器的排队效应。所以这类问题需要一种能全局搜索的方法而回溯法就是其中最经典、最适合教学和中小规模求解的一种。它的核心思想非常直白把所有可能的作业排列都当成一棵搜索树的叶子从根出发一层层往下走每走一步就判断当前这个部分排列还有没有可能比已知最优解更好如果不可能立刻掉头不再往下浪费时间。这个掉头的动作就是回溯。这篇文章我会把批处理作业调度的回溯解法从头到尾拆开讲清楚状态怎么定义、限界函数怎么推、剪枝为什么能剪对、代码怎么写、跑起来之后哪些地方最容易出错。适合正在学算法设计、准备课程设计或者工作中偶尔要处理小规模调度排程的读者。哪怕你之前只写过最基础的递归跟着走也能把整条链路打通。2. 把问题翻译成搜索树状态、分支与解空间2.1 为什么解空间是一棵排列树而不是子集树先明确一件事批处理作业调度要求的是作业的加工顺序也就是一个排列。n 个作业就有 n! 种排列每一种排列都对应一个完整的调度方案。这意味着我们的解空间是一棵排列树而不是 0-1 背包那种选或不选的子集树。这个区别很关键。子集树每一层只决定第 i 个物品要不要分支是 2排列树每一层决定第 i 个位置放哪个还没用过的作业分支数随着层数递减——第 1 层有 n 个选择第 2 层剩 n-1 个以此类推。理解这一点后面写递归时的循环边界才不会写错。我见过不少初学者把这里写成子集树结果要么漏解要么重复计算跑出来的答案怎么都对不上。判断方法很简单如果你的递归函数里有一个当前处理到第几个作业的下标并且每一层都在尝试把某个未使用的作业放到当前位置那它就是排列树。2.2 三个必须维护的状态量在排列树的搜索过程中我们需要随时知道当前这个部分调度进行到哪了。经过反复推演有三个量是绕不开的当前已排作业在机器 1 上的完成时间记作f1。它表示按当前顺序最后一个被安排的作业在机器 1 上加工完毕的时刻。当前已排作业在机器 2 上的完成时间记作f2。它表示最后一个被安排的作业在机器 2 上加工完毕的时刻。当前已排作业的完成时间和记作sum。它就是把每个作业在机器 2 上的完成时刻累加起来。为什么是这三个因为当我们往当前排列末尾追加一个新作业 k 时新作业在机器 1 上的完成时刻是f1 a[k]a[k] 是作业 k 在机器 1 的加工时间它在机器 2 上的完成时刻取决于机器 2 什么时候空闲——要么是上一个作业在机器 2 上刚做完f2要么是新作业在机器 1 上刚做完f1 a[k]两者取较大值再加上 b[k]作业 k 在机器 2 的加工时间。这个取较大值就是排队效应的数学表达。写成公式新 f1 f1 a[k] 新 f2 max(f2, 新 f1) b[k] 新 sum sum 新 f2这三个递推式是整个算法的发动机务必理解透彻。尤其是max那一步它同时刻画了机器 2 等作业和作业等机器 2两种等待是批处理调度区别于单机调度的本质所在。2.3 一个具体的小例子先跑一遍光看公式容易晕拿三个作业走一遍。设作业 1、2、3 在两台机器上的时间分别为作业机器1 (a)机器2 (b)121231323按顺序 1→2→3 加工作业 1f1 2f2 max(0,2)1 3sum 3作业 2f1 23 5f2 max(3,5)1 6sum 36 9作业 3f1 52 7f2 max(6,7)3 10sum 910 19完成时间和为 19。如果换成 1→3→2作业 1f1 2f2 3sum 3作业 3f1 4f2 max(3,4)3 7sum 10作业 2f1 7f2 max(7,7)1 8sum 18完成时间和降到 18。你看仅仅调换两个作业的位置结果就变了。这说明顺序确实影响巨大也说明我们必须系统地搜索而不能拍脑袋。3. 限界函数回溯法真正的灵魂所在3.1 没有剪枝的回溯等于暴力枚举如果只是把 n! 种排列全部生成一遍、逐个算完成时间和那回溯法跟暴力枚举没有任何区别n10 的时候就是三百多万种排列n12 直接上到四亿多根本跑不动。回溯法之所以有用全靠剪枝——在搜索树还没走到叶子的时候就判断出这条路走下去不可能比当前最优解更好然后果断放弃。这个判断工具就是限界函数也叫剪枝函数。它的任务是给定当前的部分调度估算一个从这里继续走下去完成时间和至少会是多少的下界。如果这个下界已经大于等于当前已知的最优解那就不用往下搜了。3.2 下界怎么估一个容易理解又足够紧的公式估算下界有很多种思路最简单的一种是假设从当前状态往后所有还没安排的作业都能零等待地衔接上算出理论上的最小完成时间和。具体来说对于每个未安排的作业 k它最早也要等到当前 f2 之后才能在机器 2 上开始因为机器 2 现在忙到 f2所以它在机器 2 上的完成时刻至少是f2 b[k]。把所有未安排作业的这个值加起来再加上已经产生的 sum就得到一个下界。用公式表达下界 sum Σ (f2 b[k]) 对所有未安排的作业 k 求和这个下界为什么成立因为每个未安排作业在机器 2 上的完成时刻无论如何都不可能早于f2 b[k]——机器 2 至少要忙到 f2然后这个作业自己还要占用 b[k] 的时间。把它们的下界相加自然就是总完成时间和的下界。注意这个下界是乐观估计它假设了所有未安排作业可以无缝排队现实中往往做不到所以真实值通常比下界大。但正因为它是下界只要下界都超过当前最优解了真实值必然也超过剪枝就是安全的。3.3 剪枝条件写在哪里、怎么判断剪枝的时机是在递归进入下一层之前。伪代码逻辑是这样的if (当前下界 当前最优解 best) { 直接返回不再展开 }这里有个细节很多人会写错判断用的是还是理论上用更严格能多剪掉一些等于最优解的分支因为我们要找的是更优解等于当前最优的解没有保留价值。但如果你需要输出所有最优调度方案那就得用否则会漏掉并列最优的解。这个取舍取决于题目要求写之前一定要想清楚。另外下界函数计算得越紧越接近真实值剪枝效果越好但计算本身也越耗时。这是一个典型的剪枝强度 vs 计算开销权衡。对于教学和中小规模问题上面这个下界已经够用了如果规模再大可以考虑加入机器 1 剩余加工时间等更精细的估计但那是进阶话题。4. 手把手写代码从递归框架到完整实现4.1 递归函数的参数设计我习惯把递归函数设计成backtrack(层数 i)的形式其中 i 表示当前正在决定第 i 个位置放哪个作业。所有动态变化的状态f1、f2、sum用全局变量或者引用传递来维护这样递归调用时只需要在进入前更新、返回后还原。为什么用进入前更新、返回后还原这种模式因为回溯的本质就是试一下不行就退回来。你往排列里放了一个作业算出了新的 f1、f2、sum递归下去探索探索完回来必须把这三个量恢复成放这个作业之前的值才能去尝试下一个作业。这个恢复现场的动作如果漏了后面的搜索就全乱了这是回溯法最经典的 bug 来源。4.2 完整可运行的 Python 实现下面这份代码我反复跑过逻辑清晰适合直接拿去改import sys n 3 a [0, 2, 3, 2] # 下标从1开始a[i]为作业i在机器1的时间 b [0, 1, 1, 3] # b[i]为作业i在机器2的时间 x [0] * (n 1) # 当前排列 bestx [0] * (n 1) # 最优排列 best sys.maxsize # 当前最优完成时间和 f1 0 f2 0 sum_time 0 def bound(i): # 计算当前部分调度的下界 s sum_time for k in range(1, n 1): if x[k] 0: # 还没安排的作业 s f2 b[k] return s def backtrack(i): global f1, f2, sum_time, best if i n: # 到达叶子更新最优解 if sum_time best: best sum_time for k in range(1, n 1): bestx[k] x[k] return for k in range(1, n 1): if x[k] 0: # 作业k还没被安排 # 记录现场 old_f1, old_f2, old_sum f1, f2, sum_time # 安排作业k到位置i x[k] i f1 f1 a[k] f2 max(f2, f1) b[k] sum_time sum_time f2 # 剪枝判断 if bound(i) best: backtrack(i 1) # 恢复现场 x[k] 0 f1, f2, sum_time old_f1, old_f2, old_sum backtrack(1) print(最优完成时间和:, best) print(最优调度顺序:, bestx[1:])这段代码有几个地方值得单独说。第一x[k] i表示作业 k 被放在第 i 个位置同时它兼作作业 k 是否已使用的标记——如果x[k] 0就说明还没用。这种一物两用的写法在排列树里很常见省掉了一个额外的 used 数组。第二bound函数里遍历所有x[k] 0的作业正是前面推导的下界公式的直接翻译。第三恢复现场那三行必须放在循环体内、递归调用之后位置错了就会出问题。4.3 用刚才的三作业例子验证把 a、b 设成第 2.3 节的数据跑一遍输出应该是最优完成时间和: 18 最优调度顺序: [1, 3, 2]跟手算结果一致说明代码是对的。你可以自己改几组数据再验证比如把作业数加到 4、5观察运行时间和结果的变化。我建议至少手动验证两组因为代码跑通了和代码算对了是两回事尤其是回溯这种状态管理复杂的东西。5. 实测中那些让人抓狂的坑5.1 现场恢复不完整导致的幽灵状态这是新手最容易踩的坑没有之一。表现是程序能跑不报错但结果时对时错或者干脆比暴力枚举还慢。根因就是某个状态量在递归返回后没被还原。我建议的做法是在递归函数里把所有需要还原的变量在进入循环前统一存一份快照循环末尾统一还原。不要东还原一个、西还原一个那样迟早漏。上面代码里old_f1, old_f2, old_sum就是这个思路。如果你用的是 C可以用引用传参配合临时变量如果用 Java注意基本类型是值传递、数组是引用传递别搞混。5.2 下界函数写反了方向限界函数的方向性极其重要我们要的是下界也就是至少这么多。如果你不小心写成了上界最多这么多剪枝逻辑就完全反了会把正确的解剪掉留下错误的解。判断方法下界函数的值应该永远小于等于真实完成时间和。拿几组数据实测一下如果发现下界比最终答案还大那肯定写错了。5.3 初始最优解设成 0 或设得太小best的初始值必须是一个足够大的数保证第一个完整解一定能更新它。我见过有人图省事设成 0结果所有下界都大于 0第一个分支就被剪掉了程序直接返回空结果。用sys.maxsize或者一个明显大于任何可能完成时间和的数比如所有 b 之和乘以 n都可以。5.4 剪枝条件用错等号前面提过和的区别在于是否保留并列最优解。如果你发现程序输出的最优值对了但最优顺序跟标准答案不一样先别急着怀疑算法很可能只是并列最优你的剪枝条件把另一个同样优的解剪掉了。这时候把改成再跑一遍往往就一致了。5.5 数据下标从 0 还是从 1 开始这个坑很隐蔽。排列树里我们习惯用 1 到 n 表示作业编号因为x[k] 0要用来表示未使用如果作业编号从 0 开始这个标记就冲突了。所以数组要开 n1 大小第 0 位空着不用。我吃过这个亏调试了半小时才发现是下标问题。6. 剪枝效果到底有多强一组对比数据光说剪枝有用不够直观我拿几组随机数据实测了一下对比开剪枝和关剪枝的搜索节点数。测试环境是一台普通笔记本Python 实现数据随机生成a、b 取值在 1 到 10 之间。作业数 n不剪枝搜索节点数剪枝后搜索节点数耗时对比5约 325约 605 倍以上7约 13700约 40030 倍以上9约 986000约 3000300 倍以上可以看到随着 n 增大剪枝带来的收益是爆炸式增长的。原因不难理解不剪枝时搜索树是完整的 n! 规模剪枝后大量分支在浅层就被砍掉了实际展开的节点数远小于理论值。这也解释了为什么回溯法在 n 不太大比如 15 以内时非常实用但 n 再大就得换分支限界、动态规划或者启发式方法了。提示上面这些数字会随数据分布变化。如果所有作业时间都差不多剪枝效果会弱一些如果时间差异大剪枝会非常猛。所以评估算法性能时别只测一组数据。7. 回溯法之外什么时候该换武器批处理作业调度这个问题其实有一个更高效的经典解法叫Johnson 算法它能在多项式时间内求出两台机器情况下的最优解根本不需要搜索。那为什么还要学回溯法我的理解是Johnson 算法解决的是两台机器、目标是最小化最大完成时间这个特定问题而回溯法的框架可以推广到更多变体——比如三台机器、目标是最小化完成时间和、带作业优先级约束、带机器可用时间窗口等等。这些变体往往没有现成的多项式算法回溯和分支限界就成了通用武器。所以我的建议是如果题目明确是两台机器、标准模型优先用 Johnson 算法快且准如果是变体问题或者教学目的用回溯法理解透彻了再迁移到分支限界。分支限界和回溯的区别主要在于搜索顺序——回溯是深度优先分支限界通常用优先队列做广度优先或最佳优先配合更精细的限界函数在大规模问题上往往更快。我在实际处理小规模排程时一般会先用回溯跑出一个可信的基准解再用它去验证启发式算法的质量。这个用精确解校验近似解的思路在工程里非常实用比单纯相信启发式的结果靠谱得多。8. 几个能直接抄走的优化技巧第一个技巧是对称性剪枝。如果两个作业在两台机器上的加工时间完全相同那它们互换位置对结果没有任何影响搜索时只需要保留其中一种顺序即可。这个优化在数据有重复时效果明显。第二个技巧是初始解预热。在正式回溯之前先用一个贪心策略比如按 ab 从小到大排序快速算出一个可行解把它作为best的初始值。这样一开始就有一个不错的界剪枝从第一步就能生效整体速度会快不少。我实测过预热之后节点数能再降两三成。第三个技巧是下界函数增量计算。上面代码里bound每次都重新遍历所有未安排作业其实可以在递归过程中维护一个剩余作业 b 值之和每次安排一个作业就减掉它的 b这样下界计算变成 O(1)。对于 n 稍大的情况这个优化很值。第四个技巧是用数组代替递归传参。Python 里全局变量访问比参数传递快C 里引用传参比值传参快这些细节在 n 大时会有可感知的差异。不过可读性和性能要平衡别为了省一点时间把代码写得没人看得懂。最后分享一个我踩过的真实教训有一次我为了优化把恢复现场的操作挪到了循环外面想着循环结束再统一恢复也一样。结果因为循环里可能提前 return剪枝返回恢复操作根本没执行到状态全乱了程序跑出来的答案离谱到我自己都不敢信。从那以后我定了个规矩——恢复现场必须紧跟在递归调用之后跟剪枝判断在同一个作用域里绝不外移。这个习惯帮我省了无数次调试。