做车间调度的朋友应该都有这种感觉排产方案看着很合理一上线就被库存绊住脚。我做了几年离散制造车间的调度算法落地最常遇到的场景是——车间里十几台规格各异的机器几百个工件挤在同一个时段每台机器加工同一个工件的速度还不一样交期全线告急中间的在料品不能堆太多成品库容量也有天花板。这类问题在学术上有专门的名字叫无关并行机调度问题UPMSP我用Matlab里的模拟退火算法把它完整实现了一版重点就是处理在料品和成品库存都受约束、资源有限、每个工件还带截止日期的场景。这篇文章把建模思路、编码方式、参数调优和踩坑过程都摊开来讲适合正在做车间调度、生产排程或者刚开始接触UPMSP的同行参考。1. 为什么库存受约束让UPMSP从教科书难题变成实战难题1.1 UPMSP到底是什么机器不是等价替换件先把这个名词拆开。并行机调度有几种常见类型相同并行机Pm每台机器加工同一工件的时间完全一样机器之间只是数量差异。同型并行机Qm机器有统一的速度倍数快的机器对任何工件都快。无关并行机Rm也就是UPMSP每台机器对每个工件有独立的加工时间机器之间不存在统一速度比。UPMSP里的加工时间矩阵往往毫无规律。工件A在机器1上可能只要2小时在机器2上要8小时工件B恰好反过来。这种无关特性会让几乎所有贪心规则失效。你按选最快机器去分配看着局部最优但全局可能把关键机器堵死。打个比方裁缝店里的老师傅老张擅长做西装不擅长做旗袍小李正好相反。你每次只挑干活最快的师傅派单最后一定有人闲着、有人排队交期整体崩掉。1.2 在料品库存半成品堆积是隐形成本也是硬约束标题里写的在料品我习惯叫在制品WIP。它指的是已经从原料库释放出来、但还没完成全部加工的工件。车间调度里最容易被忽略的就是WIP。很多算法模型只算机器上在加工什么却不管机器旁边堆了多少半成品。实际场景中工序与工序之间要有缓冲区缓冲区满了前面机器再快也没用物料会把通道堵死。我处理过的项目里WIP上限可能是20个工件但贪心排产一下就积压到35个。这时候机器利用率看起来很高实际车间里已经乱成一锅粥。所以模型里必须加这么一条约束任意时刻处于已释放但未完工状态的工件数量不得超过WIP上限。这个约束看起来简单真正写进解码逻辑时才会发现它直接影响每个工件的开工时间安排。1.3 成品库存完工不等于能交货很多新手会把完工时间越短越好当成默认目标。但加上成品库存约束后这个直觉要改。工件加工完了交期还没到东西只能放成品仓暂存。仓库容量是有限的每多放一个就挤占后面工件的位置。如果排产方案一味追求快点做完结果就是把一堆工件提前做完放在仓库里吃灰既占库容又增加持有成本。这也是为什么目标函数里要同时加入提前惩罚earliness penalty。调度方案要做到的不是拼命赶而是刚好踩点。这个点在实际排产中特别重要很多教科书案例不讲但真实车间里这是每天都在发生的矛盾。1.4 资源约束和截止日期真正决定方案能否落地的两条线资源约束在UPMSP里通常指辅助资源。工件上机加工除了要占一台机器往往还需要模具、夹具、操作工或者专用刀具。这类资源数量有限比如车间里一共只有8套夹具那同一时刻最多允许8个工件上机加工跟机器数量无关。截止日期则是另一个维度。每个工件都有交期 d_i排产方案如果拖期要付违约金、要影响后续装配如果提前太多完成又会产生库存压力。所以目标函数里要对拖期tardiness和提前量earliness同时惩罚权重根据实际业务来定。这几条线叠在一起UPMSP就不再是教科书里那个单纯的最小化最大完工时间问题了而是一个多约束、多目标组合优化问题。这也是我选择用模拟退火的核心原因。2. 为什么选模拟退火UPMSP这类问题SA是真的合适2.1 组合爆炸精确算法在这里先出局先说结论UPMSP的规模稍微一大精确算法基本算不动。20个工件、5台机器时工件分配到机器的方案有5的20次方种每种机器分配下还要对每台机器上的工件排序排序数量级是n!。这种组合爆炸下分支定界、整数规划在工程规模下很难在合理时间内给出可行解。我见过有人硬用整数规划求解器跑100个工件的UPMSP跑几个小时连可行解都找不到更别说最优解。所以在工程落地场景启发式算法和元启发式算法是主流选择。2.2 模拟退火的物理直觉淬火和排产是一回事模拟退火Simulated AnnealingSA的灵感来自金属热处理先把金属烧到高温原子运动剧烈可以随便改变结构然后慢慢降温原子逐渐排列成低能量状态。对应到调度问题高温阶段算法允许接受比较差的解哪怕目标函数变差也接受目的是跳出局部最优。低温阶段算法只接受改进解逐渐收敛到一个较好的局部最优甚至全局最优。判断接不接受的公式是Metropolis准则P exp(-(f_new - f_old) / T)也就是说新解比旧解差得越多接受概率越低当前温度越高接受差解的概率也越高。这个机制特别适合调度问题——一开始多冒险后期少冒险最后稳稳收敛。2.3 SA相比GA和PSO在UPMSP上的优势我为什么不用遗传算法GA或者粒子群PSO这里把理由说清楚GA的核心操作是交叉和变异但调度问题用的是工序序列编码交叉算子设计不好很容易产生不可行解。比如两个工件在子代里重复出现另一个工件丢失。要处理这种问题就得加修复机制代码复杂度和调试成本都上去了。PSO本身是连续优化算法适合实数向量。调度问题是离散的要把PSO改造成离散版本粒子速度、位置更新的语义都不太自然。SA是单点搜索每次只在当前解附近小步改动邻域结构设计好后非常契合调度问题动一两处就能得到新方案的特点。SA实现简单参数少主循环几十行就能写完调试方便而且对约束处理友好——每次小步改动更容易保持解的可行性。当然SA也有局限单点搜索容易陷入局部最优对大规模问题收敛速度偏慢。所以我最终的方案里加了多随机重启机制后面会详细讲。3. 库存、资源和截止日期的建模目标函数怎么定3.1 先列参数把问题说清楚我建模时用的参数如下n工件总数每个工件只需在一台机器上加工一道工序。m机器总数并行工作每台机器同一时刻只能加工一个工件。p[i][j]工件i在机器j上的加工时间。d[i]工件i的截止日期。WIP_max在料品/在制品库存上限。F_max成品库存容量上限。R_max辅助资源总数比如8套夹具。r[i]工件i加工时需要占用的辅助资源数量。为了讲清楚我用一个10个工件、3台机器的小算例来演示。加工时间矩阵大概是这样的单位小时工件机器1机器2机器3截止日期J159718J2861024J3711420...............每台机器加工不同工件的时间完全没规律这就是无关。3.2 解码时怎么处理库存和资源约束调度算法解码时并不是简单地把工件按序列扔到机器上。我的解码逻辑是这样的按工件序列顺序取出当前工件找到给它分配的机器。计算这台机器的最早可用时间以及该工件所需辅助资源的最早可用时间取两者最大值作为最早可开工时间。关键步骤检查开工后WIP数量是否超过上限。如果会超就把开工时间往后推迟直到有工件完工释放WIP为止。同样要检查成品库存。如果该工件完工后交期还远不仅要占着WIP完工后还要暂存到成品仓成品仓满了也得推迟开工。把工件安排到机器上更新机器空闲时间、资源占用时间、WIP计数器、成品库存量。这一步是整个算法的核心。很多SA实现效果不好问题就出在解码时只算机器时间没算库存和资源时间。3.3 目标函数拖期、提前、库存一个都不能少我用的是加权多目标min Z w1 * 总拖期 w2 * 总提前量 w3 * 平均WIP持有成本总拖期 Σ max(0, C_i - d_i)C_i是工件i的完工时间。总提前量 Σ max(0, d_i - C_i)。平均WIP持有成本 统计整个调度周期内WIP数量的均值乘以持有成本系数。资源约束和库存约束本身不放到目标函数里而是作为硬约束在解码时直接处理。这样做的好处是SA搜索过程中永远不会出现破坏约束的不可行解只要解能解码出来就是可行的。3.4 权重怎么定业务优先级和量纲都要考虑w1、w2、w3的取值直接决定解的风格如果车间最怕拖期w1要远大于w2比如w110、w21。如果成品库存很紧张w3就要调高逼算法不要把工件过早做完。注意量纲匹配拖期和提前都是时间单位但WIP持有成本换算成元/小时的话可能需要把时间目标乘以单位成本系数。我一般先用w11、w20.1、w30.01跑一遍看解的目标值结构再根据实际业务调整。不要一上来就追求完美权重先让算法跑通再调优。4. Matlab实现核心编码、邻域与退火流程4.1 解编码工件序列加机器分配我用的是两段式编码一个解由两个等长向量组成sequence向量长度为n是工件编号的一个排列表示所有工件的优先级顺序。assign向量长度为n每个位置对应工件分配的机器编号。例如sequence [3, 1, 2, 4]assign [2, 1, 3, 2]表示工件3在机器2上加工工件1在机器1上加工工件2在机器3上加工工件4在机器2上加工。至于每台机器上多个工件的先后顺序由它们在sequence中出现的先后决定。这种编码的优点是任意改变sequence或assign得到的新解在结构上仍然是合法的——每个工件只加工一次不会出现遗传算法里那种工件重复或缺失的问题。4.2 邻域结构三个操作按比例混合SA的搜索质量很大程度上取决于邻域设计。我用了三种邻域操作交换swap随机选两个位置交换它们对应的工件编号。插入insert随机选一个工件插到另一个位置后面。重分配reassign随机选一个位置把该工件从当前机器改到另一台机器上。三种操作的效果不一样。swap和insert主要改变调度顺序对库存和交期影响更直接reassign主要改变机器负荷分配对绕过瓶颈机器很有用。我实测下来比较稳定的比例是swap:insert:reassign 2:1:1。每次生成邻域时按这个概率随机选一种操作。比例可以根据问题规模微调——机器数量多时reassign的比例可以适当提高。4.3 模拟退火主循环核心代码框架长这样function bestSol sa_upmsp(data, params) currentSol init_solution(data); % 随机初始解 currentObj objective(currentSol, data); bestSol currentSol; bestObj currentObj; T params.T0; while T params.Tend for k 1 : params.L newSol neighbor(currentSol, data); newObj objective(newSol, data); delta newObj - currentObj; if delta 0 || rand() exp(-delta / T) currentSol newSol; currentObj newObj; if newObj bestObj bestObj newObj; bestSol newSol; end end end T params.alpha * T; end end这段代码没什么玄乎的真正花时间的是objective函数内部的解码也就是第三节讲的库存和资源检查逻辑。4.4 工程化的关键细节缓存目标值每次算完目标函数后保存别在邻域搜索时重复全量计算。解码复杂度不要每次解码都从头扫描所有机器用向量记录每台机器的空闲时刻和维护一个WIP时间表复杂度可以压到O(n*m)。用结构体封装解Matlab操作struct数组比操作一堆零散变量清晰得多尤其在调试时能一眼看清楚每个解的sequence、assign和机器空闲表。5. 调参和实验心得参数组合比算法本身更容易翻车5.1 四个关键参数的经验范围参数含义经验范围我的建议T0初始温度100~1000按初始解目标值量级估算取目标值的10~50倍alpha降温系数0.85~0.98小规模用0.98收敛稳定大规模想提速可以0.95L每个温度下的迭代次数100~1000我用nm20左右10工件3机器就是600Tend终止温度0.01~1取T0的千分之一左右太小浪费时间初温是新手最容易搞错的。初温太低算法一开始就不接受差解等于变成爬山法很容易陷在局部最优里。我建议这样验证随机生成一批初始解计算它们目标值的标准差初温取标准差的5~10倍。这样一开始接受率大概在0.7~0.9是健康的退火起点。5.2 收敛曲线怎么判断看接受率比看目标值更直接退火初期接受率应该在0.7以上说明解在充分乱跳。退火中期接受率逐步降到0.2~0.4开始趋于局部精调。退火后期接受率接近0.05以下基本只接受改进解。如果跑到后期目标值还在大幅波动说明降温太快退火效果没发挥出来应该提高alpha或者加大L。5.3 多随机重启比单链硬撑更稳单次SA跑一万次迭代很容易在某个局部最优附近反复打转。我改成跑10次独立SA每次从随机初始解开始温度从高到低跑1000次迭代最后取10次里最好的解。这个方法成本低、代码改动小效果却非常明显。对我那个15工件4机器的试验算例单次长链和10次短链找到的最好解差别大约在5%左右10次短链明显更稳。5.4 一个实测算例的对比结果我用15个工件、4台机器的小算例随机生成加工时间5到30小时截止日期按平均加工时间的1.2倍生成WIP上限设为6成品库存上限设为8辅助资源上限4。用经典的EDD规则按截止日期最早优先排产和本文SA各跑一组结果对比如下一次运行的实际输出排产方式总拖期总提前量综合目标ZEDD规则31288328SA本文18967212SA的综合目标比EDD改善约35%。当然这不是说SA永远比规则好——规则算法秒出结果SA要跑几十秒。但在这种多约束场景下规则算法根本没法同时照顾库存、资源和交期SA的优势就体现出来了。6. 源码结构和使用说明6.1 文件结构这套Matlab实现的代码按功能拆分如下main_sa_upmsp.m主程序入口负责读入数据、设置参数、调用SA。init_solution.m生成随机初始解。decode_solution.m对给定解进行解码输出每台机器上的工件序列、开工时间、完工时间。cal_objective.m计算目标函数值内部调用decode_solution。gen_neighbor.m按比例生成三种邻域操作。plot_gantt.m画甘特图并输出结果。data_case.m生成测试数据包含加工时间矩阵、截止日期、资源参数等。6.2 直接运行的流程在Matlab里进入代码目录先运行data_case.m生成算例数据再运行main_sa_upmsp.m就能看到结果。如果你要换自己的数据只需要修改data_case.m里的p矩阵、d向量、WIP上限、成品库存上限和辅助资源上限即可。输出结果包括最佳调度方案每台机器上依次加工哪些工件。每个工件的开工时间和完工时间。总拖期、总提前量、WIP均值和综合目标值。甘特图。6.3 二次开发建议想把这个框架用到自己的场景主要看三条路换目标函数在cal_objective.m里增加新的惩罚项比如换线成本、能耗成本。加约束在decode_solution.m里加判断逻辑比如机器可用时间窗、禁止某工件在特定机器上加工。换邻域操作在gen_neighbor.m里加新的邻域生成方式比如交换两台机器上的整段工件序列。编码和解码是整个框架的关键只要能生成合法解、算准目标值后面换任何算法都很方便。7. 踩过的坑和最后的经验7.1 库存约束最坑的点解码顺序不等于加工顺序我最初实现时踩过一个很隐蔽的坑解码时按sequence的顺序逐个安排工件但忽略了前一个工件还没开工后一个工件已经把成品库存占满的情况。后来发现正确做法是每次安排完一个工件要立即模拟推进时间轴把在t时刻已经完工的工件从WIP里释放把已经到交期的工件从成品库存里清出去。顺序搞反库存约束就等于没加。建议在decode_solution.m里用事件驱动的方式维护时间轴记录每个完工时刻按时间顺序释放WIP和成品库存再判断能否插入新工件。7.2 甘特图别只画机器要把库存占用一起画刚开始我画的甘特图只有机器和工件结果发现调度方案看起来挺好但完全看不出库存爆没爆。后来我把WIP数量随时间变化曲线和成品库存曲线画在甘特图下方一眼就能看出约束有没有被违反也方便向车间管理人员解释方案为什么这么排。画WIP曲线其实很简单解码时把每个工件的开工时间、完工时间记录下来按时间轴统计区间内的在加工工件数量就能得到。7.3 参数稳定性比最优解更重要做了一段时间调度算法后我的体会是对工程落地来说算法稳定给出一个可行的、比手工排产好的方案远远重要于追求所谓全局最优。车间里的数据天天在变工件插单、机器故障、物料延迟都是常事。这个SA框架的好处是参数调好之后换一批数据不需要重新大改跑一遍就能给出可用的排产建议这比任何花哨的优化都实在。最后分享一个小技巧实际使用中可以把SA的结果当成初始方案再让生产计划员在甘特图上手工调几个工件因为算法不知道车间里那些写在老师傅脑子里的潜规则。人机结合才是调度系统真正能落地的方式。