做过钢结构车间生产管理的朋友应该都遇过这种场面行车吊着三吨重的钢梁在天上挪切割机前排队七八张板两台焊机一台在等图纸一台忙不过来喷漆线下午四点半要收线可构件还没打砂。排产全凭车间主任按经验和直觉插单一来整个下午的计划就得推倒重来。这个问题放到学术里叫作业车间调度问题Job Shop Scheduling Problem, JSP是典型的NP-Hard问题规模稍大精确算法就跑不动。我这次用MATLAB实现了一个基于遗传算法的车间生产调度求解器拿钢结构件制造车间的真实尺度数据做例子把目标函数怎么设、染色体怎么编码、遗传算子怎么写、参数怎么调整套逻辑完整走一遍。做制造数字化、研究智能优化算法或者正在被排产折磨的朋友这篇应该能给你一个可以直接参考的底子。钢结构件制造车间不是一条固定节拍的流水线它的调度问题有很强的自身特点。很多做算法的人一上来就套用经典JSP或者柔性流水车间模型结果现场数据一对就发现对不上。所以第一步不是写代码而是把车间里到底发生了什么看清楚。1.1 三个让人头疼的车间特征第一构件规格差异巨大。一个订单里可能同时有箱型柱、H型钢梁、十字柱、支撑杆、连接节点板、檩条尺寸从两三米到二十几米重量从几十公斤到十几吨都有。不同构件的工艺路线相似又不完全相同所以没法简单按产品线划分车间产能。第二工序路线“同中有异”造成调度冲突。箱型柱要做切割、组立、焊接、钻孔、抛丸、涂装六道工序支撑杆可能只要切割、焊接、抛丸、涂装四道连接板直接切割、钻孔、涂装就完了。大家都要抢切割机、抢焊机、抢喷漆线但各自加工顺序不完全一样。这不是流水线上分批那么简单而是多类工件在共享设备上互相穿插。第三设备物理约束和等待成本高。大型构件跨工序转运靠行车行车忙不过来就得等焊接工序动辄几十个小时是明显瓶颈切割机前面排得不好板子堆满地连脚都下不去。再加上每批构件交期不同紧急插单是家常便饭。这些特征叠加在一起决定了钢结构车间排产本质上是一个多工件共享有限设备、工艺路线有交错的组合优化问题。靠Excel手工排、靠老师傅经验判断工件数上了十几之后基本就排不动了即使排出来也没法保证接近最优。1.2 为什么选遗传算法而不是精确求解或简单规则车间调度问题的规模可以先用排列组合感受一下。按本次实例的规模6个工件、6台设备各工件工序数从3道到6道不等所有可行工序排列有超过27万种。如果工件数到20个这个数字直接爆炸到天文级别分支定界这类精确算法在合理时间内基本算不完。20个工件对钢结构车间来说也就是一周左右的生产量。精确算法不现实那用调度规则行不行EDD、SPT、FIFO这些规则实现简单、速度快很多场景下能给出可用的方案但本质上是贪心策略容易被局部最优绊住。比如SPT会让小构件全部插队结果大构件交期被严重耽误。规则排产长远看不够稳。遗传算法是另一条路不追求一步到位而是在种群层面上做“选择-交叉-变异”的循环做全局搜索。它不要求目标函数可导不要求问题有特别强的数学结构对约束的表达非常灵活。配合MATLAB的矩阵和cell数组操作解码和迭代代码可以写得比较短非常适合做原型验证和方案推演。这是我选择它的直接理由。1.3 本次要解决的问题定义先把目标说清楚给定一批订单的构件清单、每类构件的工艺路线和加工时间求解每个工序在哪台设备上、什么时候开始加工使得整批构件的最大完工时间Makespan最小。暂不讨论总拖期最小、设备负载均衡这类多目标问题那是后续扩展方向。单目标Makespan的好处是直观车间最关心的就是这批活到底什么时候能全部下线。2. 把车间约束写成算法能算的数学模型建模不复杂但有几个地方很容易想当然。我习惯先把变量、目标、约束这三件事彻底写清楚再动代码否则后面调试会非常痛苦。2.1 变量与目标函数标准JSP数学描述长这样有n个工件m台设备每个工件Ji有ni道工序第j道工序Oij必须在指定设备Mij上加工耗时为pij。决策变量是每道工序的开工时间Sij。目标函数是最小化最大完工时间Cmax max(Cij)其中Cij Sij pij选择Makespan做单目标因为它直接反映整批订单的产出周期。对于钢结构车间这种单件小批量为主的场景生产周期就是资金占用周期这个指标比设备利用率更贴近经营需求。2.2 约束条件主要卡住哪三条在编码和解码设计里真正起作用的约束有三条工艺顺序约束同一工件的前道工序完成后后道工序才能开始。设备独占约束同一台设备在任意时刻只能加工一个工序。工序不可中断约束一道工序一旦开始就必须连续干完。实际车间还有设备维护、班组轮换、行车转运时间、物料配套等附加条件。这些要么折算进加工时间要么作为后处理检查项第一版模型里先不要全塞进去。原因很实际约束塞得越多模型越难调。先跑通核心逻辑再逐项加约束是我做这类项目一贯的套路。2.3 工序编号染色体为什么它天然合法JSP的染色体编码有几种常见思路。基于工件的编号编码染色体是工件编号的排列但一个工件有多道工序时它没法表达同一工件多道工序的先后穿插需要额外搭配工序指针做起来繁琐。基于优先规则的编码染色体和真实调度之间隔着一层映射调试困难。我选用基于工序的编码染色体是工件编号的重复序列每个工件i在染色体中出现ni次。从左往右扫描染色体第t次出现的工件编号i就代表该工件的第t道工序。选择它的关键原因是基于工序的编码天然满足工艺顺序约束任意一种排列翻译出来都能得到一个可行调度根本不需要修复操作。这让初始化、交叉、变异三个环节写起来都很干净不容易产生废个体。比如染色体某一段是[3 1 2 1 3 2]从左往右读第一个“3”是J3的第一道工序第一个“1”是J1的第一道工序第二个“3”是J3的第二道工序以此类推。2.4 实例数据准备6个构件、6台设备为了演示不超篇幅我构造了一个贴合钢结构车间特征的例子6个代表构件、6类设备。设备定义设备名称角色M1数控切割机下料前期瓶颈M2组立机板件组装M3焊接工作站核心瓶颈负荷最高M4数控钻床钻孔、打连接孔M5抛丸机表面处理M6喷涂线成品涂装各构件工序路线与加工时间工件代表构件工序路线各工序加工时间(小时)J1箱型柱M1→M2→M3→M4→M5→M645, 30, 90, 40, 25, 20J2H型钢梁M1→M2→M3→M4→M5→M640, 25, 80, 35, 25, 20J3十字柱M1→M2→M3→M5→M650, 30, 100, 30, 15J4支撑构件M1→M3→M5→M630, 60, 20, 15J5连接板M1→M4→M615, 20, 10J6檩条M1→M4→M610, 15, 10从数据可以直观看到M3焊接是负荷最重的设备M5抛丸机和中后期的喷涂线也紧张切割机前期压力大。这种数据结构和真实钢结构车间是吻合的焊接永远是瓶颈排产核心其实就是把焊接工位喂饱但不堵死。3. 遗传算法在MATLAB里的完整落地建模做完开始写实现。MATLAB的好处是矩阵操作和cell数组让数据结构非常直观遗传算法的核心部分几十行就能写完特别适合做这种需要不断调整查效果的调度原型。3.1 数据定义和种群初始化用cell数组保存路线和加工时间每个cell对应一个工件% 工件工艺路线设备编号从1到6 route { [1 2 3 4 5 6]; ... [1 2 3 4 5 6]; ... [1 2 3 5 6]; ... [1 3 5 6]; ... [1 4 6]; ... [1 4 6] }; % 对应加工时间单位小时 ptime { [45 30 90 40 25 20]; ... [40 25 80 35 25 20]; ... [50 30 100 30 15]; ... [30 60 20 15]; ... [15 20 10]; ... [10 15 10] };初始化种群的思路是先按工序总数生成一条基础模板序列每个工件编号重复其工序数次然后随机洗牌。这样得到的每条染色体都合法不会出现某个工件多一道工序或少一道工序的情况。function pop init_pop(popsize, job_counts) total_len sum(job_counts); base []; for i 1:length(job_counts) base [base, i * ones(1, job_counts(i))]; end pop zeros(popsize, total_len); for i 1:popsize pop(i, :) base(randperm(total_len)); end end调用时先取每个工件的工序数job_counts cellfun(length, route); % 得到 [6 6 5 4 3 3] pop init_pop(60, job_counts);3.2 解码是算法的核心解码函数决定了适应度评估的正确性和算法效率上限。它的逻辑可以看作一个“按染色体顺序往前塞活”的贪心过程。维护三个数组job_step记录每个工件已经安排到第几道工序job_end记录每个工件最后一道已安排工序的完工时间machine_end记录每台设备上最后一个工序的完工时间。然后从左到右遍历染色体当遇到工件编号j时就安排j的下一道工序。查route{j}得到设备编号查ptime{j}得到加工时长。这道工序能开工的最早时刻是max(前一工序完工时间, 设备空闲时间)。更新对应状态继续下一个基因位。function makespan decode(chrom, route, ptime) n length(route); m max(cellfun(max, route)); % 设备数量 job_step zeros(n, 1); job_end zeros(n, 1); machine_end zeros(m, 1); for k 1:length(chrom) job chrom(k); step job_step(job) 1; machine route{job}(step); p ptime{job}(step); start_t max(job_end(job), machine_end(machine)); finish_t start_t p; job_end(job) finish_t; machine_end(machine) finish_t; job_step(job) step; end makespan max(job_end); end这里有个很微妙的点当染色体中同一工件的编号连续出现时比如[... 1 1 ...]第二个“1”代表J1的第二道工序而它的开始时间必须大于等于第一个“1”代表的第一道工序完工时间代码里job_end(job)天然满足了顺序约束。这是基于工序编码最漂亮的地方——约束被编码本身消化掉了。如果后期想把调度压得更紧可以把解码改成插入式即在设备时间轴上找最早的可用空洞插进去。插入式解码能把Makespan进一步压低但代码复杂度会上一个台阶。我建议新手先把简单解码跑通再考虑升级。3.3 选择算子锦标赛选择的直觉选择压力太小算法收敛慢选择压力太大种群很快失去多样性。我用锦标赛选择每次随机抽k个个体取适应度最好的那个进入下一代候选池。k通常取2或3可以通过调整k来控制选择压力。function parent tournament_select(pop, fit, k) idx randperm(size(pop, 1), k); [~, best] min(fit(idx)); parent pop(idx(best), :); end注意fit这里存的是Makespan越小越好所以用min。也有人习惯把适应度定义为1/Makespan然后求max原理一样但别混用不然正负号会把自己绕晕。3.4 交叉算子POX为什么适合JSP交叉算子是遗传算法里影响解空间探索能力的关键。对基于工序的编码简单单点交叉会产生大量重复基因和缺失基因的废个体必须做修复很麻烦。我推荐POX优先工序交叉。步骤拆开讲把全部工件随机分成两个非空子集G1和G2。子代C1先继承父代P1中属于G1的工件基因保持它们在P1里的位置不变。然后按顺序从P2中取出属于G2的工件基因依次填入C1的空位。子代C2对称操作继承P2中G2的基因从P1中取G1填入空位。写成代码function [c1, c2] pox_crossover(p1, p2, n) g1 randperm(n, randi([1, n-1])); g2 setdiff(1:n, g1); mask1 ismember(p1, g1); mask2 ismember(p2, g2); c1 zeros(size(p1)); c2 zeros(size(p2)); c1(mask1) p1(mask1); c1(~mask1) p2(mask2); c2(mask2) p2(mask2); c2(~mask2) p1(mask1); endPOX之所以有效是因为它在交换基因片段的同时保留了每个工件在父代中的相对位置信息。焊接、切割这类重工序的先后关系不会被打乱子代质量普遍高于随机重组。3.5 变异交换变异就够了对基于工序的编码任意交换两个基因位得到的仍然是合法染色体因为每个工件的基因总量没变。所以最简单的变异就是随机选两个位置交换。function chrom swap_mutation(chrom, pm) if rand pm idx randperm(length(chrom), 2); chrom(idx) chrom(flip(idx)); end end实际使用中变异概率不要太高否则算法容易退化成随机搜索。后面参数实验会具体对比。3.6 主循环和精英保留策略主程序的基本框架长这样popsize 60; maxgen 200; pc 0.8; pm 0.1; job_counts cellfun(length, route); pop init_pop(popsize, job_counts); best_history zeros(maxgen, 1); for gen 1:maxgen fit zeros(popsize, 1); for i 1:popsize fit(i) decode(pop(i, :), route, ptime); end [best_val, best_idx] min(fit); best_history(gen) best_val; newpop pop; newpop(1, :) pop(best_idx, :); % 精英保留直接进下一代 for i 2:2:popsize p1 tournament_select(pop, fit, 2); p2 tournament_select(pop, fit, 2); if rand pc [c1, c2] pox_crossover(p1, p2, length(route)); else c1 p1; c2 p2; end c1 swap_mutation(c1, pm); c2 swap_mutation(c2, pm); newpop(i, :) c1; if i 1 popsize newpop(i 1, :) c2; end end pop newpop; end几个细节必须提醒精英保留放在newpop第一位保证最优个体不会被交叉变异破坏锦标赛选择k设2选择压力适中如果popsize是偶数循环边界别越界。这段代码跑200代对这个27道工序的小实例MATLAB运行时间一般在一两分钟以内作为离线排产工具完全够用。4. 实例跑出来的结果和参数调优实测跑代码只是开始真正花时间的是调参数、看结果、判断算法有没有正常工作。这一章是我自己调试过程中的一手记录。4.1 一组合适参数下的调度结果在实例数据上我用了popsize60、maxgen200、pc0.8、pm0.1这组参数跑出来的最好Makespan是215小时。作为对比随机初始解大约在290~310小时之间优化幅度超过三成。看排程结构M3焊接工作站从第45小时左右开始到第195小时前后几乎满负荷运转M5抛丸机和M6喷涂线在中后期连续工作M2组立机反而有较多空闲。这非常符合钢结构车间以焊接为瓶颈的实际感受——算法自己“找”出了瓶颈设备说明模型和编码方向是对的。需要强调遗传算法是随机算法每次运行结果不同。215这个数是我多次运行里的较优一次工程上一般取多次运行的最优值或平均值来评估算法稳定性。4.2 一组快速参数对比实验我做了个小规模对比实验控制单一变量每组跑5次取最好Makespan结果如下参数设置最好Makespan小时平均运行时间popsize30, gen200, pc0.8, pm0.1224约20秒popsize60, gen200, pc0.8, pm0.1215约50秒popsize100, gen200, pc0.8, pm0.1213约90秒popsize60, gen100, pc0.8, pm0.1221约25秒popsize60, gen400, pc0.8, pm0.1212约100秒popsize60, gen200, pc0.6, pm0.1219约50秒popsize60, gen200, pc0.9, pm0.1216约50秒popsize60, gen200, pc0.8, pm0.05219约50秒popsize60, gen200, pc0.8, pm0.2218约50秒我的结论是种群规模从30提到60收益最大继续提到100收益变小但耗时几乎翻倍迭代代数从200加到400只换来3小时改善性价比不高交叉概率在0.8附近比较稳变异概率0.1比0.05和0.2都稍好。换句话说参数调优的重点应该放在保证种群多样性上而不是一味堆迭代次数。4.3 看收敛曲线判断要不要停跑完把每一代最优值存下来画一条收敛曲线。曲线会先急剧下降然后趋于平缓。判断是否早熟我有两条经验一是对比最优值和平均值。如果最优值长时间不变但平均值还在缓慢下降说明还有个体在探路可以继续跑如果平均值也长时间不动种群已经高度同质化再跑下去也没意义。二是最优值超过20代没有更新就主动干预。我通常会调大变异概率或者做种群重启把部分个体重新随机初始化逼算法跳出局部极值。实测中这种方法比单纯把maxgen往上加更有效。早熟的根源是种群多样性丧失而不是迭代次数不够。4.4 甘特图怎么画、怎么看调度结果光看数字远远不够一定要画甘特图。画图思路很简单解码时额外保存每个工序的开始时间、结束时间、设备编号最后用rectangle函数在时间轴上堆矩形块每个工件一种颜色。figure; hold on; for k 1:length(records) x records(k).start; y records(k).machine; w records(k).duration; rectangle(Position, [x, y-0.4, w, 0.8], ... FaceColor, color(records(k).job, :)); text(x w/2, y, sprintf(J%d-O%d, ... records(k).job, records(k).step), ... HorizontalAlignment, center); end ylim([0.4, 6.6]); xlabel(时间(小时)); ylabel(设备编号);看甘特图重点确认三件事同一设备上有没有两个矩形重叠。有重叠说明解码逻辑有bug调度不可行。焊接设备M3的占用率是不是明显高于其他设备。如果是说明瓶颈定位准确。同一工件前后两道工序之间的等待时间是否过长。如果某道工序前空了一大段说明路径上该工件的设备时序可以再优化。甘特图还是和车间主任沟通的最好工具。他们不一定懂遗传算法但一眼能从图上看出“这里焊机等了半天”“那里切割机提前排满了”这种沟通反馈反过来会帮你修正模型。5. 从demo到车间落地要补的几块拼图原型跑通了距离真正用来排产还有几步路要走。这几块拼图是我在实际项目里遇到的不是学术论文里会写的东西。5.1 并行工位把逻辑设备拆开就行钢结构车间通常不止一台焊机、一台切割机。处理并行设备的思路很直接一个物理区域对应多台逻辑设备。比如焊接工位有两台焊机就把M3拆成M3a和M3b两个逻辑设备在route矩阵里把焊接工序的设备编号改成两者之一加工时间不变。这样GA框架完全不用改只需要在初始化时做一下设备分配。如果想更进一步可以上柔性作业车间调度FJSP的双段编码第一段给每个工序选设备第二段排工序顺序。柔性调度更贴近实际但编码、解码复杂度都上一个台阶。我给的建议是项目早期先用“固定路线逻辑设备拆分”的方式把业务跑通再考虑柔性调度。5.2 紧急插单和动态重调度车间里插单是常态不是例外。最简单实用的做法是滚动重调度把已经开工且不可中断的工序锁死把尚未开工的工序连同新插入的构件一起重新构成一个子问题重新跑遗传算法。这样做的好处是算法不需要从头重跑全部数据收敛也快。我用过一个更省事的变体给每个尚未开工的工件加一个最迟允许开始时间约束已经排好的部分不动只对受影响的时间窗口重排。做法是在适应度函数里加一个惩罚项超过窗口的个体直接给差评。效果在订单复杂度不高的场景下足够用。5.3 把算法结果变成现场能用的东西遗传算法给的是一个优化排程但现场执行还会遇到设备故障、物料没到、工人加班时间变化。我给车间用的版本做了两件事一是把解码结果导出成工序指派表包含每道工序的开工时间、完工时间、设备、操作班组直接打印成表格下发给班组长。光给一张甘特图现场不会看表格最管用。二是每天早晨根据实际进度更新数据重新跑一次调度。算法跑几十秒比车间主任手工排一个小时快得多而且每次给出的都是当前信息下的最优解。即使最终执行有偏差至少给出一个不依赖个人经验的标准答案对管理本身就是价值。最后再分享一个我的体会很多人拿到遗传算法第一反应是去调参数其实不如先花时间把解码函数写对、写好。解码是适应度评估的基础决定了算法的效率上限。Makespan能压到多少九成靠解码策略和算子的合理搭配参数只是锦上添花。如果数据量变大后MATLAB跑得慢可以先把循环向量化再把解码编译成mex或者把核心逻辑移植到Python或C上。算法骨架不变这套建模思路照样能用。