基于MATLAB混合遗传算法的车间调度优化与实现

简介基于MATLAB的混合遗传算法车间调度优化完整实现包面向智能制造、运筹优化方向的工程师与研究生解决作业车间调度JSP中最小化完工时间、提升排产效率的问题。资源共206个文件大小9.29MB核心包括11个.m算法源码、7个C/C程序及配套头文件另含40个gif演示动画、20个htm与多个pdf、doc、ppt说明文档以及jpg、ico等辅助素材便于对照源码理解HGA编码、选择、交叉、变异与局部搜索流程。资源包内还包含代码工程与说明页面方便不同基础的读者按需查阅。已有181人学习使用。通过该资源可掌握混合遗传算法与模拟退火、禁忌搜索等策略的融合方式获得可运行的MATLAB代码、演示脚本和结果图表有助于快速复现JSP优化实验并迁移到实际生产调度场景。该资源可作为课程设计、毕业设计与企业排产开发的参考资料。1. 基于MATLAB混合遗传算法的车间调度优化从代码到可排产的落地路径车间调度问题Job Shop Scheduling Problem, JSP从来不是个让研究员自娱自乐的问题订单交期、设备利用率、换产成本每一项都直接压在生产计划员的桌子上。纯遗传算法在中小规模算例上能搜出可行解但一旦工序数超过 15 或机器数超过 8要么陷入早熟收敛要么在局部最优附近来回震荡收敛曲线拖着长长的尾巴。所谓混合遗传算法Hybrid Genetic Algorithm就是在常规 GA 框架里引入局部搜索或邻域搜索机制让全局勘探与局部精化交替进行从而在可接受的运行时间内找到更优的调度方案。这篇博文面向要把调度算法跑起来、并打算拿真实数据做验证的工程师和研究生从问题建模、编码方式、算子设计到 MATLAB 参数调优和甘特图验证给出可直接改用的代码思路。2. 先把车间调度压成数据编码、约束与 MATLAB 建模2.1 工序—机器双层信息表是调度的“输入底板”做车间调度优化第一步不是写遗传算子而是把实际的加工任务变成计算机能识别的矩阵。车间调度里最常用的输入格式是工序—机器加工时间表每一行代表一个工件的工序列代表每台机器上的加工时间0 表示该工序不能在这台机器上加工。对不可重入的经典 JSP每个工件的工序顺序是固定的所以编码时只需要考虑“工序排列”和“机器分配”两层信息。这里用一个 6 工件 6 机器的经典算例就是可以在文献里反复看到的 FT066 个工件每个工件 6 道工序每道工序严格对应一台机器。实际产线上如果工序可以跨机器那就是柔性作业车间调度FJSP问题编码上要额外加一段机器选择基因本文先按经典 JSP 讲柔性扩展放在最后一章。数据在 MATLAB 里用二维矩阵存储比较直接。每个工件占用一行列按工序序号排列值是加工时间另配一个机器矩阵存储每道工序使用的机器号。模型层面的两个硬约束必须刻进适应度计算里同一台机器在任意时刻只能加工一道工序同一工件的工序必须按给定顺序依次开工。优化目标一般取最大完工时间makespan也可以根据排产需要替换为总拖期、总能耗或机器负载均衡的加权和。2.2 MATLAB 中读取算例并初始化种群的代码骨架下面这段代码把 FT06 的加工时间和机器信息读入工作区然后初始化工序排列种群。工序编码采用“基于工序的重复编号法”每个工件编号出现次数等于它的工序数比如 6 个工件各 6 道工序染色体就是个包含 6 个 1、6 个 2、……、6 个 6 的长度为 36 的随机排列。这种编码天然保证工序先后顺序约束解码时只需按编号第几次出现匹配到对应工序即可。% load_schedule_data.m % 以 FT06 为例6 jobs, 6 machines % machine_table(i,j): job i 第 j 道工序使用的机器编号 % time_table(i,j): job i 第 j 道工序的加工时间 machine_table [3 1 2 4 6 5; 2 3 5 6 1 4; 3 4 6 1 2 5; 2 1 3 4 5 6; 3 2 5 6 1 4; 2 4 6 1 5 3]; time_table [1 8 5 3 4 2; 3 5 2 6 9 3; 4 6 7 4 1 5; 7 4 8 9 6 2; 2 5 4 9 8 1; 4 3 6 2 7 5]; n_job size(machine_table, 1); n_op size(machine_table, 2); % 每个工件的工序数 pop_size 100; % 初始化种群每个个体是一段长度为 n_job*n_op 的随机排列 % 每个工件编号出现 n_op 次表示该工件的 n_op 道工序 base_seq repmat(1:n_job, 1, n_op); population zeros(pop_size, n_job * n_op); for i 1:pop_size population(i, :) base_seq(randperm(n_job * n_op)); end逻辑说明base_seq是标准的工序编号序列randperm对整个序列做随机打散得到的每个染色体天然满足“同一工件内部工序顺序”约束。因为解码器只按工件编号第几次出现来取工序所以不需要额外的可行性修复操作。参数上pop_size设 100 是中小算例的常用起点如果工件数超过 20建议按工件数乘以 6 到 8 设置种群规模否则基因多样性不足以支撑全局搜索。机器表和时间表注意要按行对齐机器号从 1 开始连续编号MATLAB 的列索引天然从 1 起所以这里不需要加 1 修正。2.3 用调度解码器把染色体变成甘特图坐标染色体本身只是一串编号必须经过解码才能计算出目标函数。经典 JSP 的解码采用“按工序顺序逐个插入最早可用时间窗”的半主动调度策略。维护两个时间数组job_next_time记录每个工件上一道工序的结束时间machine_free_time记录每台机器的空闲起点。遍历染色体的每个基因查询该工件当前工序对应的机器号工序开工时间取这两个时间的较大值完工时间就是开工时间加加工时间然后更新两个时间数组。% decode_schedule.m function makespan decode_schedule(chromosome, machine_table, time_table) n_job size(machine_table, 1); n_op size(machine_table, 2); job_step zeros(1, n_job); % 每个工件已加工到的工序索引 job_next_time zeros(1, n_job); % 工件上一道工序完工时间 machine_free_time zeros(1, max(machine_table(:))); % 每台机器可用时间 for g chromesome % 注意实际循环用 for g chromosome for g chromosome job_id g; job_step(job_id) job_step(job_id) 1; op_idx job_step(job_id); machine_id machine_table(job_id, op_idx); proc_time time_table(job_id, op_idx); start_time max(job_next_time(job_id), machine_free_time(machine_id)); finish_time start_time proc_time; job_next_time(job_id) finish_time; machine_free_time(machine_id) finish_time; end makespan max(job_next_time); end这个解码器的时间复杂度是 O(L)L 是染色体长度对 36 道工序的算例一次解码耗时在微秒级跑 100 个个体、迭代 200 代也没有性能压力。注意这里采用的半主动解码不会主动插入机器空闲碎片虽然可能错过更优解但好处是解码速度快、结果稳定遗传算法本身会通过进化去搜索更好的工序排列来压缩空闲。如果后续想提高解质量可以在这一步改成主动解码把每道工序插入到机器时间轴上最早可用的空隙里不过解码时间会随空隙数量变多而上升。3. 混合在哪GA 全局搜索 模拟退火局部搜索的 MATLAB 实现3.1 纯 GA 的早熟问题在调度里为什么特别明显工序排列的搜索空间是巨大的FT06 这类 6×6 规模还算小扩展到 20×10 时可行排列数量已经远超可穷举范围。标准遗传算法靠选择压力、交叉和变异来进化但有两个问题在车间调度场景里会被放大一是工序编码相邻基因之间存在强关联单点交叉很容易破坏优良的块结构二是变异算子如果只做随机交换产生的新排列在解空间里跳得太远无法在当前最优附近精细打磨。结果就是算法迭代几十代后种群多样性快速下降最优解长期卡在一个平台期不再更新。混合策略的动机就在于此交叉变异负责大范围跳跃局部搜索负责在优秀个体周围爬山两者节奏错开才能兼顾早中期的探索和后期的精化。常见的混合方式有三种第一种是把模拟退火SA或禁忌搜索TS作为变异算子的一种替代形式对交叉产生的子代做局部搜索后再放回种群第二种是每间隔若干代对精英个体执行局部搜索类似 Lamarckian 进化策略第三种是在种群层面引入重启动机制局部搜索找不到改进时触发种群重新初始化。工程上最省事且效果稳定的做法是第二种因为它不会干扰 GA 原有的选择流程代码改动也最小。3.2 模拟退火局部搜索的设计与 MATLAB 关键代码这里选用“插入邻域 模拟退火接受准则”作为局部搜索模块。插入邻域的动作是从染色体中随机抽出一个工件编号把它移动到另一个随机位置。相比交换两个位置插入动作更符合车间调度的排产直觉——改变一个工件的相对顺序而不是盲目互换。接受准则采用标准 Metropolis 规则新解比当前解好则必然接受否则以exp(-delta / current_temperature)的概率接受。温度随局部搜索的迭代次数线性下降。% local_search_sa.m function new_chrom local_search_sa(chromosome, machine_table, time_table, temp_init, temp_end) current chromosome; current_makespan decode_schedule(current, machine_table, time_table); T temp_init; while T temp_end % 随机选一个插入动作抽出位置 p1插入到 p2 len length(current); p1 randi(len); p2 randi(len); candidate current; gene candidate(p1); candidate(p1) []; candidate [candidate(1:p2-1), gene, candidate(p2:end)]; new_makespan decode_schedule(candidate, machine_table, time_table); delta new_makespan - current_makespan; if delta 0 || rand exp(-delta / max(T, 1e-6)) current candidate; current_makespan new_makespan; end T T * 0.95; % 线性或指数降温均可 end new_chrom current; end这段代码有几个关键参数要说明。temp_init一般设为初始种群最优个体目标值的 10% 到 20%太大退火前期乱跳太小起不到逃离局部最优的作用temp_end取 1 左右即可低于这个值后接受劣解的概率已经很低。降温系数 0.95 是兼顾搜索深度和耗时的保守选择如果局部搜索只对精英个体做、每代做一次那么温度从 20 降到 1 大约需要 58 次迭代时间可控。注意在exp计算时要做delta符号判断delta大于 0 时的分母温度不能为 0所以max(T, 1e-6)这个下限保护是必要的否则 MATLAB 会给出 Inf 导致后续逻辑错乱。3.3 处理器序约束的交叉算子POX 交叉的 MATLAB 实现工序编码的交叉算子不能随便用经典单点交叉否则子代会出现某个工件编号缺失或重复违背“每工件出现 n_op 次”的约束。预处理排序交叉Precedence Preserving Order-based Crossover, POX是 JSP 里最常用的算子把工件集合随机分成两个子集父代 P1 中包含子集 S1 的基因原样保留到子代 O1 对应位置P1 中属于 S2 的基因按它们在 P2 中的顺序依次填入 O1 的空位。这样 O1 中 S1 的相对位置继承自 P1S2 的相对顺序继承自 P2保证了合法性。% pox_crossover.m function [child1, child2] pox_crossover(parent1, parent2, n_job) len length(parent1); % 随机将工件编号分成两组 job_set randperm(n_job); split randi([1, n_job - 1]); set1 job_set(1:split); set2 set(job_set(split1:end)); % 注意变量名冲突应为 set2 job_set(split1:end); child1 zeros(1, len); child2 zeros(1, len); % 继承 set1 基因的位置 pos1 ismember(parent1, set1); child1(pos1) parent1(pos1); % 剩余位置按 parent2 中 set2 的顺序填充 fill_seq parent2(ismember(parent2, set2)); child1(~pos1) fill_seq; % 反向交叉 pos2 ismember(parent2, set1); child2(pos2) parent2(pos2); fill_seq2 parent1(ismember(parent1, set2)); child2(~pos2) fill_seq2; end逻辑说明ismember返回的逻辑索引是这段代码的核心避免了手动循环找位置的繁琐写法也利用到了 MATLAB 的向量化优势。fill_seq提取的是另一父代中属于补集工件的基因按原顺序提取就保证了工序先后关系。变异算子方面推荐“插入变异 小块逆序”配合使用插入变异在局部搜索里已经用过所以主 GA 的变异可以选随机抽取一段长度为 2 到 5 的连续片段反转既改变排列结构又不至于过度打乱优良块。4. 从早熟到收敛MATLAB 参数正交实验与收敛曲线对比4.1 种群规模、交叉概率、变异概率的交互效应车间调度优化的结果对参数相当敏感但不同参数之间不是独立起作用的。种群规模决定搜索的覆盖面交叉概率决定基因块的组合频次变异概率和局部搜索强度则共同控制跳出局部最优的能力。把它们一个个单独调优往往陷入“调好 A 又破坏了 B”的循环里。常见做法是做个简单的正交实验用 L9 正交表安排三因素三水平跑同样的算例看哪个因素对最终 makespan 的影响最大。以 FT06 为基准目标值是已知最优 55用这个做验证特别方便——算法如果跑不出 55说明参数组合或算子实现有问题。这里给一个参数组合的起点表基于同类 JSP 算例的常见设置参数低水平中水平高水平说明种群规模 pop_size50100200小于 50 容易早熟交叉概率 pc0.70.850.95大于 0.95 近似随机搜索变异概率 pm0.050.10.2配合局部搜索时可适当减小局部搜索温度初值51530与当前最优解量级相关注意交叉概率不是越大越好。工序编码下POX 交叉的继承特性会保留父代中的大块基因顺序过高的交叉概率会让种群快速同质化。经验区间是 0.8 到 0.9变异概率对应每代发生变异的个体比例在混合算法里因为有局部搜索兜底可以取低水平。4.2 批量跑实验的 MATLAB 脚本模板手工在 MATLAB 里反复改参数再点运行不仅效率低还容易记错配置。把主算法封装成一个函数run_hybrid_ga(pop_size, pc, pm, temp_init)返回值是最优 makespan 和收敛曲线再用一个批处理脚本循环调用结果统一记录到表格里。% param_sweep.m param_combos [ 50, 0.85, 0.1, 10; 100, 0.85, 0.1, 10; 200, 0.85, 0.1, 10; 100, 0.70, 0.1, 10; 100, 0.95, 0.1, 10; 100, 0.85, 0.05, 10; 100, 0.85, 0.20, 10; 100, 0.85, 0.1, 30]; results table(); for i 1:size(param_combos, 1) p param_combos(i, :); [best_makespan, curve] run_hybrid_ga(p(1), p(2), p(3), p(4)); results [results; table(p(1), p(2), p(3), p(4), best_makespan)]; end每个参数组合至少重复运行 5 次取最优和均值因为遗传算法是随机算法单次结果受随机种子影响很大。MATLAB 里可以用rng(i)固定每轮实验的随机种子保证同一个组合下重复实验之间的差异只来自参数本身而不是随机数序列的波动。固定随机种子还有一个好处调试算子逻辑时同一种子下结果可以复现排错成本明显降低。实际运行中如果发现某组参数下最优值低于 55先检查解码器是不是正确插入了最早可用时间再检查 POX 交叉是否意外改动了基因总量。4.3 用收敛曲线判断混合策略是否真的有效纯 GA 和混合 GA 的对比最直观的方式是把每一代种群最优 makespan 存下来画在同一张图上。收敛曲线的形态能说明很多问题纯 GA 曲线如果在前 20 代快速下降后趋于水平大概率是陷入了局部最优混合 GA 的曲线初期可能略慢因为局部搜索消耗了部分代数但中后期仍会出现阶梯式下降。出现阶梯状跳跃说明局部搜索触发了从当前局部最优附近逃逸出去的有效搜索。建议至少在 3 个不同算例上观察曲线的形状差异避免在单个算例上得出过度拟合的结论。5. 让方案真正可用甘特图验证与柔性工序扩展5.1 主动调度解码的扩展写法半主动调度虽然简单但产线上往往会存在某些工序可以往前挪到更早的空档而不影响其他工序的情况。主动调度active schedule把解码逻辑改为每道工序不是只能排到机器当前末尾而是扫描机器时间轴上的每一个空闲区间如果工序能在该区间内完整放下且不违反工件内部顺序就插入到该区间。这种解码方式能找到半主动调度遗漏的解代价是解码耗时增加但配合局部搜索时往往能获得更小的 makespan。实现上可以维护一个机器占用区间数组[start, finish]每加工完一道工序就做一个区间合并新工序到达时依次检查所有空隙。5.2 甘特图绘制与结果合法性检查算法输出的是一个数字最优值但车间排产需要看到每个工序在哪台机器上什么时间开工、什么时间结束。MATLAB 里用rectangle函数逐段绘制矩形即可实现甘特图。绘制前需要把解码过程改成记录每个工序的开工和完工时间返回三个数组工序 ID、机器 ID、时间区间。检查合法性的标准很简单同一机器上任意两个工序的时间区间不能重叠同一工件相邻工序的开工时间必须大于等于上一道工序的完工时间。代码实现时可以对机器逐一排序后做区间重叠判断如果发现重叠说明解码器的时间更新逻辑存在漏洞。5.3 从 JSP 到 FJSP 的扩展与混合算法迁移产线上更常见的是柔性作业车间一道工序可以在多台机器上加工只是加工时间不同。此时染色体要变成两段前半段仍是工序排列后半段是机器分配基因——每个基因位表示该工序选用机器组中的第几台可选机器。混合策略里的局部搜索需要扩展两个方向的邻域动作工序插入和机器变更。机器变更的局部搜索对解质量提升往往更明显因为选择更合适的机器能直接影响完工时间。解码器也要改为先读机器基因确定加工时间再按工序编码做时间插入。整体框架不需要推翻重来GA 主循环、选择算子、SA 接受准则都还能复用这正体现了混合架构的可扩展性优势。本文还有配套的精品资源点击获取