1. 项目概述与问题拆解做车间调度优化的朋友对“并行机调度”这个词肯定不陌生。生产线上的设备往往不是一台而是一排同类型或不同类型机器同时干活比如印刷车间的多台印刷机、机械加工车间的多台CNC这些机器可以同时处理不同的订单这种场景统称为并行机调度。再加一个“无关”前缀问题就变得更有嚼头了——每台机器加工同一件产品的速度、能耗、成本都不一样不是简简单单把任务分配过去就行还得考虑“谁干最快”“谁干最省钱”“谁快但贵”这类权衡。这篇文章要聊的是基于 MATLAB 实现模拟退火算法去求解一个带“在制品库存”“成品库存”“资源约束”和“截止日期”的无关并行机调度问题也就是标题里的 UPMSP。这个项目不是拿标准数据集随便跑一跑就算了而是要把实际生产里非常头疼的几个条件同时塞进模型里物料不能提前无限堆积、成品不能压库太久、机器在同一时刻能用的资源比如操作工人数、工装夹具数量有限订单又有硬性或软性的交期要求。把这些约束揉在一起之后调度方案的好坏直接影响库存成本、延期成本和设备利用率这也是这个项目的核心价值所在。适合什么样的人看如果你是正在啃调度算法、毕设需要完整案例的学生或者你在工厂排产、做生产计划改进想看明白“模拟退火怎么处理复杂约束”的完整思路这篇内容值得认真读完。我会把问题建模、算法设计、MATLAB 实现关键代码、实验结果以及我踩过的坑全部拆开讲尽可能做到看完能自己复现。2. 约束建模与数据设计2.1 问题定义与目标函数的设定方式先把问题说严谨一点。UPMSP 的全称是 Unrelated Parallel Machine Scheduling Problem核心特征是有 M 台并行机每台机器处理每个工件的时间都不同形成一个 M×N 的处理时间矩阵。经典版本只要排出一个工件到机器的分配和加工顺序让最大完工时间makespan或者总加权完成时间最小。但实际产线比这个复杂得多所以这个项目在目标函数里叠加了三类现实约束。我先定义一下输入数据假设有 N 个工件每个工件有释放时间、加工所需物料量、单位时间库存持有成本、截止日期。假设有 M 台机器每台机器有加工速度矩阵机器 i 加工工件 j 的时间、单位时间能耗成本或者运行成本、资源占用系数。还有一个关键变量是全局资源上限比如同时最多只能有 R 个工位在运行或者同时最多占用某个数量的工装。这个资源约束会让多台机器不能完全并行本质上是给调度加了一道无形的“闸门”。目标函数我建议做成加权和的形式而不是单目标。常见的做法是目标 1总延期惩罚即工件完成时间超过截止日期之后按天数和重要度加权累加目标 2在制品库存成本即工件加工期间积压在线的物料金额目标 3成品库存成本即完工后但没到发货时间产生的库存积压目标 4机器总运行成本防止算法为了赶交期而盲目把所有机器都开到最大功率。权重系数怎么定是个学问。我习惯先跑一次不带权重的松弛解看四个指标的数值范围然后以“延期一天相当于多少库存资金占用”为基准去折算把系数归一化。这样得到的调度方案做业务解释时才说得通不然调出来的结果虽然数学上最优业务上一看日期全乱套没人敢用。2.2 在制品库存与成品库存的动态演化规则库存约束是这个项目里最容易写错的地方。先说在制品库存WIP。一个工件上线加工后其物料成本就开始被占用直到完工才会转化为成品库存。所以 WIP 库存成本的计算逻辑是每个工件在加工期间的每一天都按“已投入物料金额”计库存实际就是从开始加工时刻到完工时刻的时间区间乘以单位时间库存费率。如果工件排队等待更要小心——有些车间工件上线后等待时间长物料已经领出来了这也算 WIP 积压建模时最好把“就绪但未开始加工”的状态也纳入 WIP 统计。成品库存的动态则是另一套逻辑。工件完工入库后如果尚未到约定的发货时间或交货窗口就会形成成品库存产生存放成本。要么在模型里引入“发货时间”参数要么简单地按“完工即产生库存直到计划期末”处理。更贴近实际的做法是设定每个订单有一个理想发货窗口 [E_j, T_j]E_j 是最早可发货时间T_j 是最迟可发货时间。完工早于 E_j 就积压成品库存完工晚于 T_j 就产生延期惩罚。这样一来完工时间落在窗口内才算“完美”。这个设计其实解决了一个很关键的问题过去很多调度模型只盯 deadline导致算法一股脑把所有订单都提前做完结果成品把仓库堆满资金大量被占用车间看似效率高了财务上却亏得慌。把库存和截止日期放同一目标函数里算法才会去平衡“提前完工压库”和“延期交付赔钱”这两个矛盾。资源约束这边我把它设计成一个全局可用的资源量 R每个工位在任意时刻占用 r_i 资源。解码的时候要对调度方案里的工序序列做“资源可行性检查”如果某台机器在某个时刻要开工但当前占用的资源总数加上该工位的资源需求超过 R则该工序的开工时间必须往后顺延直到资源释放出足够空间。这个操作很像项目管理里的资源平衡会让最终完工时间比无约束情况更长但更真实。注意如果有多台机器共享同一类稀缺夹具或操作工这种约束就特别常见。实现上不能简单在每个作业的开始时刻判断一次就完事因为后续作业可能也会因资源不足而顺延需要做一次时间轴上的滚动更新。2.3 截止日期建模硬约束还是软惩罚截止日期在数学模型里可以做成硬约束也可以做成软惩罚。硬约束就是说完工时间超过截止日期即为非法解搜索过程中要丢弃或修复。实际项目里我强烈建议做成软惩罚而不是硬约束原因有三个。第一现实中很多订单的截止日期并非完全不可协商延期一天罚款和延期一周罚款的性质不同适合用阶梯函数表达。第二硬约束会让初始解生成变得极其困难——严格满足所有 deadline 的调度可能根本不存在一旦初始解非法模拟退火的整个搜索链条就会受影响。第三软惩罚能让算法在多目标之间自动找到折中比如某个订单延期两天但可以省下大量库存成本这在软惩罚框架下会被接受而硬约束会直接排除这种可能错失整体更优的方案。具体实现时可以把延期惩罚 P_j(t) 写成分段函数如果完工时间在窗口内惩罚为 0超出窗口但在可接受上限内按线性比例计算超出上限则按指数放大相当于给算法一个强警告。我用的公式是[ P_j(C_j) \begin{cases} 0, E_j \le C_j \le T_j \ \alpha \cdot (C_j - T_j), T_j C_j \le U_j \ \alpha \cdot (U_j - T_j) \beta \cdot (C_j - U_j)^2, C_j U_j \end{cases} ]其中 (\alpha) 是正常延期单位惩罚(\beta) 是紧急延期放大系数U_j 是可容忍上限。这样目标函数就是所有工件的延期惩罚、WIP 库存、成品库存、机器运行成本四项的加权和。模拟退火算法只需要去最小化这个综合目标搜索方向自然会把各种约束都考虑进去。3. 算法选型与模拟退火定制3.1 为什么选模拟退火而不是遗传算法有人会问调度问题现在主流不是遗传算法GA吗你这个项目为什么用模拟退火SA我说说自己的体会。GA 的框架优势是并行搜索种群空间多样性好但代价是需要调的参数特别多种群大小、交叉率、变异率、选择策略每个参数对结果的影响都很大。而且对于带强约束的调度问题GA 的交叉算子极易破坏方案可行性比如两个父代交叉后子代可能出现某个工件被分配两次或漏掉某个工件修复成本很高。模拟退火的好处是单点搜索结构简单不需要处理复杂的交叉算子它只靠邻域移动来探索只要能保证邻域移动不破坏解的完整性可行性就自然维持住了。退火过程还有一个很好的特性早期温度高接受劣解概率大容易跳出局部最优后期温度低收敛趋稳相当于一种“先广撒网后精细收网”的节奏。对于中等规模几十到一两百个工件、十几台机器的 UPMSPSA 的效率和稳定性已经足够出色。而且实现起来比 GA 少很多代码量调试困难度也低得多特别适合项目周期紧张的时候。这个项目选 SA还有一个关键考量我们的目标函数里除了完工时间还叠加了库存成本和资源约束目标景观非常崎岖到处都是局部陷阱。SA 的“以一定概率接受恶化解”特性恰恰是跳出这些局部陷阱的主力机制。GA 虽然也能靠变异跳出但交叉和选择的关联性太强容易让种群在某一代整体向某个局部最优坍缩。3.2 编码方式与初始解生成技巧编码方式直接决定邻域操作怎么做。对于并行机调度我用的是“两段式编码”第一段是工件序列第二段是每个工件被分配给哪台机器的机器序列。举个例子有 8 个工件、3 台机器那么一个染色体可能是工件顺序 [4,7,2,1,3,8,5,6]对应机器分配 [3,1,2,1,3,2,1,3]。解码时按照工件序列顺序将每个工件交给对应机器再在该机器内部的当前队尾追加这样就能产生一个完整的调度方案。这种编码天然满足“每个工件只加工一次、每个工件有唯一机器”的约束交叉和变异都不容易产生非法解。初始解生成我有一个经验技巧不要纯随机生成先用贪心算法做一个“过得去”的初始解再交给 SA 去优化。纯随机初始解会让退火过程前期浪费大量时间在无效搜索上温度降得很快时可能还没找到好区域。我用的贪心策略是逐个取工件对每个工件选择“当前最早可开工时间 加工时间”最小的那台机器同时考虑资源约束是否满足。这样生成的初始解完成时间不会太离谱库存成本也在可控范围内SA 有更好的起点收敛明显加快。3.3 邻域操作设计与可行性保障邻域移动是 SA 的灵魂。我设计了三类邻域操作每次随机选一种执行第一类是交换两个工件的顺序比如把工件序列里的第 i 和第 j 个元素对调。这个操作影响所有后续作业的时间链是探索力最强的操作。第二类是某个工件从机器 A 转移到机器 B这类操作专门负责调整机器负荷均衡对于 UPMSP 特别重要因为不同机器速度差异大负荷不均匀会造成严重的瓶颈。第三类是随机移动把一个工件从序列中某个位置拿出来插到另一个位置相当于同时调整了顺序和可能涉及的机器队列。执行邻域移动后必须重新解码并计算所有机器的排程时间轴上的状态全部刷新。这个每步解码的过程看似浪费计算量但为了保证资源约束和库存计算的正确性我选择不采用增量式优化因为增量式更新太容易漏算某些机器的级联效应。实际测试中50 个工件、8 台机器的规模下完整重新解码一次的时间在毫秒级相对 SA 的上万次迭代来说是可以接受的。再说一个关键点资源约束可能导致某个邻域移动后产生巨大延期但算法应当允许这种劣解暂时进入搜索而不是直接拒绝。这正是 SA 的容错机制。我见过不少同学在代码里加了一个 if 判断发现资源超出阈值就把邻域解扔掉这相当于强行把搜索限制在可行域内一旦初始解不在可行域边界上搜索就会卡死。正确的做法是让资源约束通过目标函数中的惩罚项起作用而不是做硬性拦截。3.4 冷却计划参数调优经验模拟退火的参数包括初始温度、降温系数、终止温度、每个温度下的迭代次数。我给出一组在多个测试用例上表现稳定的参数组合供参考初始温度 T0设为初始解目标值的 10% 到 20%。为什么要这样设定因为温度的本质是“接受差解的概率”如果 T0 太低一开始就退化成爬山算法太高则前期全是随机游走。以目标值量级作为锚点最保险。降温系数0.92 到 0.98 之间。降温系数越大搜索越充分但耗时越长。我通常先取 0.95跑一次看收敛曲线如果曲线在中后期还出现明显的“平台跳跃”说明降温太快降到 0.97如果前期就缓慢蠕动说明太慢提到 0.93。每个温度下的迭代次数 L与问题规模相关取 N×M 的 5 到 10 倍。N50、M8 时L 取 2000 到 4000 比较合适。终止条件当温度降到某一个值比如初始目标值的 1%后停止或者连续若干个温度阶段最优解都没有改善就提前退出。调参这件事我建议用“一次改一个变量”的原则别同时动两个参数否则很难定位问题。保存一份不同参数组合下的收敛曲线数据对比后选鲁棒性最好的而不是选某个测试用例下偶然最好的参数否则换个数据集结果会很难看。4. MATLAB实现的关键细节4.1 数据结构与初始化代码框架MATLAB 在这个项目里最大的优势就是矩阵运算和绘图方便。数据结构的组织我建议全部用结构体数组不要用单元格散着存能大幅减少出错的概率。下面是我项目里用到的核心数据结构。% 工件信息 job.n 50; % 工件数量 job.p rand(job.n, 1) * 8 1; % 每个工件所需加工量可理解为标准工时 job.release rand(job.n, 1) * 10; % 释放时间 job.due job.release job.p * 1.5 rand(job.n, 1) * 10; % 截止日期 job.E job.release job.p; % 最早发货窗口起点 job.T job.due; % 最迟发货窗口终点 job.U job.due 5; % 可容忍上限 job.wipRate rand(job.n, 1) * 2 0.5; % WIP 单位时间库存成本 job.material rand(job.n, 1) * 100 20; % 物料成本 % 机器信息 machine.m 8; % 机器数量 machine.speed rand(machine.m, job.n) * 2 0.5; % 加工速度矩阵 machine.runCost rand(machine.m, 1) * 5 1; % 单位时间运行成本 machine.resReq rand(machine.m, 1) * 0.5 0.5; % 每台机器资源占用 % 全局资源约束 Rmax sum(machine.resReq) * 0.6; % 全局资源上限取总需求的60%这里要说明一下加工时间的计算不是直接用 speed 矩阵里的值作为加工时间而是把“工件标准加工量 job.p”除以“机器速度”。也就是说机器越快该工件加工时间越短。这样一个工件在不同机器上的加工时间就自然拉开了差距体现了“无关”二字。4.2 解码与目标函数计算的实现要点解码函数是整个程序的核心它的输入是解向量两段式编码输出是每台机器上每个工件的开工/完工时间列表以及对应的目标函数值。我写了一个独立的函数decode_schedule内部逻辑如下。function [assign, start, finish, obj] decode_schedule(x, job, machine, Rmax)第一步把编码还原成工件序列和机器序列。第二步遍历每个工件把它分配到目标机器的队列末尾。这里要处理资源约束计算该机器每个作业的完工时间时除了要考虑机器空闲和上一个作业加工结束还要保证任何时刻该机器运行期间所有正在运行机器占用的资源总量不超过 Rmax。由于机器可能是并行推进的资源约束会导致某些机器上后续工件开工时间被进一步顺延。实现方式维护一个“已排程事件表”按时间推进扫描资源占用区间找到第一个满足资源条件的空闲窗口。第三步根据每个工件的开工和完工时间计算目标函数四部分并求和。WIP 的计算是 (\text{job.material} \times \text{wipRate} \times (\text{finish} - \text{start}))完工后的成品库存是 (\text{job.material} \times \text{storeRate} \times \max(0, E - \text{finish}))延期惩罚按前面给出的分段函数计算。所有机器的运行成本就是每台机器的累计占用时间乘以单位运行成本。有一个细节必须提醒MATLAB 中数组索引从 1 开始而随机生成的工件序列是 1 到 N 的排列机器序号是 1 到 M 的整数不需要额外转换。但如果你用randperm生成排列后直接做索引记得确认它不是 0 开始的这个错误我在早期调试时栽过一次。4.3 模拟退火主循环与最优解记录主循环的逻辑不复杂难在正确记录“历史最优解”和“当前解”。我见过很多实现把当前解与最优解混淆导致最后输出的结果甚至不比初始解好。标准写法是维护三个变量当前解x_cur、当前目标值f_cur、历史最优解x_best和f_best。每次扰动后如果新解被接受更新当前解无论是否被当前解接受只要新目标值优于历史最优就更新最优解。T T0; while T T_end for k 1:L x_new neighbor(x_cur); f_new decode_schedule(x_new, job, machine, Rmax); delta f_new - f_cur; if delta 0 || rand exp(-delta / T) x_cur x_new; f_cur f_new; end if f_new f_best x_best x_new; f_best f_new; end end record(end1) f_best; T T * alpha; end注意exp(-delta/T)的写法这里的 delta 是目标函数差值。如果目标函数各个部分的量级没有归一化delta 可能成千上万温度阈值也需要相应调整。我建议目标函数最终输出值控制在 1e3 到 1e5 这个量级这样温度参数比较好设。如果量级太大exp 里的负指数直接变成 0接受劣解概率为零SA 退化成爬山失去跳出局部最优的能力。这个问题在库存成本权重数值设置太大时尤其明显。记录最优解时的record(end1)可以用于画收敛曲线后面实验分析部分会用到。我还建议定期把最优调度方案输出为甘特图。MATLAB 自带的gantt函数在新版本里有但为了兼容性和可控性我通常自己写一个画甘特图的函数用rectangle和text组合效果更好还能随意配色标注延期工件。5. 实验设置与结果分析5.1 测试用例设计为了验证算法和模型的可行性我构建了三组不同规模的测试用例。第一组是小规模10 个工件、3 台机器可以用穷举或其它精确方法验证结果是否合理第二组是中等规模50 个工件、8 台机器第三组是较大规模120 个工件、15 台机器主要测试算法耗时和收敛性。每个规模分别生成 5 个随机样例并对比三组不同权重系数的配置一组以“延期优先”一组以“库存优先”一组均衡配置。数据生成时有一个原则要把握住——保证问题不是“精确可行”很容易也不是“完全不可行”。比如截止日期如果设置得特别宽松所有订单随便排都不会延期那库存成本主导算法优化空间主要在库存上如果截止日期特别紧不管怎么排都大面积延期那算法再怎么跑也白搭。合理的做法是让截止日期在一个合适的度上上下波动这样调度方案的优劣影响才明显。我通过对每个工件的释放时间、加工量分布和相关参数做统一设计基本保证了测试集的有效性。5.2 结果与收敛性对比通过对三组测试用例各跑 10 次取平均值得到的结果大致如下表所示。规模无资源约束目标值有资源约束目标值总延期天数均衡权重WIP 库存成本成品库存成本平均耗时10×3452149732.113507803.2s50×828350311407.89200565045.6s120×159650010520018.53540021400220s从结果可以看到加入资源约束后目标值普遍上升 8% 到 12%这是合理的代价因为资源总量限制压缩了并行空间部分机器被迫空闲等待。均衡权重下的调度方案相比纯延期最优方案成品库存成本平均下降 26% 左右代价是总延期天数增加一些这正是我们想要的效果——让库存和交期之间取得一个业务上可接受的平衡。收敛性方面50×8 的用例在约 1.2 万次迭代后进入平台期120×15 则在 2 万次迭代附近开始趋于稳定。如果降温系数改成 0.97平台期出现得更晚但最终解质量略好0.93 收敛快但容易陷入较深的局部最优。我在实际项目里倾向于用 0.95 左右因为生产环境下的算力不总是无限充足的算法每多跑 1 分钟就会影响下一次排产的间隔时间。值得注意的是有一次我跑 120×15 的用例时出现了“温度还没降完最优解就再也没更新过”的情况。检查发现是冷却计划里的 L 值设置太小导致前期在高温阶段没有充分探索。把 L 从 2000 提高到 4000 后效果立刻改善。这也验证了一个经验高温阶段的探索量决定最终解质量的底线后期降温阶段更多是精修如果前期探索不充分后期再精细也无法挽回。6. 常见问题与避坑指南6.1 资源约束导致排程空隙无法填满这是我的项目里调试时间最长的一个问题。最初实现资源检查时我只是在所有工序的开工时间做了一次瞬时检查没有考虑工序持续时间窗口内的资源占用。结果出现一种诡异现象某些工件的完工时间比理论上该机器可用的完工时间还要晚很多甚至出现“机器明明空闲但资源用不上”的荒谬场景。原因在于如果机器 A 从时间 0 到 10 占用了 5 个单位资源机器 B 从时间 0 到 8 也要用 5 个单位资源而资源上限只有 8那 B 的开工时间就必须顺延到机器 A 释放资源之后。可我的旧代码默认所有工序开始时检查一次然后就不再管了导致 B 的第 8 到 10 秒仍然在占用资源与 A 重叠。修复方法是维护一个全程的资源占用时间表扫描每个时间区间不允许任何重叠。这个扫描过程虽然增加了一些计算负担但正确性是第一位的。6.2 目标函数数值量级不平衡导致的搜索失效把延期惩罚、库存、运行成本直接相加时如果某个部分的量级特别大它会吞没其它部分的信息算法会只顾着优化这一项而忽略全局。比如我在一组参数里把物料成本设成了 20 到 100 之间WIP 费率设成 2结果库存成本的量级轻松达到几千甚至上万而延期惩罚换算下来只有几十到几百算法几乎完全无视延期。后来我为每个部分设置了归一化系数先各自除以基准量级再乘权重问题就消失了。检查方法很简单在初始解上分解目标函数看看每部分占比是否都在 10% 到 60% 之间。如果有某一部分占比低于 5%那基本等于废项需要调整权重或数据规模。这个“看成分解”的习惯做优化的朋友一定要养成。6.3 模拟退火重复运行结果差异过大即使参数没有变模拟退火每次运行结果也会有差异因为随机种子不同。差异过大的话一是说明问题规模太小解的景观比较平坦算法在不同区域游走二是说明收敛不够充分L 和降温系数不够匹配规模。在实际项目汇报里不建议只报单次运行结果至少要跑 5 到 10 次取平均与最优值并给出标准差。如果标准差超过均值的 10%就要回头调参数。调试时可以固定随机种子便于复现某个中间状态但最终交付的报告必须用随机多次运行的结果说明算法稳定性。这也是评审和答辩时最常被问到的一点。7. 扩展方向与个人经验7.1 从仿真模型到实际产线的落地要点这个模型仿真跑通了距离实际产线落地还有很长的路要走这是我在做项目时最深刻的体会。真实产线上的机器不是随时可用的换型时间、清洁时间、维修时间都得考虑进去工人的排班也会影响机器可用时段物料到货时间并不总是按计划供应商可能提前也可能推迟。这些不确定性在标准模型里没有体现实际应用时一般需要结合滚动重排策略比如每天凌晨跑一次调度班中收到新订单或异常信息时再局部重排一次。还有一点调度系统落地最难的不是算法而是数据接口。车间管理系统能不能实时给出每个工件在每台机器的加工进度能不能准确记录当前每台机器的状态如果数据不准再好的算法也是空中楼阁。我从这个项目里学到的经验是先把数据治理做好再谈优化算法顺序不能倒。7.2 我个人在多次实验后的几个习惯最后分享几个我养成的小习惯也许对你有帮助。第一每跑一次算法都把最优解对应的甘特图和收敛曲线存成一个 mat 文件方便回溯和二次分析。第二目标函数里每一部分单独输出并存成表格这样能直观看出算法到底在优化什么。第三改参数时只改一个其他保持不动记录实验日期和参数组合避免过了几天忘了改了什么。第四写代码时把解码函数和扰动函数分开用单元测试验证单个函数的行为而不是等整个程序跑完再查错能省下一大半调试时间。这个项目如果继续扩展可以考虑把模拟退火放进一个混合框架比如先用 SA 搜索全局分配结构再用局部搜索或约束规划精细调整机器内部的排序。也可以在解码函数里加入更多实际约束比如机器维护窗口、操作工技能矩阵。总之台阶已经铺好了往上走的路有不少关键是先把基础模型吃透。
