简介模拟退火算法解决作业车间调度问题JSP的C语言实现与配套说明文档面向计算机专业学生、工业工程师及算法爱好者用于求解多工件多工序条件下的完工时间最小化问题。压缩包共2个文件总体积约210KBcpp源码完整实现了随机初始解生成、邻域扰动、Metropolis接受准则与指数降温策略等核心环节docx文档则从问题背景、数学模型到参数设置与结果分析形成可对照学习的闭环。目前已有3498人学习/下载。通过源码阅读和文档实操读者能理解模拟退火如何通过概率性接受劣解跳出局部最优学会调整初始温度、冷却速率和迭代停止条件来平衡搜索质量与效率并能将这一思路迁移到生产排产、路径规划等类似组合优化场景中为后续设计更高效的调度算法打下基础。1. 模拟退火为什么是作业车间调度的首选试错方案调度排产做到一定规模最难受的不是算法跑得慢而是最优解根本求不出来。作业车间调度问题Job Shop Scheduling, JSP只要工件数超过 10、机器数超过 8直接上精确求解器就会面临指数级爆炸等一晚也未必给出一个可行解。这时候模拟退火Simulated Annealing, SA几乎是最快的落地路径逻辑五六十行就能跑通不依赖昂贵的商业求解器而且你不需要证明全局最优只要能在可接受时间内拿到一个“足够好”的排产车间就能立刻用起来。这篇笔记写给两类人一类是刚接触排产优化的开发者想知道怎么用模拟退火把这个调度问题跑出一个像样的结果另一类是已经在用启发式算法、但对邻域搜索和解码细节心里没底的人。我会把编码方式、解码规则、温度曲线、邻域操作和参数调试整个过一遍每一步都能照着敲。至于那些“为什么别人调参跑出的结果就是比你好”的玄学大部分其实都出在解码和邻域这两个环节上下面会逐个拆开讲。2. 先立住模型JSP的形式化与模拟退火的适配点2.1 JSP的约束拆解工序顺序和机器独占这两条硬约束JSP 的经典定义是有 n 个工件每个工件有 m 道工序每道工序必须在指定的某一台机器上加工且加工时间固定。不同工件的工序之间没有先后关系但同一个工件的工序必须按给定顺序执行。调度要决定的是为每道工序选择一个开工时间使得所有工序都完成而总完工时间makespan最小。这里只有两条硬约束。第一同一工件的工序顺序不能乱工序 2 必须在工序 1 完成后才能开始。第二同一台机器同一时刻只能加工一道工序。其余约束都是这两条的推论。所以问题本质是在满足这两个约束的所有可行调度里找完成时间最小的那个而可行调度的数量是 (n!)^m 量级的这就是 NP-hard 的来源。做模拟退火之前先把这些问题用数据形式和代码确认一遍每个工件的工序数、每道工序对应的机器编号、加工时间。标准做法是读入两个矩阵一个存工序对应的机器一个存加工时间。工件数几十、机器数十几的规模读取和校验都非常快这一步不写快反而会在后面排查调度冲突时吃大亏。2.2 模拟退火的Metropolis准则如何绕过局部最优模拟退火和爬山法一样都是沿着邻域移动的区别在于它允许以一定概率接受更差的解。温度高的时候接受概率大算法大步乱跳温度低的时候接受概率小算法逐渐收敛到某个局部区域。在 JSP 上这个策略比禁忌搜索和遗传算法都更容易只用少量参数就调出稳定的结果因为它没有记忆结构几乎不消耗额外内存。Metropolis 准则的公式很简单当新解的目标值比当前解好时无条件接受当新解更差时以概率 exp(-(新目标值-当前目标值)/温度) 接受。温度是控制探索与开采平衡的唯一开关。这个准则对 JSP 尤其友好的原因在于调度解空间里有大量结构相似、目标值相近的邻居解差解不一定是坏解很多次优解会引导到更好的区域。解空间搜索的效率还取决于邻域结构。JSP 里常用的邻域操作有工序交换swap和工序插入insertion两种各有适用的规模场景后面第四章会展开细说。从建模角度看你只需要把 SA 的“当前解”定义成一个完整的调度“邻域解”定义成在当前调度上做一次小扰动得到的新调度剩下的事情就都统一了。3. 最小可复现实现编码、解码与邻域操作的三个关键落点3.1 基于工序的编码与活动化解码在 JSP 中最常用的编码方式是“基于工序的编码”。你可以把调度表示成一个一维整数数组长度为所有工件的工序总数数组里每次出现工件编号就代表该工件按顺序推进一道工序。比如数组 [1, 2, 1, 2] 表示工件 1 的第一道工序、工件 2 的第一道工序、工件 1 的第二道工序、工件 2 的第二道工序。这种编码天然满足同一工件工序顺序约束因此交换或插入后得到的数组仍然合法无需修复。解码是从编码生成实际开工时间表的过程这是整个算法里最容易出偏差的地方。解码时逐个读取编码数组中的每个工序找到该工序所在机器上最早可插入的时间窗口。具体说先找到这个工序所属工件的前一道工序的完工时间这是最早开工时间再在这个工件前序完工时间之后在这台机器的空闲区间中找第一个能装下加工时间的窗口把工序插进去。我用过的解码实现有两类一类是每次从头扫描机器时间线找空闲窗口代码直观但 O(n*m) 复杂度更高另一类是维护每台机器的空闲段列表用二分法找窗口性能更好。小规模问题两种都能跑但大规模建议直接上空闲段列表后面的搜索要迭代成千上万次解码速度快慢直接决定你是否愿意把参数调到足够好。def decode(seq, job_count, machine_seq, proc_time): # 记录每个工件下一道工序的索引 job_step [0] * job_count # 记录每个工件上道工序的完工时间 job_finish [0] * job_count # 每台机器的空闲段列表初始为 [0, infinity] machine_free [[[0, float(inf)]] for _ in range(16)] schedule [] for job_id in seq: step job_step[job_id] machine machine_seq[job_id][step] duration proc_time[job_id][step] earliest_start job_finish[job_id] # 在 machine 的空闲段里找能容纳 duration 的窗口 start_time None for idx, (s, e) in enumerate(machine_free[machine]): if e - s duration and max(s, earliest_start) duration e: start_time max(s, earliest_start) # 更新空闲段列表拆分成两段 machine_free[machine][idx] [s, start_time] if start_time duration e: machine_free[machine].insert(idx 1, [start_time duration, e]) break if start_time is None: raise ValueError(no feasible slot found, code error) end_time start_time duration job_finish[job_id] end_time job_step[job_id] 1 schedule.append((job_id, machine, start_time, end_time)) makespan max(job_finish) return schedule, makespan上面这段代码的每个细节都会影响结果。关键点在earliest_start的处理它保证同一工件前序工序未完成时当前工序不能提前开工这是第一条硬约束。而机器空闲段的拆分会保证同一机器同一时刻只加工一道工序这是第二条硬约束。如果某台机器空闲时间窗不够代码会抛异常——正常编码序列下不应走到这个分支如果走到说明空闲段维护逻辑写错了后续排错时优先检查这里。3.2 两种邻域操作交换和插入以及它们的效果差异邻域操作决定了解空间的连接方式。在工序编码上最常用的操作是随机选两个不同位置交换或者随机取一个工序插入到另一个位置。这两种操作对 JSP 解码结果的影响差别很大。交换会打乱两个工件在序列中的相对节奏改变是局部的适合在温度较高时快速探索插入则会改变一段工序序列的整体顺序产生的邻域解往往差异更大适合在温度较低时精细调整。在实际工程方案里我一般会在高层温度使用交换操作到低层温度改为插入操作这种 combo 在 makespan 收敛速度和终值上通常比单一邻域好 10%~20%。这不算什么严密定理更像积累下来的经验但你可以直接照用再根据自己的数据规模微调切换温度点。import random def neighbor_swap(seq): i, j random.sample(range(len(seq)), 2) seq[i], seq[j] seq[j], seq[i] return seq def neighbor_insert(seq): i random.randrange(len(seq)) val seq.pop(i) j random.randrange(len(seq)) seq.insert(j, val) return seqswap 和 insert 各自的作用域要结合解码过程体会。swap 直接在序列上换两个位置不改变其他工序相对顺序解码时只会影响这两道工序及后续工序的时间窗局部扰动小insert 把一个工序抽出来放在另一个位置中间所有工序的位置都顺移一位邻域解变化更大可能打开新的搜索方向。参数选择上每次迭代在 swap 和 insert 之间二选一即可不必两个操作都执行。4. 让算法跑起来模拟退火主循环的代码骨架与参数调优4.1 主循环代码骨架全注释模拟退火的主体比很多人想象得简单就是一个外层降温循环嵌一个内层抽样循环。外层负责把温度从高往低降内层在每个温度下反复生成邻域解并用 Metropolis 准则判断是否接受。写代码前先明确几个变量初始温度、终止温度、降温速率、每个温度下的迭代次数马尔可夫链长度、以及记录全局最优解的位置。def simulated_annealing(initial_seq, initial_makespan, sa_params): cur_seq initial_seq[:] cur_cost initial_makespan best_seq cur_seq[:] best_cost cur_cost T sa_params[T_init] T_end sa_params[T_end] alpha sa_params[alpha] L sa_params[L] while T T_end: for _ in range(L): new_seq cur_seq[:] # 根据当前温度选择邻域操作 if T sa_params[T_switch]: neighbor_swap(new_seq) else: neighbor_insert(new_seq) _, new_cost decode(new_seq, job_count, machine_seq, proc_time) delta new_cost - cur_cost if delta 0 or random.random() math.exp(-delta / T): cur_seq new_seq[:] cur_cost new_cost if cur_cost best_cost: best_seq cur_seq[:] best_cost cur_cost T * alpha return best_seq, best_cost这段代码里值得解释的细节有三个。第一L表示该温度下的迭代次数通常设为工序总数的 10~20 倍太少则当前温度下搜索不充分太多则计算时间线性增长。第二alpha是降温系数常用 0.95~0.99太靠近 1 收敛慢但结果好0.9 以下跑得快但容易落入局部最优。第三T_switch是交换和插入操作的切换温度这个值不是必须的但加了之后中等规模问题上终值通常会更好。运行流程是这样先用贪心法生成一个可行初始解比如按工序顺序逐个插入最早可行时间窗作为模拟退火的起点然后进入外层循环。每次新解的代价都是通过重新解码得到的没有做增量计算。这样实现的优点是不会积累误差缺点是解码开销大所以在解码函数上做优化比在退火逻辑上做优化收益更大。4.2 初始温度、衰减系数、终止温度和迭代次数的参数表模拟退火之所以被人说是玄学就是参数没有一个万能值但你可以用一个通用规则确定它们而不是拍脑袋。初始温度决定了算法前期接受差解的概率。标准做法是随机采样若干邻居解计算目标值的平均绝对差然后反推初始温度使得初始接受概率在 0.85 左右。我通常在核心参数表里保留一组不敏感的建议值见下表实际项目里会在此基础上做一轮网格调整。参数建议范围设定逻辑对结果影响初始温度 T_init目标值标准差的 5~10 倍保证高温期能接受 85% 的差解太小会过早收敛太大浪费时间终止温度 T_end小于目标值标准差的 0.05 倍低温期只接受极少数差解过大提前结束过小拖时间降温系数 alpha0.95~0.99温度下降越慢搜索越充分0.95以下易陷入局部最优每温度迭代数 L工序总数的 10~20 倍保证当前温度下充分探索过短搜索不充分过长耗时邻域切换温度 T_switch初始温度的 20%~40%高温交换快速探索低温插入精细调整对终值有 10% 左右的提升这个表的每项都不是随意定的。初始温度如果目标值范围大而温度设太小高温期所有差解都被拒绝模拟退火就会退化成爬山法等于没做反过来温度过大则在高温期纯随机游走白白浪费大量迭代。终止温度也不宜设到 0因为到达极低温度后几乎不接受任何差解继续降温和空转没有区别。实际工作中给每位新手同事的建议是先用小算例3 工件 × 3 机器把整套流程跑通确认解码结果可以和穷举法对上的再上大规模数据大规模数据下先固定初始温度只调 alpha 和 L用目标函数的下降曲线观察是否出现长时间平台期。平台期说明温度下降过快需要把 alpha 调大或者加大 L。5. 模拟退火求解JSP的常见问题排查与避坑记录5.1 现象一解码耗时暴增一次迭代比一次迭代慢有次在某公司的排产模拟项目X里排查助手反馈程序跑得越来越慢一开始以为数据规模太大后来才发现代码里每台机器的空闲段在解码时重复扫描了所有历史工序复杂度从线性变成了平方级。现象就是同样 1000 次迭代开始时几毫秒几百次后变成几百毫秒。原因绝大多数不在退火逻辑而在解码数据结构。循环里每次插入空闲段都从头部开始线性查找空闲段越来越多查找长度越来越长整体就退化成 O(n^2)。解决方法是把每台机器的空闲段维护成有序列表并用二分查找定位候选窗口插入删除时只做局部更新。这个改动一般能让解码速度提升一个量级。5.2 现象二初始温度设错前期快速坍缩到次优解某次做多工件多机器的调度初始温度直接按经验填了 100结果目标值从 2000 一路掉到 1400 就再也不动了重跑多次都卡在 1420 附近。用穷举验证发现全局最优在 1380 左右明显是收敛太早。原因在于目标值范围太大差解的 delta 在 30~80 之间exp(-delta / T) 在 T100 时只是 0.7 左右并不是足够高的接受概率而正确逻辑要求初始时刻接受大部分差解给算法足够多的随机跳跃空间。解决方法是先随机跑 500 次邻域操作统计目标值的标准差再反推初始温度确保初始接受概率在 0.8~0.9。这个做法比按经验填数可靠得多尤其是你换了新数据集之后目标值尺度变了经验温度完全不适用。5.3 现象三最优解连续几千次迭代没有更新退火跑到中后期经常出现连续 2000 次迭代 does not improve 的情况新手会以为算法已经收敛。绝大多数情况下不是收敛而是温度还是太高接受大量差解在整个解空间里乱跳导致局部最优附近的好解很快被弹出去。解决思路是检查温度曲线看看当前温度处于哪个阶段。如果还在初始温度的 20% 以上那就不需要干预给算法更多时间搜索如果已经在很低温度但仍不更新说明该项下的迭代数 L 不够需要加大 L 或调小 alpha 让温度降得更慢。另一个选择是引入“回火”机制长时间未更新时把温度回升到当前温度的 2~3 倍再重新降温。实际工程中这个技巧经常能把结果再压低 3% 左右。5.4 现象四同一份代码两次运行结果差异明显模拟退火是随机算法没有固定随机种子就必然有方差。如果两次结果相差超过 5%可能不是种子问题而是初始解或邻域操作概率分布有问题。比如 insert 操作从序列里弹出再插入如果总是插入到附近位置邻域范围就会比预期小很多搜索空间探索不充分方差自然大。排查方法是固定随机种子重跑同一组参数看是否能够复现结果。能够复现说明问题在随机性上多次取最优值即可不能复现则检查代码是否有全局变量或非确定性依赖。规范做法是把“多次独立运行取最优”作为最终交付策略同时对每次运行记录随机种子结果可回溯。5.5 现象五系统输出可行调度但车间执行不了程序给出的调度方案在算法内部是合法解拿到车间现场却发现两台机器同时加工了同一工件。这类问题的根源几乎都在解码实现与现场约束不一致比如同一台机器的换型时间、工件在不同工序间的运输时间没有建模或者机器宕机维修带来的时间窗口空缺没有考虑。实际作战里车间约束往往比教科书的 JSP 多几条最简单解决办法是把这些约束折算成工序加工时间的附加量或者压缩机器可用时间窗口再跑模拟退火而不是在解析结果后再人工修正。6. 验证与下钻用分批抽样法确认解的质量再谈超参数习惯模拟退火跑出来的解不能只看一次运行就交付。可靠的验证办法是做“分批抽样”固定一组参数用不同随机种子独立运行 10 次记录每次的 makespan取最小值作为最终结果同时观察这 10 个结果的分布。如果最大值和最小值相差在 3% 以内说明算法已经收敛稳定如果差距超过 8%说明要么参数太激进要么邻域设计有问题需要回头调整而不是硬碰运气。对于小规模 JSP 实例你可以把模拟退火的结果和穷举法结果直接对比确认解码器和邻域操作没有隐藏 bug。这一步特别推荐在刚开始写代码时做拿 3 个工件 × 3 台机器的算例跑出全部可行调度和 SA 输出的最小 makespan 对比对得上再往深处做。我见过太多团队把大规模数据跑出漂亮曲线最后发现解码器少了条约束结果整个数字都是错的。这种翻车非常伤没人愿意见到。我自己的一个习惯是每次调参前先固定随机种子然后只改一个参数记录目标值下降曲线而不是同时调好几个坑人的值。初始温度和降温系数就是最明显的两个“后悔药”参数一旦它们之间比例错位后面怎么加迭代次数都救不回来。先固定 alpha0.98、L 设为工序数 15 倍单独调初始温度确定初始温度后再单独调 alpha这样至少能分清是温度曲线的问题还是邻域结构的问题省掉大量无头绪的试错。参数确定后别忘了把最终方案用表格输出每道工序的开工时间、完工时间、所在机器附带机器的占用甘特图。车间的人不关心算法细节但你要能给出一份能直接看得懂的排产表让他们知道这套东西能落地而不是黑匣子。如果你把解码速度优化好了跑一次大规模调度从几分钟缩短到几十秒你自然会更愿意多试几组参数最终结果大概率也更好——这比纠结元启发式算法的理论选型更实际。希望这篇笔记能帮你少走些弯路把模拟退火在作业车间调度上真正用起来。如果有更细的调度约束比如并行机、设备维护窗口或者订单交期优先级基本思路仍然是建模成目标函数的惩罚项或约束条件模拟退火框架本身不需要大改。本文还有配套的精品资源点击获取