前阵子帮我一个做生产线的朋友复现调度方案他那边十几台设备几十道工序机器之间还能互相替换传统排程软件根本啃不动。我顺手把多目标优化里两套最经典的算法——MOEAD 和 NSGA-II——都用 Python 实现了一遍用来求解柔性车间调度问题FJSP。这篇就是把完整的思路、代码框架、参数调节和踩坑记录整理出来给准备入坑调度优化、或者想拿 FJSP 练手多目标算法的朋友一个能直接抄作业的参考。我的目标是让这篇内容做到小白能看懂原理、熟练工能直接拿去改代码。FJSP 本身不复杂但“柔性”这两个字会带来一堆连锁反应多目标也不是多跑几个单目标就完事。下面我从问题建模开始逐步拆到算法细节和 Python 工程实现。1. 柔性车间调度为什么“柔性”会带来麻烦1.1 从固定车间调度说到柔性二字先回顾一下最经典的车间调度问题 JSP有若干个工件每个工件有固定顺序的若干道工序每道工序只能在一台指定机器上加工。比如工件 A 的第一道工序只能在铣床上做第二道只能在磨床上做没得选。这时候我们要做的就是把每道工序排到哪一天、几点开始、几点结束让整体指标最优。FJSP 比 JSP 多了一个自由度每道工序可以在多台机器中任选一台来加工而且不同机器上的加工时间还不一样。这就等于你在排工序顺序的同时还得给每道工序挑机器。两个决策交织在一起复杂度一下子蹿上去了。举个简单的例子一个工件有三道工序第一道工序在车床、铣床、加工中心上都能做耗时分别是 5 分钟、3 分钟、2 分钟。看起来加工中心最快但加工中心可能同时是其他工件的瓶颈死命把活往它身上堆整体完工时间反而更差。这就是 FJSP 有意思的地方局部最优不一定是全局最优机器选择必须跟工序排序一起考虑。所以把 FJSP 当成“排程”来做很容易翻车。它是一个典型的大规模组合优化问题解空间呈指数膨胀用穷举法做 10 个工件、10 台机器就已经彻底没戏了。这正是元启发式算法的用武之地。1.2 多目标为什么不是“多跑几次”我最初做这个项目的时候犯过一个典型错误把“完工时间最短”作为唯一目标跑完一轮得到一个看起来不错的甘特图。结果朋友看了一眼说你这方案不行3 号机累死其他机器闲得发慌这样没法排产。这才意识到实际车间调度几乎都是多目标的。我当时选了三个有代表性的目标目标含义实际意义最大完工时间 makespan所有工件全部完成的时间客户订单的交期机器总负载 total load所有机器加工时间之和整体能耗和刀具消耗关键机器负载 max load单台机器最重的负载瓶颈工序和机器利用率这三个目标之间有很强的冲突性。你把 makespan 压到最短必定要把活往快机器上集中于是 max load 猛涨你想让各台机器负载均衡某些工件就可能被安排到慢机器上整体交期又拉长。多目标优化的意义就是找出这种冲突均衡下的一组帕累托最优解而不是一个单一答案。这里有个关键认知多目标不是说把三个目标加权成一个数跑若干次取不同权重。真正的多目标算法能一次性得到一个帕累托前沿面让决策者从一批候选方案里根据偏好去选。这个思路贯穿整篇文章也是后面为什么同时用 MOEAD 和 NSGA-II 的原因。2. MOEAD 与 NSGA-II 为什么各火各的2.1 NSGA-II 的排序思想NSGA-II 的全称是非支配排序遗传算法第二代。核心逻辑很简单每次迭代时先把种群里的个体按“谁支配谁”分成一层层的前沿面第一层是最优的、不受任何其他个体支配的解第二层次之依此类推。然后不同层个体按层数高低依次被选入下一代。这引出了支配关系的定义解 A 支配解 B当且仅当 A 在所有目标上都不比 B 差而且至少在一个目标上严格优于 B。如果 A 在某目标更好、B 在另一目标更好两者就互不支配一起留在第一前沿面。光有非支配排序还不够否则第一前沿面可能挤满一堆扎堆的相似解。NSGA-II 用拥挤距离来解决多样性问题对于同一层的个体计算它们在目标空间中的密集程度距离大的个体优先保留从而让帕累托前沿覆盖得更均匀。因为 NSGA-II 用排序的方式刻画多目标之间的关系它对目标个数不太敏感三个目标跑起来依然稳定而且实现起来门槛低特别适合入门。至今它依然是调度问题中使用频率最高的多目标算法之一。2.2 MOEAD 的分解思想MOEAD 的全称是基于分解的多目标进化算法思路和 NSGA-II 完全不同。它把多目标问题拆成一堆单目标子问题预先在目标空间里生成一组均匀分布的权重向量每个权重向量对应一个子问题然后用切比雪夫聚合函数或者加权和法把多目标合并成一个带权重的标量值。每个子问题只关注自己权重方向上的标量值最小化。有趣的是相邻权重向量对应的子问题最优解往往也相近所以 MOEAD 给每个权重向量划定一个邻域范围个体只在邻域内共享信息、做交叉变异。这相当于让每个子问题周围有一小撮“邻居”互相帮衬整体上能同时逼近帕累托前沿的不同区段。MOEAD 的收敛速度通常比 NSGA-II 快因为它实际上把多目标优化转化成了并行的一组单目标优化而且邻域机制让信息只在相近方向之间流动不容易出现“一锅乱炖”。代价是权重向量生成、邻域大小、聚合函数的选择都需要仔细调参数比 NSGA-II 略敏感。2.3 选哪个我全都要从实际代码量来看两个算法有相当一部分公共模块可以复用种群表示、FJS解码、目标计算、交叉变异算子。区别只在于环境选择那一层。所以我的做法是在同一套 FJSP 代码里同时实现两种算法互相做对照组。这样有几个好处第一个是验证算法实现有没有 bug如果一个算法结果异常但另一个正常排查范围大大缩小第二个是可以直观看到两种算法的解质量差异和收敛速度差异在真实项目中才能选合适的方案。后文我会给出一套能跑通的对比流程。3. 建模与编码FJSP 的第一步不能错3.1 输入格式设计在写 Python 代码之前先把 FJSP 的输入数据结构化。我用一个列表来表示一个算例结构如下# 每个元素代表一个工件 # 每个工件是一个工序列表 # 每个工序是一个“可用机器耗时”列表例如 [(机器编号, 耗时), ...] data [ [ # 工件 0 [(0, 3), (1, 2)], # 工序0可在机器0(3小时)或机器1(2小时)上做 [(1, 4), (2, 5)], # 工序1可在机器1(4小时)或机器2(5小时)上做 ], [ # 工件 1 [(0, 5), (2, 3)], [(1, 2), (2, 4)], ], [ # 工件 2 [(0, 2), (1, 4)], [(2, 6), (0, 3)], ], ]这个格式简单直白后续无论读 txt 文件还是直接手写算例都能统一转换。实际项目中常用 benchmark 算例比如 Kacem 系列、Brandimarte 系列都能解析成这种结构。一定要把机器编号统一从 0 开始防止后面数组索引错位引发莫名的越界错误。3.2 基于工序基于机器的双段编码FJSP 的每个解要同时表达“工序按什么顺序加工”和“每道工序用哪台机器”。我用经典的双段编码工序排序段 OSoperation sequence一个长度为总工序数的列表里面是工件编号每个工件编号出现多少次等于该工件的工序数。例如[0, 1, 2, 0, 2, 1]表示先安排工件0的第一道工序再安排工件1的第一道工序然后是工件2的第一道工序接着是工件0的第二道工序……这种编码天然满足工件内部工序的先后约束。机器选择段 MSmachine selection同样长度为总工序数每个位置记录该工序在其候选机器列表中的下标。注意不是直接存机器编号而是存下标这样不同工序可选机器数量不一致也能统一处理。我把两个段打包成一个个体对象在进化过程中两个段同步参与交叉变异。为什么用这种编码因为它解码后一定能生成合法调度不需要后续修修复复地修补约束省心很多。3.3 解码与调度实现解码就是把 OS 和 MS 翻译成实际的时间安排。解码质量直接决定算法优化效果的上限。我实现了一个基于“插入式”的活性解码def decode(data, process_seq, machine_seq): machine_num max(m[0] for job in data for op in job for m in op) 1 job_count len(data) machine_finish [0.0] * machine_num # 每台机器当前最后完工时间 job_op_idx [0] * job_count # 每个工件已推进到的工序下标 job_finish [0.0] * job_count # 每个工件当前最后完工时间 for i, job_id in enumerate(process_seq): op_idx job_op_idx[job_id] job_op_idx[job_id] 1 candidates data[job_id][op_idx] m_idx machine_seq[i] % len(candidates) m_id, duration candidates[m_idx] # 开始时间 max(机器空出来时间, 该工件上一道工序完成时间) start max(machine_finish[m_id], job_finish[job_id]) finish start duration machine_finish[m_id] finish job_finish[job_id] finish makespan max(job_finish) total_load sum(machine_finish) max_load max(machine_finish) return makespan, total_load, max_load这个解码是逐工序插入逻辑简单运行速度快。如果要进一步优化可以在机器空闲窗口里尝试插空而不是只往机器末尾排能得到更紧凑的调度。插空操作虽然能减少 makespan但也会显著拖慢解码速度我建议先用上面的简单版本跑通流程再根据性能需求决定要不要升级。4. Python 实现框架和关键代码4.1 类和数据结构工程上我不会把所有逻辑揉成一个巨大的脚本而是拆成清晰的三块问题实例类、个体类、算法类。核心数据结构如下class FJSPInstance: def __init__(self, data): self.data data self.job_count len(data) self.op_count sum(len(job) for job in data) self.machine_num max(m[0] for job in data for op in job for m in op) 1 def decode(self, process_seq, machine_seq): # 用上文的decode逻辑 pass class Individual: def __init__(self, instance): self.process_seq [] # OS段 self.machine_seq [] # MS段 self.objectives [] # 三个目标值 self.rank 0 # NSGA-II非支配排序层 self.crowd 0.0 # NSGA-II拥挤距离 self.weight None # MOEAD权重向量 self.neighbor [] # MOEAD邻域索引个体里把两种算法需要的辅助字段都放进去虽然会多占一点内存但写起来方便不用在算法之间来回转换数据结构。4.2 目标函数和约束处理FJSP 的约束有两个机器同一时刻只能加工一道工序、同一工件内部的工序有先后顺序。我的解码方式天然保证了这两点start max(machine_finish[m_id], job_finish[job_id])就是约束处理的全部。三个目标都在 decode 里一次算完。这里有个工程细节目标值计算是进化算法的内循环一个种群 200 个个体迭代 300 代就要解码 60000 次。所以解码函数必须尽量精简避免在循环里写复杂的列表推导或频繁创建对象。我实测过用 Python 的 list 和简单循环60000 次解码在三台机器小算例上大概十几秒算是可以接受如果算例规模大到几千道工序就要考虑改用 numpy 向量化或加缓存了。4.3 初始化策略初始种群的质量对 MOEAD 和 NSGA-II 的影响都很大。我用了三种方式混合全局选择法对于每道工序在所有可选机器中选择使“当前时间加工时间”最小的那台偏向制造出较短的 makespan。局部选择法只考虑当前工件做完这道工序的最早完成时间偏向局部决策。完全随机MS 段随机选机器下标OS 段随机洗牌保证种群多样性。三种方式按一定比例混合生成初始种群。纯随机初始化的好处是多样性高但收敛慢全是启发式初始化收敛快但容易过早失去多样性。我一般让 70% 的个体走随机30% 走启发式效果相对均衡。5. NSGA-II 与 MOEAD 的进化循环怎么写5.1 NSGA-II 排序与拥挤度NSGA-II 一次迭代的核心流程是父代种群通过锦标赛选择选出两个个体交叉变异生成一个子代子代和父代合并再非支配排序按层和拥挤度挑选出下一代。非支配排序代码不复杂def fast_non_dominated_sort(pop): fronts [[]] for p in range(len(pop)): for q in range(len(pop)): if p q: continue p_dom_q all(pop[p].objectives[i] pop[q].objectives[i] for i in range(len(pop[p].objectives))) and any(pop[p].objectives[i] pop[q].objectives[i] for i in range(len(pop[p].objectives))) q_dom_p all(pop[q].objectives[i] pop[p].objectives[i] for i in range(len(pop[p].objectives))) and any(pop[q].objectives[i] pop[p].objectives[i] for i in range(len(pop[p].objectives))) if p_dom_q: pop[p].dominates.append(q) elif q_dom_p: pop[p].dominated 1 if pop[p].dominated 0: fronts[0].append(p) # 依次生成后续层 return fronts实际工程里上面的双重循环是 O(n2)种群一大就很吃力。我建议用列表记录每个个体被谁支配先统计支配计数和支配列表再逐层剥离复杂度能降不少。我在这里省略了完整优化但代码结构要预留改动的空间。拥挤距离的计算方法是对同一前沿面的个体按某个目标排序两端个体的拥挤距离设为无穷大中间个体的距离等于相邻目标差值之和再按目标范围归一化。距离大说明这个解周围的同伴少优先保留它避免前沿面局部扎堆。5.2 MOEAD 邻域与聚合函数MOEAD 的第一步是生成权重向量。对于三目标问题我用均匀网格法def generate_weights(div, m3): # div是每个维度分割的份数 from itertools import combinations weights [] for comb in combinations(range(div m - 1), m - 1): w [comb[0]] for i in range(1, m - 1): w.append(comb[i] - comb[i-1] - 1) w.append(div m - 1 - comb[-1] - 1) weights.append([x / div for x in w]) return weights权重向量生成后任意两个权重向量之间的欧氏距离决定了邻域关系。我给每个子问题保留 T 个最近邻一般取种群规模的 10%。子问题的目标值用 Tchebycheff 聚合函数计算def tchebycheff(individual, weight, z): return max(weight[i] * abs(individual.objectives[i] - z[i]) for i in range(len(z)))其中 z 是当前所有目标中已经达到的最优值构成的一个参考点。MOEAD 每轮进化要先从当前种群中更新 z再从邻域里随机选个体进行交叉变异子代如果让某个邻域子问题的 Tchebycheff 值变小就替换掉该邻域内最差的个体。这个过程可视化为前沿面一步步向外推进收敛路径很清晰。5.3 交叉变异细节FJSP 的交叉要特别小心不能让 OS 段交叉后违背工件的工序顺序约束。我用的是 POX基于工序的交叉思想随机把工件编号分成两组 S1 和 S2父代 A 中属于 S1 的工件顺序保留父代 B 中属于 S2 的工件顺序按原序填充到 A 的剩余位置。这样既引入父代 B 的信息又保证每个工件出现次数不变。MS 段相对简单用均匀交叉对每个基因位随机选择继承父代 A 或父代 B 的机器下标因为每个位置本身都是合法下标交叉后天然合法。变异方面OS 段采用两点交换MS 段采用随机点变异。变异率我通常设定在 0.1 附近。太低了容易早熟太高会把好解打碎这个在后文调参部分细说。6. 实验调参和避坑实录6.1 我踩过的三个坑第一个坑是参考点 z 的更新。MOEAD 里如果 z 更新得太激进比如某一代偶然出现一个超优值后续所有 Tchebycheff 值都会变大导致整个种群一下子就丧失了选择压力。我的解决办法是只在 z 确实优于历史值时更新而不是无条件刷新。听起来是小细节实际对 MOEAD 的稳定性影响巨大。第二个坑是 NSGA-II 的拥挤距离用错了对象。我一开始把拥挤距离算在实数空间而非目标空间里导致相同层内两个相似工序序列被误判为拥挤丢失了大量有价值的解。记住拥挤距离衡量的是目标空间里的稀疏程度而不是染色体相似度。第三个坑是种群规模太小导致两个算法都崩溃。有一次我用 50 个个体跑 MOEAD权重向量之间邻域重叠太紧密整个群体收敛到同一个小区域帕累托前沿连一半都没铺满。后来我把种群规模提到 200问题立刻缓解。多目标优化不能省种群规模这是用计算时间换搜索覆盖的必然取舍。6.2 参数配置建议我在三个目标、三道工序到二十道工序的小规模算例上做过对比实验推荐参数如下参数NSGA-II 推荐值MOEAD 推荐值种群规模150-250200-300迭代次数200-400150-300交叉率0.8-0.90.8-0.9变异率0.05-0.150.05-0.15邻域大小不适用种群规模的5%-15%权重向量分割不适用每维20-30份MOEAD 收敛快、代际消耗低可以适当多给初始多样性和邻域搜索能力NSGA-II 则需要更多迭代次数来让排序选择充分生效。这个组合不是绝对的大规模 FJSP 算例往往需要把种群规模再翻倍。6.3 结果展示与对比我跑完实验后用 matplotlib 把两个算法的帕累托前沿投影到二维上展示X 轴是 makespanY 轴是最大机器负载。总体规律是 MOEAD 在迭代早期就能快速逼近前沿但前沿两端容易稀疏NSGA-II 迭代前期慢半拍但最终前沿面覆盖更均匀尤其是我增加到三个目标后NSGA-II 的分布性优势更明显。对一个真实小型算例一次跑完 300 代MOEAD 的耗时约为 NSGA-II 的 70%但 NSGA-II 最后给出的候选方案更适合实际排产因为它在目标均衡上有更多细分选择。如果你的场景对实时响应要求高可以用 MOEAD 快速出一版方案如果你要做详细生产计划且能多等两分钟NSGA-II 更靠谱。最后再分享一个实用小技巧无论用哪种算法跑完一轮后把获得的非支配解放进 CSV 文件再用甘特图画图脚本可视化。多目标优化的直接输出是一堆数值但现场生产负责人关心的永远是“这台设备几点开工几点结束”。我在可视化里发现过好几处解码逻辑的小毛病比如同一台机器在同一时间被排了双份工序这种问题靠看数字根本发现不了。所以做调度别光盯着算法最后一步可视化绝不能省。
