车间里的调度问题做过的人都知道难缠的地方不在设备而在人。设备参数是死的工人不是——技能不同、熟练度不同、上班时段不同同一个工件在不同工人手里的加工时间能差出百分之二三十。这就是带工人约束的混合流水车间调度问题HFSSPW让人头疼的地方既要排机器又要排工人两套约束叠在一起目标还不止一个。我最近用Matlab实现了一套基于融合启发式解码的多目标进化算法来求解HFSSPW效果还不错。这篇博文把整个思路、建模过程、关键代码逻辑和踩过的坑完整记录下来适合正在做生产调度优化、写毕业论文或者在企业里搞智能制造排产方案的朋友参考。1. HFSSPW问题的数学模型从车间现场到约束方程1.1 混合流水车间到底是什么混合流水车间Hybrid Flow ShopHFS是经典流水车间Flow Shop的扩展。经典流水车间是一串机器排成一条线每个工件按同一顺序依次经过每台机器混合流水车间则在某些阶段布置了多台并行机工件在某个阶段只需要选择其中一台机器加工。现实中的机加工车间、PCB组装线、制药包装线基本都是这种形态。举个例子一个典型的机加工车间可能有三个阶段下料、粗加工、精加工。下料阶段一台锯床粗加工阶段三台不同型号的铣床精加工阶段两台磨床。每个工件都要依次经过这三个阶段但在粗加工阶段可以任选一台铣床。这样问题就变成了两层次决策第一阶段给每个工件确定加工顺序第二阶段给每个工序选择合适的机器。如果车间里还有工人操作限制每个工人在同一时刻只能操作一台机器而且不是所有工人都会操作所有机器那就成了HFSSPW。1.2 工人约束怎么进入模型我最初只考虑了机器约束结果排出来的方案在车间根本执行不了——精加工阶段的两台磨床分别需要不同技能的工人而我排的时段里只有一个会磨床的师傅在岗另一台机器只能空转。所以工人约束必须显式建模不能事后补救。HFSSPW里的工人约束主要体现在三个维度技能矩阵工人w是否会操作机器m记为一个0/1变量。工人不会操作某台机器那台机器在这个时段就不能指派给他。熟练度差异即使两个工人都能操作同一台机器加工时间也可能不同。可以用工人-机器对应的加工时间系数来表示比如熟练工的加工时间是标准时间的0.8倍新手是1.2倍。可用时间窗工人不是24小时都在岗有班次、休息、换班。这比机器的可用时间窗更复杂因为同一班次内工人的可用时间段可能是交错的。数学上这个问题可以这样描述。给定n个工件J1到Jn、s个加工阶段stage1到stages、每个阶段有m_k台并行机、车间里有w个工人。每个工件j在第k个阶段的机器i上由工人l加工的时间记作p_{j,k,i,l}。如果工人不会操作这台机器这个加工时间为无穷大。决策变量有三个工序排序π、每道工序的机器分配M、每道工序的工人分配W。约束如下同一工件的工序顺序约束工件在第k阶段完工后才能进入第k1阶段。机器容量约束一台机器在同一时刻只能加工一个工件。工人容量约束一个工人同一时刻只能操作一台机器。技能匹配约束工人l被指派到机器i的前提是技能矩阵中对应元素为1。可用时间约束工序在机器上的开始时间必须落在工人l的可用时间窗口内。1.3 多目标定义与评价指标为什么要用多目标算法因为实际车间排产从来不是只追一个指标。我接触过的企业里最常见的三个目标分别是最大完工时间所有工件完成加工的总时间英文叫makespan。这个指标直接决定了订单的最短交付周期。总拖延时间每个工件相对交期的延误时间之和。制造业里逾期交付要赔钱这个很重要。工人负载均衡不同工人之间的总工作量差异。为了平衡工人绩效车间主任通常会要求负载不要差太多。可以用最大工人负载与平均工人负载的差值来衡量。这三个目标经常是矛盾的缩短makespan可能让某个熟练工忙死新手闲着减少总拖延可能要让某个瓶颈设备超负荷运转。多目标进化算法的作用就是找到一组Pareto最优解让决策者根据现场情况在目标之间权衡。在Matlab实现里我定义了一个适应度评估函数输入一个调度方案输出三个目标值。用结构体存储每次调度的完整时间表这样后面做Gantt图也方便。2. 为什么选多目标进化算法NSGA-II框架与HFSSPW的适配逻辑2.1 问题特性与算法匹配分析HFSSPW属于NP-hard问题精确算法只能解决极小的规模。我做实验时用CPLEX求解10个工件、3个阶段、8台机器、6个工人的小实例跑了半个小时还经常找不到最优解。所以大规模场景基本只能靠启发式和元启发式。在多目标元启发式里NSGA-II带精英策略的非支配排序遗传算法是经过大量工程验证的成熟框架。它好在哪里第一非支配排序能同时维护多个目标的解集不需要人为设定加权系数第二拥挤距离机制保证解集在Pareto前沿上分布均匀避免所有解挤在一小段前沿上第三精英保留策略保证算法收敛过程中最优解不会丢失。当然NSGA-II和NSGA-III我都试过。NSGA-III用参考点来维持多样性在高维目标4个以上下更优秀但HFSSPW常用的是2到3个目标NSGA-II的拥挤距离已经够用而且实现更简洁、运行更快。所以最后我选择了NSGA-II作为主框架。2.2 染色体编码与种群初始化编码方式是进化算法里最关键的决策之一直接决定算子设计和解码难度。HFSSPW的决策空间包含工序顺序、机器分配、工人分配三层怎么编码很有讲究。我采用的是基于工件排列的编码permutation-based encoding它的思路是染色体上一共有 (n) 个位置每个位置是某个工件的编号工件号出现的次数等于它在流水线上经过的工序数。假如有5个工件每个工件3道工序那么染色体长度为15工件1出现3次、工件2出现3次……解码时从头到尾扫描染色体第 (t) 次出现的工件j就代表该工件的第t道工序。这样做的好处是天然满足同一工件的工序次序约束不需要在解码时做可行性修复。至于机器和工人不放在染色体上而是在解码阶段用启发式规则实时决定。这就引出了本文的核心——融合启发式解码。种群初始化方面直接随机生成 (N) 条随机的工件排列染色体然后全部用启发式解码来评估。有朋友建议我用NEH启发式Nawaz-Enscore-Ham生成一部分初始解来加速收敛这个思路我采纳了后面第三节详细说。2.3 非支配排序、拥挤度与选择算子NSGA-II的骨架在Matlab里实现起来并不复杂核心就三个模块。第一个是非支配排序。对种群里的每个个体计算它被多少个个体支配支配计数和它支配了哪些个体支配集合。循环取出所有支配计数为0的个体归入第1层Pareto前沿然后把这些个体的支配集合里的成员支配计数减1再取下一批为0的归入第2层如此循环直到所有个体分层完毕。判断个体A支配个体B的条件是A的所有目标值都不比B差小于等于并且至少有一个目标严格优于B。注意这是一个偏序关系不是简单比大小。我在Matlab里用的是一个双层循环最开始没加向量化处理500个种群个体、迭代300代时间开销肉眼可见地增长。后来把目标值矩阵化循环次数大幅下降速度提升明显。第二个是拥挤距离计算。对同一Pareto前沿层里的个体按每个目标值排序边界个体的拥挤距离设为无穷大中间个体的距离等于相邻两个个体在该目标上的归一化差值之和。距离越大表示周围越空旷多样性贡献越大。第三个是锦标赛选择。每次随机从种群中抽取两个个体先比Pareto层级层级小的获胜层级相同比拥挤距离距离大的获胜。这个设计保证了算法在收敛和多样性两个方向上的平衡。Matlab的randperm函数可以方便地实现锦标赛选择但要注意每次选择的随机性要在不同代之间独立否则容易陷入局部收敛。2.4 交叉和变异的Matlab实现交叉算子我用了顺序交叉Order CrossoverOX它对排列编码的效果比较稳定。具体做法是随机选两个交叉点把父代P1在这两个点之间的基因片段先复制给子代C1然后从父代P2中按顺序取出那些不在该片段内的工件编号依次填入C1的剩余位置。这个过程的Matlab实现大约15行代码核心是利用ismember函数判断某个工件编号是否已经在片段中。变异算子用的是交换变异随机挑选染色体上的两个位置交换工件编号。有文献说对排列编码使用插入变异效果更好就是把一个位置的工件编号拿出来插入到另一个位置。我在实验里对比过两种变异交换变异的收敛速度略慢但最终Pareto前沿的多样性更好所以保留了交换变异。这里给一个交叉率的参考值我试过0.6到0.90.8附近比较稳定变异率0.1到0.2之间表现不错低于0.05时算法很容易早熟。当然这只是针对我构造的测试算例不同规模的具体问题还是得自己做参数实验。3. 融合启发式解码解决工人约束的关键设计3.1 解码的基本流程解码是把染色体翻译成实际调度方案的过程也是整个算法里工程味道最浓的部分。普通的解码方式是按染色体顺序把工序逐个插入到当前最早可用的机器上这种方式在无工人约束的HFS里没问题但一旦引入工人约束机器最早可用并不代表工人也有空必须把人和机器一起安排。我的解码流程分四步按染色体顺序取出当前要安排的工序确定它属于哪个工件的哪一道工序以及该工序对应哪个加工阶段。扫描该阶段所有可用机器筛选出在当前时刻之后有可用时间窗口的机器。对每台候选机器扫描所有技能匹配且在该时段可用的工人计算一个可能完工时间。选择可能完工时间最小的机器工人组合把工序插入更新机器和工人的空闲时间表。这其实就是把机器分配和工人分配合并成了一个启发式规则的过程。之所以叫融合是因为传统的两步式解码会先选好机器、再选工人容易产生一端最优另一端吃亏的情况。合并成一步后设备和人力资源作为一个整体来决策。3.2 机器选择与工人分配启发式规则在第四步选择哪个机器工人组合时我测试过几种规则总结下来效果排名如下规则描述适用场景实验排名最早完工时间ECT选择当前工序最早加工完成的组合目标以makespan为主1最早可用机器EAM选择最早空出的机器目标均衡性要求高3最短加工时间SPT选择加工时间最短的组合瓶颈设备明显2工人负载最小选择当前累计负载最小的工人目标包括负载均衡2与SPT并列我最终使用的是复合规则先按最早完工时间筛选出前3个候选组合再从中选择工人累计负载最小的那个。这样可以兼顾makespan和负载均衡两个目标。注意这里说前3个是经验值没必要对整个候选集合做完整排序那样计算量太大。3.3 用NEH启发式生成初始解NEH启发式是解决流水车间调度问题最经典的构造式启发式它的核心思想是先把所有工件按总加工时间降序排列然后逐个插入到一个已有的部分调度里每次尝试所有可能插入位置选择使目标函数最优的位置。我把它改造成了两阶段版本来做HFSSPW初始化。第一阶段对每个工件计算它在所有阶段、所有机器上的平均总加工时间考虑工人技能系数按从大到小排序。第二阶段依次取出排序后的工件尝试插入到当前染色体的所有可能位置用启发式解码评估新染色体的makespan选择makespan最小的插入位置。这样生成的初始解质量远高于纯随机解。有一点需要提醒用NEH生成的全部初始解会让初始种群过早集中导致多样性下降。我的做法是只有20%的初始个体用NEH生成其余80%保持随机。这个混合比例也值得在具体问题上做微调。3.4 解码后处理与局部改进启发式解码给出的方案不一定局部最优我加了一个轻量的后处理对解码产生的工序序列做两次局部搜索。第一次把每个阶段中负载最重的机器上的工序与负载最轻的机器上的工序尝试交换第二次在满足工件工序约束的前提下将某道工序的开工时间向前移动检查是否能空出更长的连续空闲段。这一步叫左移交换。这个后处理的关键收益是能在不破坏多目标特性的前提下显著改善Pareto解集的质量。我在5个工件的小案例上测试加上后处理之后IHR超体积指标平均提升了8%左右。代价是每个个体的解码时间多了大概15%但整体在可接受范围内。4. Matlab代码实现关键模块与核心代码解读4.1 数据结构的定义Matlab里没有传统意义上的类我习惯用结构体组织数据。核心数据结构有三个problem、population和schedule。problem存储问题实例的全部参数包括problem.n 5; % 工件数 problem.s 3; % 阶段数 problem.m [1 3 2]; % 每个阶段的机器数量 problem.w 4; % 工人数 problem.procTime cell(problem.n, problem.s); % 加工时间矩阵 problem.skill randi([0 1], problem.w, sum(problem.m)); % 技能矩阵 problem.avail ones(problem.w, 24); % 工人的每小时可用性这里procTime用了cell数组因为每个工件在每个阶段的机器数不同不能用普通三维数组统一存储。每个元素是一个 (m_k \times w) 的矩阵表示在不同机器、不同工人组合下的加工时间。如果某个工人不会操作某台机器就把对应元素设为inf解码时天然会排除这个组合。population存储种群个体每个个体有chrom、machineAssign、workerAssign、obj等字段。schedule则存储一次完整解码的各类时间信息包括每个工序的开工时间、完工时间、工人分配、机器分配画Gantt图时直接读取这个结构体。这里有一个容易被新手忽略的点Matlab的struct数组在横向拼接和索引时非常吃内存当种群规模达到500、染色体长度为30以上时反复赋值会导致性能急剧下降。我的解决办法是把每个个体的关键属性存为普通数组矩阵只有schedule这种需要可视化的大结构体才单独保存。4.2 主循环结构整个算法的主循环比较清晰这里给出简化版的伪代码逻辑% 初始化 pop initializePopulation(problem, popSize, initMethod); [pop, F] evaluatePopulation(pop, problem); % 进化主循环 for gen 1:maxGen % 锦标赛选择 matingPool tournamentSelection(pop, F, popSize); % 交叉和变异 offspring crossover(matingPool, pc); offspring mutation(offspring, pm); % 解码评估 [offspring, F_off] evaluatePopulation(offspring, problem); % 合并父子种群非支配排序选择前popSize个 combined [pop, offspring]; combinedF [F; F_off]; [combined, combinedF] nonDominatedSort(combined, combinedF); pop selectBest(combined, combinedF, popSize); F combinedF(1:popSize, :); end注意交叉和变异都是对染色体数组进行操作操作完再调用decode函数生成schedule并计算目标值。这个分离设计很重要——进化算子和问题模型解耦以后如果想换编码方式或者加约束只需要改decode函数不需要动进化骨架。4.3 约束处理和可行性校验解码时最头痛的问题是合法性校验因为机器约束和工人约束互相嵌套。我的做法是在插入工序时维护两个时间表machineFreeTime是每个阶段每台机器的下一个可用时刻workerFreeTime是每个工人下一个可用时刻。插入工序前先找出当前时刻所有候选机器工人组合中当前可以开工的集合。这里的关键逻辑在判断可以开工工序的潜在开始时间 (t_{start}) 必须同时满足机器空闲、工人空闲、工人在此时段可用这三个条件。工人可用性如果细化到时间窗就不能只用一个nextFreeTime标量需要用区间列表来表示。我实现了一个函数findEarliestSlot输入开始时间和持续时间搜索工人的可用区间列表找到第一个能容纳该工序的窗口。这个函数是代码里最容易被写错的地方。如果工人的可用区间是有多个时段的简单的取下一个空闲时刻很可能落在一个不可用区间里导致排出来的方案无法实际执行。最开始我没考虑到这一点排出的方案机器利用率很好看但拿到车间一核对工人根本没有在岗全部作废。后来我专门写了一个单元测试函数生成随机问题实例并校验所有工序是否满足工人可用性才把这个坑填上。4.4 实验设计与性能验证实验设计这块我构造了三组不同规模的算例小规模5个工件3个阶段6台机器4个工人中规模10个工件4个阶段10台机器6个工人大规模20个工件5个阶段16台机器8个工人每组算例随机生成10个实例有技能约束和没有技能约束各一组。为什么要做有/无技能约束的对照因为可以单独观察工人约束对算法性能的影响程度这是论文审稿人经常会问的对照实验。性能评价指标我用了三个超体积指标HV、世代距离GD和反转世代距离IGD。Matlab里实现HV需要先确定参考点一般取各目标单独优化时的最差值向量GD和IGD都需要知道真实的Pareto前沿对大规模问题这是未知的所以我的做法是用长时间运行的NSGA-II迭代5000代的解集近似作为参考前沿。算法对比方面除了纯NSGA-II我还对比了带融合启发式解码的NSGA-II也就是本文方案和一个最简单的经典规则调度方法。实验结果很明确带融合启发式解码的方案在HV和IGD上明显优于纯NSGA-II在小规模算例上尤其突出说明启发式解码确实帮助算法更高效地利用了问题结构信息。5. 调参经验与工程实践中的坑5.1 种群规模和迭代次数的选择调参是最磨人的环节。对HFSSPW这种情况种群大小我建议从50开始试逐步加到100、200、500。最终我发现50个个体对5个工件的小算例足够但到20个工件的大算例就明显不够用Pareto前沿会稀疏得很厉害。20个工件的算例我最终用了200个个体。迭代次数要看收敛曲线。我的经验做法是运行算法并每隔10代记录一次HV值画一条HV-迭代次数曲线。当曲线在50代之后基本不再上升说明已经收敛如果200代还在涨那就继续加长。不要盲目迷信大迭代次数计算时间也是成本。有一次我跑到800代发现HV还有上升趋势但每轮解码加上后处理已经很慢最终在300代到400代之间取了折中。5.2 参数敏感性分析我做了几个关键参数的敏感性测试结论如下交叉率0.6到0.9的范围内HV值差异不大但交叉率偏低时解集多样性差一点。变异率超过0.3时算法近乎随机搜索收敛性急剧恶化低于0.05时容易陷入局部前沿。NEH初始化比例从0%提高到30%HV明显改善继续提高反而导致种群多样性下降中规模算例上HV降低了4%左右。后处理开关的对比显示在工人负载均衡目标上后处理带来的改进最明显因为负载再分配是它的直接效果。这些参数的取值不是全局最优的但至少在我构造的算例集上表现稳定。做研究时最好针对自己的算例重新做一遍这个小实验参数空间不大跑起来很快。5.3 可视化与调试技巧Matlab做调度问题最大的优势就是可视化方便。我最终用Gantt图甘特图展示调度结果画法是自己写了一个函数遍历schedule结构体里的每个工序用rectangle函数按开工时间到完工时间绘制色块机器和工人用不同的行来表示。这里有一个要特别注意的点绘制工人行的Gantt图时同一个工人在不同机器上执行的工序要在同一行上展示但颜色按机器区分这样才能看出工人是否来回切换太频繁。调试方面我最常用的技巧是生成小规模实例3个工件、2个阶段、2台机器、2个工人人工手算出最优方案然后跟算法输出对比。这个验证方法虽然笨但非常有效——我靠它发现过两个隐性bug一个是在工人技能不匹配时inf没有被正确传递到目标函数里另一个是编码解码时工件工序顺序被意外打破导致同一工件的工序并行加工这在流水车间里是不允许的。5.4 代码性能优化最后聊一下Matlab代码性能。调度问题解码是整个算法最耗时的部分优化它的收益最大。第一避免循环嵌套过深。解码时对每个工序扫描所有机器和工人如果实现不当会形成三层循环。我的做法是预先对每个阶段整理出候选机器工人组合列表解码时直接遍历这个列表而不是每次都现找。第二向量化目标值计算。非支配排序和拥挤距离计算尽量用向量操作不要在每个目标维上都跑一个for循环。我试过把目标计算从逐个个体循环改成矩阵整体计算速度提升接近2倍。第三善用sparse矩阵。机器空闲时间表和工人空闲时间表如果用稀疏矩阵存储在大规模算例里不仅省内存某些操作比如查找最早空闲时刻还能用find函数向量化完成。这些优化做完后中规模算例10个工件、100个个体、300代的完整运行时间从原来的20分钟降到了8分钟左右算是可以接受的工程速度。如果继续用parfor做并行评估还能再压缩一些但那样需要额外注意随机数种子的可控性我为了确保实验结果可复现最终没有在主实验里启用并行。整个项目做下来我的核心体会是HFSSPW这类问题算法框架是通用的但真正决定解质量的往往是在解码这一层做的功夫。融合启发式解码相当于把领域知识直接注入进化过程让每个个体在评估阶段就吸收了车间调度积累的经验规则进化算法只需要在这个高质量的搜索空间里做多样化探索两者的配合比单纯加大种群的收益更明显。这套Matlab代码的组织方式也留了扩展口子——如果后续要加入能耗目标或者考虑工件搬运时间只需要在problem结构体里加字段、在decode函数里补逻辑就行主进化框架完全不用动。
带工人约束的混合流水车间调度问题：多目标进化算法与Matlab实现
车间里的调度问题做过的人都知道难缠的地方不在设备而在人。设备参数是死的工人不是——技能不同、熟练度不同、上班时段不同同一个工件在不同工人手里的加工时间能差出百分之二三十。这就是带工人约束的混合流水车间调度问题HFSSPW让人头疼的地方既要排机器又要排工人两套约束叠在一起目标还不止一个。我最近用Matlab实现了一套基于融合启发式解码的多目标进化算法来求解HFSSPW效果还不错。这篇博文把整个思路、建模过程、关键代码逻辑和踩过的坑完整记录下来适合正在做生产调度优化、写毕业论文或者在企业里搞智能制造排产方案的朋友参考。1. HFSSPW问题的数学模型从车间现场到约束方程1.1 混合流水车间到底是什么混合流水车间Hybrid Flow ShopHFS是经典流水车间Flow Shop的扩展。经典流水车间是一串机器排成一条线每个工件按同一顺序依次经过每台机器混合流水车间则在某些阶段布置了多台并行机工件在某个阶段只需要选择其中一台机器加工。现实中的机加工车间、PCB组装线、制药包装线基本都是这种形态。举个例子一个典型的机加工车间可能有三个阶段下料、粗加工、精加工。下料阶段一台锯床粗加工阶段三台不同型号的铣床精加工阶段两台磨床。每个工件都要依次经过这三个阶段但在粗加工阶段可以任选一台铣床。这样问题就变成了两层次决策第一阶段给每个工件确定加工顺序第二阶段给每个工序选择合适的机器。如果车间里还有工人操作限制每个工人在同一时刻只能操作一台机器而且不是所有工人都会操作所有机器那就成了HFSSPW。1.2 工人约束怎么进入模型我最初只考虑了机器约束结果排出来的方案在车间根本执行不了——精加工阶段的两台磨床分别需要不同技能的工人而我排的时段里只有一个会磨床的师傅在岗另一台机器只能空转。所以工人约束必须显式建模不能事后补救。HFSSPW里的工人约束主要体现在三个维度技能矩阵工人w是否会操作机器m记为一个0/1变量。工人不会操作某台机器那台机器在这个时段就不能指派给他。熟练度差异即使两个工人都能操作同一台机器加工时间也可能不同。可以用工人-机器对应的加工时间系数来表示比如熟练工的加工时间是标准时间的0.8倍新手是1.2倍。可用时间窗工人不是24小时都在岗有班次、休息、换班。这比机器的可用时间窗更复杂因为同一班次内工人的可用时间段可能是交错的。数学上这个问题可以这样描述。给定n个工件J1到Jn、s个加工阶段stage1到stages、每个阶段有m_k台并行机、车间里有w个工人。每个工件j在第k个阶段的机器i上由工人l加工的时间记作p_{j,k,i,l}。如果工人不会操作这台机器这个加工时间为无穷大。决策变量有三个工序排序π、每道工序的机器分配M、每道工序的工人分配W。约束如下同一工件的工序顺序约束工件在第k阶段完工后才能进入第k1阶段。机器容量约束一台机器在同一时刻只能加工一个工件。工人容量约束一个工人同一时刻只能操作一台机器。技能匹配约束工人l被指派到机器i的前提是技能矩阵中对应元素为1。可用时间约束工序在机器上的开始时间必须落在工人l的可用时间窗口内。1.3 多目标定义与评价指标为什么要用多目标算法因为实际车间排产从来不是只追一个指标。我接触过的企业里最常见的三个目标分别是最大完工时间所有工件完成加工的总时间英文叫makespan。这个指标直接决定了订单的最短交付周期。总拖延时间每个工件相对交期的延误时间之和。制造业里逾期交付要赔钱这个很重要。工人负载均衡不同工人之间的总工作量差异。为了平衡工人绩效车间主任通常会要求负载不要差太多。可以用最大工人负载与平均工人负载的差值来衡量。这三个目标经常是矛盾的缩短makespan可能让某个熟练工忙死新手闲着减少总拖延可能要让某个瓶颈设备超负荷运转。多目标进化算法的作用就是找到一组Pareto最优解让决策者根据现场情况在目标之间权衡。在Matlab实现里我定义了一个适应度评估函数输入一个调度方案输出三个目标值。用结构体存储每次调度的完整时间表这样后面做Gantt图也方便。2. 为什么选多目标进化算法NSGA-II框架与HFSSPW的适配逻辑2.1 问题特性与算法匹配分析HFSSPW属于NP-hard问题精确算法只能解决极小的规模。我做实验时用CPLEX求解10个工件、3个阶段、8台机器、6个工人的小实例跑了半个小时还经常找不到最优解。所以大规模场景基本只能靠启发式和元启发式。在多目标元启发式里NSGA-II带精英策略的非支配排序遗传算法是经过大量工程验证的成熟框架。它好在哪里第一非支配排序能同时维护多个目标的解集不需要人为设定加权系数第二拥挤距离机制保证解集在Pareto前沿上分布均匀避免所有解挤在一小段前沿上第三精英保留策略保证算法收敛过程中最优解不会丢失。当然NSGA-II和NSGA-III我都试过。NSGA-III用参考点来维持多样性在高维目标4个以上下更优秀但HFSSPW常用的是2到3个目标NSGA-II的拥挤距离已经够用而且实现更简洁、运行更快。所以最后我选择了NSGA-II作为主框架。2.2 染色体编码与种群初始化编码方式是进化算法里最关键的决策之一直接决定算子设计和解码难度。HFSSPW的决策空间包含工序顺序、机器分配、工人分配三层怎么编码很有讲究。我采用的是基于工件排列的编码permutation-based encoding它的思路是染色体上一共有 (n) 个位置每个位置是某个工件的编号工件号出现的次数等于它在流水线上经过的工序数。假如有5个工件每个工件3道工序那么染色体长度为15工件1出现3次、工件2出现3次……解码时从头到尾扫描染色体第 (t) 次出现的工件j就代表该工件的第t道工序。这样做的好处是天然满足同一工件的工序次序约束不需要在解码时做可行性修复。至于机器和工人不放在染色体上而是在解码阶段用启发式规则实时决定。这就引出了本文的核心——融合启发式解码。种群初始化方面直接随机生成 (N) 条随机的工件排列染色体然后全部用启发式解码来评估。有朋友建议我用NEH启发式Nawaz-Enscore-Ham生成一部分初始解来加速收敛这个思路我采纳了后面第三节详细说。2.3 非支配排序、拥挤度与选择算子NSGA-II的骨架在Matlab里实现起来并不复杂核心就三个模块。第一个是非支配排序。对种群里的每个个体计算它被多少个个体支配支配计数和它支配了哪些个体支配集合。循环取出所有支配计数为0的个体归入第1层Pareto前沿然后把这些个体的支配集合里的成员支配计数减1再取下一批为0的归入第2层如此循环直到所有个体分层完毕。判断个体A支配个体B的条件是A的所有目标值都不比B差小于等于并且至少有一个目标严格优于B。注意这是一个偏序关系不是简单比大小。我在Matlab里用的是一个双层循环最开始没加向量化处理500个种群个体、迭代300代时间开销肉眼可见地增长。后来把目标值矩阵化循环次数大幅下降速度提升明显。第二个是拥挤距离计算。对同一Pareto前沿层里的个体按每个目标值排序边界个体的拥挤距离设为无穷大中间个体的距离等于相邻两个个体在该目标上的归一化差值之和。距离越大表示周围越空旷多样性贡献越大。第三个是锦标赛选择。每次随机从种群中抽取两个个体先比Pareto层级层级小的获胜层级相同比拥挤距离距离大的获胜。这个设计保证了算法在收敛和多样性两个方向上的平衡。Matlab的randperm函数可以方便地实现锦标赛选择但要注意每次选择的随机性要在不同代之间独立否则容易陷入局部收敛。2.4 交叉和变异的Matlab实现交叉算子我用了顺序交叉Order CrossoverOX它对排列编码的效果比较稳定。具体做法是随机选两个交叉点把父代P1在这两个点之间的基因片段先复制给子代C1然后从父代P2中按顺序取出那些不在该片段内的工件编号依次填入C1的剩余位置。这个过程的Matlab实现大约15行代码核心是利用ismember函数判断某个工件编号是否已经在片段中。变异算子用的是交换变异随机挑选染色体上的两个位置交换工件编号。有文献说对排列编码使用插入变异效果更好就是把一个位置的工件编号拿出来插入到另一个位置。我在实验里对比过两种变异交换变异的收敛速度略慢但最终Pareto前沿的多样性更好所以保留了交换变异。这里给一个交叉率的参考值我试过0.6到0.90.8附近比较稳定变异率0.1到0.2之间表现不错低于0.05时算法很容易早熟。当然这只是针对我构造的测试算例不同规模的具体问题还是得自己做参数实验。3. 融合启发式解码解决工人约束的关键设计3.1 解码的基本流程解码是把染色体翻译成实际调度方案的过程也是整个算法里工程味道最浓的部分。普通的解码方式是按染色体顺序把工序逐个插入到当前最早可用的机器上这种方式在无工人约束的HFS里没问题但一旦引入工人约束机器最早可用并不代表工人也有空必须把人和机器一起安排。我的解码流程分四步按染色体顺序取出当前要安排的工序确定它属于哪个工件的哪一道工序以及该工序对应哪个加工阶段。扫描该阶段所有可用机器筛选出在当前时刻之后有可用时间窗口的机器。对每台候选机器扫描所有技能匹配且在该时段可用的工人计算一个可能完工时间。选择可能完工时间最小的机器工人组合把工序插入更新机器和工人的空闲时间表。这其实就是把机器分配和工人分配合并成了一个启发式规则的过程。之所以叫融合是因为传统的两步式解码会先选好机器、再选工人容易产生一端最优另一端吃亏的情况。合并成一步后设备和人力资源作为一个整体来决策。3.2 机器选择与工人分配启发式规则在第四步选择哪个机器工人组合时我测试过几种规则总结下来效果排名如下规则描述适用场景实验排名最早完工时间ECT选择当前工序最早加工完成的组合目标以makespan为主1最早可用机器EAM选择最早空出的机器目标均衡性要求高3最短加工时间SPT选择加工时间最短的组合瓶颈设备明显2工人负载最小选择当前累计负载最小的工人目标包括负载均衡2与SPT并列我最终使用的是复合规则先按最早完工时间筛选出前3个候选组合再从中选择工人累计负载最小的那个。这样可以兼顾makespan和负载均衡两个目标。注意这里说前3个是经验值没必要对整个候选集合做完整排序那样计算量太大。3.3 用NEH启发式生成初始解NEH启发式是解决流水车间调度问题最经典的构造式启发式它的核心思想是先把所有工件按总加工时间降序排列然后逐个插入到一个已有的部分调度里每次尝试所有可能插入位置选择使目标函数最优的位置。我把它改造成了两阶段版本来做HFSSPW初始化。第一阶段对每个工件计算它在所有阶段、所有机器上的平均总加工时间考虑工人技能系数按从大到小排序。第二阶段依次取出排序后的工件尝试插入到当前染色体的所有可能位置用启发式解码评估新染色体的makespan选择makespan最小的插入位置。这样生成的初始解质量远高于纯随机解。有一点需要提醒用NEH生成的全部初始解会让初始种群过早集中导致多样性下降。我的做法是只有20%的初始个体用NEH生成其余80%保持随机。这个混合比例也值得在具体问题上做微调。3.4 解码后处理与局部改进启发式解码给出的方案不一定局部最优我加了一个轻量的后处理对解码产生的工序序列做两次局部搜索。第一次把每个阶段中负载最重的机器上的工序与负载最轻的机器上的工序尝试交换第二次在满足工件工序约束的前提下将某道工序的开工时间向前移动检查是否能空出更长的连续空闲段。这一步叫左移交换。这个后处理的关键收益是能在不破坏多目标特性的前提下显著改善Pareto解集的质量。我在5个工件的小案例上测试加上后处理之后IHR超体积指标平均提升了8%左右。代价是每个个体的解码时间多了大概15%但整体在可接受范围内。4. Matlab代码实现关键模块与核心代码解读4.1 数据结构的定义Matlab里没有传统意义上的类我习惯用结构体组织数据。核心数据结构有三个problem、population和schedule。problem存储问题实例的全部参数包括problem.n 5; % 工件数 problem.s 3; % 阶段数 problem.m [1 3 2]; % 每个阶段的机器数量 problem.w 4; % 工人数 problem.procTime cell(problem.n, problem.s); % 加工时间矩阵 problem.skill randi([0 1], problem.w, sum(problem.m)); % 技能矩阵 problem.avail ones(problem.w, 24); % 工人的每小时可用性这里procTime用了cell数组因为每个工件在每个阶段的机器数不同不能用普通三维数组统一存储。每个元素是一个 (m_k \times w) 的矩阵表示在不同机器、不同工人组合下的加工时间。如果某个工人不会操作某台机器就把对应元素设为inf解码时天然会排除这个组合。population存储种群个体每个个体有chrom、machineAssign、workerAssign、obj等字段。schedule则存储一次完整解码的各类时间信息包括每个工序的开工时间、完工时间、工人分配、机器分配画Gantt图时直接读取这个结构体。这里有一个容易被新手忽略的点Matlab的struct数组在横向拼接和索引时非常吃内存当种群规模达到500、染色体长度为30以上时反复赋值会导致性能急剧下降。我的解决办法是把每个个体的关键属性存为普通数组矩阵只有schedule这种需要可视化的大结构体才单独保存。4.2 主循环结构整个算法的主循环比较清晰这里给出简化版的伪代码逻辑% 初始化 pop initializePopulation(problem, popSize, initMethod); [pop, F] evaluatePopulation(pop, problem); % 进化主循环 for gen 1:maxGen % 锦标赛选择 matingPool tournamentSelection(pop, F, popSize); % 交叉和变异 offspring crossover(matingPool, pc); offspring mutation(offspring, pm); % 解码评估 [offspring, F_off] evaluatePopulation(offspring, problem); % 合并父子种群非支配排序选择前popSize个 combined [pop, offspring]; combinedF [F; F_off]; [combined, combinedF] nonDominatedSort(combined, combinedF); pop selectBest(combined, combinedF, popSize); F combinedF(1:popSize, :); end注意交叉和变异都是对染色体数组进行操作操作完再调用decode函数生成schedule并计算目标值。这个分离设计很重要——进化算子和问题模型解耦以后如果想换编码方式或者加约束只需要改decode函数不需要动进化骨架。4.3 约束处理和可行性校验解码时最头痛的问题是合法性校验因为机器约束和工人约束互相嵌套。我的做法是在插入工序时维护两个时间表machineFreeTime是每个阶段每台机器的下一个可用时刻workerFreeTime是每个工人下一个可用时刻。插入工序前先找出当前时刻所有候选机器工人组合中当前可以开工的集合。这里的关键逻辑在判断可以开工工序的潜在开始时间 (t_{start}) 必须同时满足机器空闲、工人空闲、工人在此时段可用这三个条件。工人可用性如果细化到时间窗就不能只用一个nextFreeTime标量需要用区间列表来表示。我实现了一个函数findEarliestSlot输入开始时间和持续时间搜索工人的可用区间列表找到第一个能容纳该工序的窗口。这个函数是代码里最容易被写错的地方。如果工人的可用区间是有多个时段的简单的取下一个空闲时刻很可能落在一个不可用区间里导致排出来的方案无法实际执行。最开始我没考虑到这一点排出的方案机器利用率很好看但拿到车间一核对工人根本没有在岗全部作废。后来我专门写了一个单元测试函数生成随机问题实例并校验所有工序是否满足工人可用性才把这个坑填上。4.4 实验设计与性能验证实验设计这块我构造了三组不同规模的算例小规模5个工件3个阶段6台机器4个工人中规模10个工件4个阶段10台机器6个工人大规模20个工件5个阶段16台机器8个工人每组算例随机生成10个实例有技能约束和没有技能约束各一组。为什么要做有/无技能约束的对照因为可以单独观察工人约束对算法性能的影响程度这是论文审稿人经常会问的对照实验。性能评价指标我用了三个超体积指标HV、世代距离GD和反转世代距离IGD。Matlab里实现HV需要先确定参考点一般取各目标单独优化时的最差值向量GD和IGD都需要知道真实的Pareto前沿对大规模问题这是未知的所以我的做法是用长时间运行的NSGA-II迭代5000代的解集近似作为参考前沿。算法对比方面除了纯NSGA-II我还对比了带融合启发式解码的NSGA-II也就是本文方案和一个最简单的经典规则调度方法。实验结果很明确带融合启发式解码的方案在HV和IGD上明显优于纯NSGA-II在小规模算例上尤其突出说明启发式解码确实帮助算法更高效地利用了问题结构信息。5. 调参经验与工程实践中的坑5.1 种群规模和迭代次数的选择调参是最磨人的环节。对HFSSPW这种情况种群大小我建议从50开始试逐步加到100、200、500。最终我发现50个个体对5个工件的小算例足够但到20个工件的大算例就明显不够用Pareto前沿会稀疏得很厉害。20个工件的算例我最终用了200个个体。迭代次数要看收敛曲线。我的经验做法是运行算法并每隔10代记录一次HV值画一条HV-迭代次数曲线。当曲线在50代之后基本不再上升说明已经收敛如果200代还在涨那就继续加长。不要盲目迷信大迭代次数计算时间也是成本。有一次我跑到800代发现HV还有上升趋势但每轮解码加上后处理已经很慢最终在300代到400代之间取了折中。5.2 参数敏感性分析我做了几个关键参数的敏感性测试结论如下交叉率0.6到0.9的范围内HV值差异不大但交叉率偏低时解集多样性差一点。变异率超过0.3时算法近乎随机搜索收敛性急剧恶化低于0.05时容易陷入局部前沿。NEH初始化比例从0%提高到30%HV明显改善继续提高反而导致种群多样性下降中规模算例上HV降低了4%左右。后处理开关的对比显示在工人负载均衡目标上后处理带来的改进最明显因为负载再分配是它的直接效果。这些参数的取值不是全局最优的但至少在我构造的算例集上表现稳定。做研究时最好针对自己的算例重新做一遍这个小实验参数空间不大跑起来很快。5.3 可视化与调试技巧Matlab做调度问题最大的优势就是可视化方便。我最终用Gantt图甘特图展示调度结果画法是自己写了一个函数遍历schedule结构体里的每个工序用rectangle函数按开工时间到完工时间绘制色块机器和工人用不同的行来表示。这里有一个要特别注意的点绘制工人行的Gantt图时同一个工人在不同机器上执行的工序要在同一行上展示但颜色按机器区分这样才能看出工人是否来回切换太频繁。调试方面我最常用的技巧是生成小规模实例3个工件、2个阶段、2台机器、2个工人人工手算出最优方案然后跟算法输出对比。这个验证方法虽然笨但非常有效——我靠它发现过两个隐性bug一个是在工人技能不匹配时inf没有被正确传递到目标函数里另一个是编码解码时工件工序顺序被意外打破导致同一工件的工序并行加工这在流水车间里是不允许的。5.4 代码性能优化最后聊一下Matlab代码性能。调度问题解码是整个算法最耗时的部分优化它的收益最大。第一避免循环嵌套过深。解码时对每个工序扫描所有机器和工人如果实现不当会形成三层循环。我的做法是预先对每个阶段整理出候选机器工人组合列表解码时直接遍历这个列表而不是每次都现找。第二向量化目标值计算。非支配排序和拥挤距离计算尽量用向量操作不要在每个目标维上都跑一个for循环。我试过把目标计算从逐个个体循环改成矩阵整体计算速度提升接近2倍。第三善用sparse矩阵。机器空闲时间表和工人空闲时间表如果用稀疏矩阵存储在大规模算例里不仅省内存某些操作比如查找最早空闲时刻还能用find函数向量化完成。这些优化做完后中规模算例10个工件、100个个体、300代的完整运行时间从原来的20分钟降到了8分钟左右算是可以接受的工程速度。如果继续用parfor做并行评估还能再压缩一些但那样需要额外注意随机数种子的可控性我为了确保实验结果可复现最终没有在主实验里启用并行。整个项目做下来我的核心体会是HFSSPW这类问题算法框架是通用的但真正决定解质量的往往是在解码这一层做的功夫。融合启发式解码相当于把领域知识直接注入进化过程让每个个体在评估阶段就吸收了车间调度积累的经验规则进化算法只需要在这个高质量的搜索空间里做多样化探索两者的配合比单纯加大种群的收益更明显。这套Matlab代码的组织方式也留了扩展口子——如果后续要加入能耗目标或者考虑工件搬运时间只需要在problem结构体里加字段、在decode函数里补逻辑就行主进化框架完全不用动。
