简介面向车间调度最大完工时间极小化场景的Matlab遗传算法GA求解方案贴合工业工程、运筹优化与智能制造方向的学习者也适合需要快速搭建调度算法的研究者。压缩包体积仅13KB共15个文件其中13个m脚本构成完整代码框架包括主程序、适应度计算、选择、交叉、变异、排序及结果绘制等模块并配有1个说明文档与1个mat数据文件方便对照数据和说明验证算法。目前已有68人学习下载。借助这套代码可掌握用GA处理工件-机器调度问题的完整流程明确工件工序与加工时间初始化种群经过适应度评价、选择、交叉、变异等迭代最终得到使最大完工时间极小化的调度方案。说明文档对参数设置和函数调用作了梳理脚本注释清晰便于在此基础上二次开发和扩展混合优化算法是学习车间调度智能优化算法的实用素材。1. 从交付压力到最大完工时间遗传算法为什么适合车间调度车间调度Job Shop Scheduling ProblemJSP里最直接压人头的指标就是最大完工时间makespan。订单里最后一道工序干完的时刻决定交付而它往往不取决于平均负荷只取决哪个工件在哪台机器上拖到最晚。精确算法能算小例子工件一多就呈阶乘级爆炸启发式规则又常被机器互锁关系带着走向局部极小。遗传算法不依赖导数也不要求目标函数连续它只通过“编码-适应度-选择-交叉-变异”反复迭代让一个杂乱的工序集合逐渐逼近极小值。这篇文章用 Matlab 从零实现一套能跑的 GA针对 makespan 极小化把编码、解码、算子、参数和甘特图验证串成一条完整链路。2. 基于工序的编码与Matlab解码把染色体转成可排产的完工时间遗传算法要在车间调度里生效第一件事不是写循环而是定“解长什么样”。二进制编码在连续优化好使但在 JSP 里很难保证工序先后顺序不被破坏所以常见做法是采用基于工序的编码operation-based encoding这也是工程里写 GA 求解车间调度时最稳妥的表达方式。2.1 为什么用基于工序的编码而不是二进制编码基于工序的编码本质是一条整数序列每个工件号出现 m 次m 是机器数量从左到右第 k 次出现某个工件号就表示该工件的第 k 道工序。比如 3 台机器时染色体[1 2 3 2 1 3 1 3 2]里出现 3 次 1分别代表工件 1 的工序 1、工序 2、工序 3。这种编码最大的好处是任意排列都能对应一个可行调度交叉变异后也天然满足“每道工序只出现一次”的约束省去大量修正逻辑。二进制或普通实数编码要表达“工序先后”就需要额外的修复程序基于工序的编码把约束内建在染色体结构里代价是需要一个解码器把整数序列翻译成每台机器上的开工结束时间。这部分跑得快不快直接影响整个 GA 的耗时所以要单独写成一个干净函数。2.2 解码函数将染色体映射到调度表解码从空机器开始依次读染色体左侧到右侧。遇到一个工件号先确认这是它的第几道工序取出该工序所在机器和加工时间开工时间必须是这台机器上一份活干完的时间与这个工件上一道工序完成时间的最大值。把所有工序塞进schedule表最终最大完工时间就是所有工件最后一道工序的完成时刻。% decodeJSP.m % chrom: 1 x (n*m) 的基于工序编码染色体 % seq: n x m 的机器顺序矩阵seq(i,k) 表示工件i第k道工序所在机器 % tm: n x m 的加工时间矩阵tm(i,k) 表示对应工序耗时 % schedule: 每行 [工件号 工序号 机器号 开始时间 结束时间] function [Cmax, schedule] decodeJSP(chrom, seq, tm) nJobs size(seq, 1); nMachines size(seq, 2); machineReady zeros(1, nMachines); % 每台机器的下一次可用时刻 jobReady zeros(1, nJobs); % 每个工件上一道工序的结束时刻 stepCount zeros(1, nJobs); % 每个工件当前已加工的工序数 schedule zeros(numel(chrom), 5); for g 1:numel(chrom) job chrom(g); op stepCount(job) 1; mac seq(job, op); pt tm(job, op); startTime max(machineReady(mac), jobReady(job)); finishTime startTime pt; machineReady(mac) finishTime; jobReady(job) finishTime; stepCount(job) op; schedule(g, :) [job, op, mac, startTime, finishTime]; end Cmax max(jobReady); end这段代码只做两件事按染色体给出的顺序把工序放到机器上并不断更新机器和工件的就绪时间。注意machineReady(mac)对应的是这台机器排到当前为止的结束时刻不是机器数量jobReady(job)代表该工件前一道工序的完成点二者取最大就是满足前置约束的最早可开工时刻。2.3 输入矩阵的组织机器顺序矩阵与加工时间矩阵为了不把矩阵维度和行顺序搞混我建议直接用两个 n×m 矩阵seq(i,k)存机器号tm(i,k)存耗时。机器号必须是 1 到 m 的整数Matlab 从 1 开始索引所以千万别出现 0 号机器。工件机器顺序 seq加工时间 tmJ1[1 2 3][3 1 2]J2[2 1 3][2 4 3]J3[3 2 1][4 3 2]用这个 3×3 算例跑如下代码染色体[1 2 3 2 1 3 1 3 2]会得到Cmax10。这个数可以作为后续调参是否破坏编码逻辑的回归基准。seq3 [1 2 3; 2 1 3; 3 2 1]; tm3 [3 1 2; 2 4 3; 4 3 2]; chrom [1 2 3 2 1 3 1 3 2]; [Cmax, schedule] decodeJSP(chrom, seq3, tm3); disp(Cmax);3. 选择、交叉与变异算子遗传算法在 Matlab 中的核心实现解码器只负责“算分”真正推动解往更小 makespan 走的是三个算子。选择决定谁有资格繁殖交叉负责组合优秀片段变异负责制造意外。三个算子的实现质量决定了最后是稳定收敛到好解还是陷在第一代就出现的局部最优里。3.1 锦标赛选择用适应度排序引导搜索最小化问题里适应度就是最大完工时间值越小越好。排序选择容易让几条特别好的染色体一开始就霸占总群体几代之后就出现多样性崩塌锦标赛选择可以通过窗口大小控制选择压力。窗口是 2 时压力小窗口是 5 时压力大工程上常用 3 作为默认值。% tournamentSelect.m % fitness: 列向量数值越小越好 % k: 锦标赛窗口大小 function idx tournamentSelect(fitness, k) n length(fitness); players randperm(n, k); [~, best] min(fitness(players)); idx players(best); end注意randperm(n, k)不会重复取同一个个体因此每次比较的都是 k 个不同候选。如果种群比较大窗口用 3 到 5 都行窗口越大收敛越快也越容易早熟需要结合后面的变异率联动调整。3.2 POX 交叉保持工序先后顺序的交叉方法普通排列编码用部分映射交叉PMX会产生无效染色体需要修复。对基于工序的编码更好用的是 POXPrecedence-preserving Order Crossover保留先后顺序的交叉随机挑一部分工件号把父代 1 中这些工件原位传给子代 1其余位置按父代 2 的顺序补上。反过来再做一次得到子代 2。% pox.m % p1, p2 是两条等长染色体 function [c1, c2] pox(p1, p2) n length(p1); jobList unique(p1); selCount randi([1, length(jobList) - 1]); selected jobList(randperm(length(jobList), selCount)); mask1 ismember(p1, selected); c1 zeros(1, n); c1(mask1) p1(mask1); fill1 p2(~ismember(p2, selected)); c1(~mask1) fill1; mask2 ismember(p2, selected); c2 zeros(1, n); c2(mask2) p2(mask2); fill2 p1(~ismember(p1, selected)); c2(~mask2) fill2; end选中的工件在子代里保持了父代的位置未选中的工件则按另一个父代的相对顺序填充所以每个工件出现次数不变工序顺序也不会乱。这就是 POX 比通用交叉稳定得多的原因实现时要注意selected至少要留一个工件不选否则交叉前后完全一样等于白做。3.3 交换变异小扰动帮种群跳出局部解变异在 JSP 的 GA 里不能太激进否则会把刚积累下来的好顺序打散。最常用的是交换两个随机位置的工件号。如果这两个位置对应同一个工件相当于没变异所以一般直接交换两个不同位置。% swapMutation.m function chrom swapMutation(chrom) n numel(chrom); pos randperm(n, 2); chrom(pos([1 2])) chrom(pos([2 1])); end对于超过 50 个基因的算例单点交换的扰动其实很小有时会不够跳出局部平台。另一种做法是把随机段反转或把某个工件的一段工序整体搬走但需要额外检查可行性。我建议先用小扰动跑通卡住时再在变异函数里加一个“逆序变异”分支。4. 规避早熟与参数组合让遗传算法在大完工时间优化中收敛更稳代码写完只能说明“能跑”车间调度最常见的失败不是解码错而是 GA 在几代内就收敛到某个很高的 makespan后面怎么迭代都不动。这就是热词里经常提到的“早熟现象”。早熟在求解最大完工时间极小化时尤其明显因为 makespan 这个目标对工序顺序非常敏感一条幸运染色体可能瞬间拥有超高适应度。4.1 早熟现象收敛快不等于找到好解早熟的表现很典型最优适应度曲线前十几代快速下降之后变成一条接近水平的线把当代种群里的染色体输出来看会发现大部分完全相同。原因是选择压力太大比如锦标赛窗口设成 5 且交叉率偏低某条局部最优染色体的副本在下一代里占掉 70% 以上位置交叉算子面对的几乎都是同一父代自然产生不了新结构。要缓解早熟优先调三个地方。第一减小锦标赛窗口到 2 或 3第二提高变异率比如从 0.05 提到 0.12第三限制精英数量精英个体只保留 1 到 2 条就够了留太多会人为制造拥挤。还可以在每次迭代后统计unique(pop, rows)的行数这个数量直接反映基因型多样性如果连续十代没有增加就说明种群被困住了。4.2 参数表种群规模、交叉率、变异率的建议值参数不是越极端越好。交叉率高有助于组件组合但太高会让好染色体被过度拆散变异率太低容易早熟太高则退化成随机搜索。下面这组数值是我在类似规模 JSP 算例里的常用起点。参数小型算例基因数 30中型算例30 到 100 个基因说明种群规模30 到 6080 到 200基因数越多需要的个体越多交叉率0.85 到 0.950.85 到 0.9过大容易破坏优良模式变异率0.05 到 0.150.01 到 0.08中型算例的交换变异影响块更大锦标赛窗口2 到 33 到 5窗口越大选择压力越大精英数量1 到 22 到 4防止历史最优丢失迭代代数100 到 200300 到 500可以再加早停条件如果用的是基于工序编码基因数是“工件数 × 机器数”。一个 6×6 算例就是 36 个基因属于中型偏小种群规模可以从 80 起步。如果发现曲线还一直能降就加大代数或增加种群规模不要盲目把窗口拉大。4.3 主循环框架精英保留与终止条件把前面的算子拼成主循环时最容易被忽略的是精英保留。每一代计算完适应度后先按适应度排序把最好的几条染色体原样复制到下一代其余个体再通过选择、交叉、变异生成这样历史最优不会因为交叉变异被意外破坏。% 主循环骨架 popSize 80; maxGen 300; pc 0.9; % 交叉率 pm 0.06; % 变异率 eliteCount 2; seq seq3; % 用前面 3x3 例子替换成自己的算例 tm tm3; nJobs size(seq, 1); nMachines size(seq, 2); nGenes nJobs * nMachines; % 初始种群每个工件出现 nMachines 次再打乱 baseGenes repmat(1:nJobs, 1, nMachines); pop zeros(popSize, nGenes); for i 1:popSize pop(i, :) baseGenes(randperm(nGenes)); end bestFit zeros(maxGen, 1); avgFit zeros(maxGen, 1); for gen 1:maxGen fitness zeros(popSize, 1); for i 1:popSize fitness(i) decodeJSP(pop(i, :), seq, tm); end [bestFit(gen), bestIdx] min(fitness); avgFit(gen) mean(fitness); [~, sortedIdx] sort(fitness); newPop zeros(popSize, nGenes); newPop(1:eliteCount, :) pop(sortedIdx(1:eliteCount), :); for i eliteCount 1:popSize p1 pop(tournamentSelect(fitness, 3), :); if rand pc p2 pop(tournamentSelect(fitness, 3), :); [p1, ~] pox(p1, p2); end if rand pm p1 swapMutation(p1); end newPop(i, :) p1; end pop newPop; end figure; plot(bestFit, LineWidth, 1.5); hold on; plot(avgFit, LineWidth, 1); legend(best makespan, average makespan); xlabel(generation); ylabel(Cmax);这个循环里每次迭代要对每个个体进行一次完整解码是耗时的主要瓶颈。你可以考虑把解码结果缓存或者对相同染色体做去重后一并算。另一个常见做法是额外保存“全局最优染色体”因为精英保留只保护了上一代的最优没有保护跨代最优在有变异的情况下历史最优还是有可能被覆盖掉。5. 用甘特图验证调度解把你算出的最大完工时间落到图纸上光看Cmax数值很难发现解码器或算子里的逻辑错误。甘特图是验证车间调度解最直观的工具矩形不能在同一台机器的时轴上重叠每个工件的矩形必须按工序顺序从左到右排。Matlab 里不需要额外工具箱用rectangle就能画清楚。5.1 甘特图绘制函数schedule里每一行已经包含工件、工序、机器、开始和结束时间。画图时先按开始时间排序再按机器分组把每个工序画成一个水平矩形横轴是时间纵轴是机器。同一工件的矩形用同一种颜色便于看前置约束是否被满足。% plotGantt.m function plotGantt(schedule) sched sortrows(schedule, 4); macList unique(sched(:, 3)); colors lines(max(sched(:, 1))); figure(Color, w); hold on; yTick []; yLabel {}; for idx 1:numel(macList) m macList(idx); rows sched(sched(:, 3) m, :); y0 idx - 0.35; for r 1:size(rows, 1) x0 rows(r, 4); w rows(r, 5) - rows(r, 4); rectangle(Position, [x0, y0, w, 0.7], ... FaceColor, colors(rows(r, 1), :), ... EdgeColor, k); text(x0 w / 2, y0 0.35, ... sprintf(J%d-OP%d, rows(r, 1), rows(r, 2)), ... HorizontalAlignment, center, FontSize, 9); end yTick [yTick, idx]; yLabel{idx} sprintf(Machine %d, m); end ylim([0, numel(macList) 1]); set(gca, YTick, yTick, YTickLabel, yLabel); xlabel(Time); title(Gantt Chart of GA Solution); grid on; end画图函数里的y0用的是机器在macList中的连续编号不是机器原始编号避免机器号不是连续整数时把图拉得很难看。调用时直接把decodeJSP的第二个返回值传进去即可。5.2 用 2×2 小例子回归验证 GA 求解器回归验证用 2 个工件、2 台机器的小算例最合适因为合法染色体只有 6 条可以枚举完所有可能性来确认真实最优解。设工件 1 走“机器1→机器2”耗时 5 和 3工件 2 走“机器2→机器1”耗时 3 和 5。这条算例总加工时间上下对称最优 makespan 是 8因为两条平行路径恰好可以交错填满两台机器。seq2 [1 2; 2 1]; tm2 [5 3; 3 5]; % 枚举所有基于工序编码的合法染色体 allChrom unique(perms([1 1 2 2]), rows); bestEnum Inf; for i 1:size(allChrom, 1) c decodeJSP(allChrom(i, :), seq2, tm2); bestEnum min(bestEnum, c); end disp(bestEnum); % 输出应该是 8把这段枚举逻辑放在 GA 主循环之后如果枚举结果是 8 但 GA 结果不是 8问题大概率出在选择交叉逻辑而不是解码器。确认解码器无误后再把第 2 章的 3×3 算例跑出 Cmax10和甘特图上的人工排布做一次比对。把这几个回归用例写成一个脚本以后改算子或参数时先跑一遍比每次都靠人眼盯曲线更可靠。本文还有配套的精品资源点击获取