FJSP 入门与 NSGA-II 实践从问题到代码这篇博客面向入门学习者先介绍 FJSP柔性车间调度问题再说明 NSGA-II 多目标进化算法最后结合本项目代码梳理如何完成求解与可视化。项目代码地址https://github.com/aslongaslihappy/NSGA-II-FJSP1. FJSP 是什么FJSPFlexible Job Shop Scheduling Problem柔性车间调度是经典调度问题的扩展。与传统车间调度不同FJSP 允许每道工序在多台机器中选择一台进行加工因此具有更强的灵活性但也带来更高的搜索复杂度。1.1 基本元素工件Job由多道工序组成工序Operation工件必须按顺序加工的步骤机器Machine每道工序可选的加工设备集合1.2 典型约束同一台机器同一时间只能加工一道工序同一工件的工序必须遵循先后顺序1.3 常见优化目标多目标FJSP 通常是多目标优化问题本项目关注两类目标Makespan完工时间所有工件完成的总时间TEC总能耗加工能耗 机器空闲能耗由于目标之间相互冲突实际求解的是Pareto 最优解集合即一组“互不支配”的解。2. NSGA-II 简介NSGA-IINon-dominated Sorting Genetic Algorithm II是经典的多目标进化算法核心思想是非支配排序将解分层第一层是最优的非支配解拥挤度距离衡量解在目标空间的稀疏程度保证多样性精英保留父代与子代合并后再选择2.1 算法流程简述初始化种群计算目标函数多目标非支配排序 拥挤度二元锦标赛选择交叉、变异产生子代环境选择得到新种群重复迭代得到 Pareto 前沿3. 本项目如何解决 FJSP项目实现了 NSGA-II FJSP 的完整流程关键模块如下main.py src/ algorithms/ GA.py decode.py initialization.py selection.py crossover.py mutation.py sorting.py utils/ data.py performance _test.py下面按求解流程梳理代码思路。3.1 数据读取src/utils/data.pydata.py支持两种格式*.txt优先读取*.fjs读取结果返回work记录每个工序属于哪个工件Tmachinetime每道工序的可选机器与加工时间这为后续编码、解码提供基础数据。3.2 编码设计OS/MS 双层编码项目使用经典的OS/MS 双层编码OSOperation Sequence全局工序加工顺序MSMachine Selection每道工序选择哪台机器这样可以同时表达“工序顺序”和“机器选择”两个维度适合 FJSP 的可行解表示。3.3 初始化、交叉与变异主要在src/algorithms/initialization.py、crossover.py、mutation.py中完成初始化生成随机可行的 OS/MS交叉算子例如 POX、UX变异算子改变工序顺序或机器选择这些操作负责探索更广的解空间。3.4 目标函数与解码src/algorithms/decode.py解码模块负责把 OS/MS 转换为可执行调度并计算目标函数根据工件顺序和机器资源安排开始/结束时间计算 Makespan计算 TEC加工能耗 空闲能耗可选绘制甘特图并保存结果关键输出是一个形如[C_max, TEC]的目标向量。3.5 NSGA-II 主流程src/algorithms/GA.pyGA.py是核心binary_tournament_selection二元锦标赛选择fast_non_dominated_sort非支配排序calculate_crowding_distance拥挤度距离environment_selection环境选择保留精英主循环初始化种群交叉与变异生成子代计算子代目标函数合并父代与子代进行非支配排序用拥挤度距离选择下一代最终输出Pareto 前沿解集最佳个体用于甘特图绘制3.6 主入口main.pymain.py负责串联所有模块读取数据初始化解码器与 GA设置迭代次数或 CPU 时间限制调用ga.total()得到结果输出 Pareto 前沿并绘制甘特图4. 结果与可视化项目输出主要包括甘特图展示具体调度方案Pareto 前沿图展示多目标权衡结果这些图像被保存在results/目录下适合用于论文或实验报告。5. 小结本项目的实现路径是数据读取 → OS/MS 编码 → NSGA-II 进化 → 解码与多目标计算 → 可视化输出。对入门者来说建议阅读顺序main.py了解整体流程GA.py理解 NSGA-II 主循环decode.py理解目标函数与调度解码如果想进一步提升效果可尝试引入局部搜索如 VNS自适应交叉与变异概率更真实的能耗模型