2-22车间调度不只追求“做得快”，还要兼顾延期、设备负荷和能耗：NSGA-II 多目标柔性车间调度 原创

一句话介绍： 这套程序使用 NSGA-II 同时优化车间的最大完工时间、总延期、设备总负荷和总能耗，在 8 个工件、28 道工序和 8 台设备之间自动搜索多组互不支配的调度方案，再从 Pareto 优解中选取一个方案生成最终加工调度。

先看它解决什么问题

真实车间排产通常不是只追求一个目标。

如果只追求“所有工件最快做完”，可能会：

把大量工序集中到高性能设备；

增加设备能耗；

让部分有交货期的工件延误；

造成设备负荷分配不合理。

这套程序同时考虑 4 个目标：

缩短完工时间 + 减少延期 + 降低设备负荷 + 降低能耗

整体流程可以概括成：

工件工艺与设备数据 → 生成调度种群 → 贪婪解码 → 计算 4 个目标 → 非支配排序 + 拥挤度 → 竞赛选择 → 交叉 / 变异 → Pareto 解集 → 输出调度方案

它最大的特点是：不强行把 4 个目标合成一个加权总分，而是保留多个具有不同权衡关系的优良方案。

1. 当前程序求解的是怎样的车间问题？

源码中共有：

8 个工件、28 道工序、8 台加工设备

不同工件拥有不同数量的工序，例如：

工件 1 有 3 道工序；

工件 2 有 6 道工序；

工件 3 有 4 道工序；

其余工件有 2～4 道工序。

更加关键的是：

每一道工序都不是只能放到固定机器上加工。

每道工序都有一组候选设备，而且在不同设备上的加工时间不同。

因此程序实际求解的是：

柔性作业车间调度问题 FJSP（Flexible Job Shop Scheduling Problem）

它需要同时决定：

各工件工序怎样穿插排序；

每道工序选择哪一台候选设备；

怎样在多个调度目标之间取得更好的平衡。

2. 一条调度方案是怎样编码的？

程序使用两层染色体。

工序染色体 P

P 中保存工件编号。

某个工件出现第 1 次，就表示它的第 1 道工序；出现第 2 次，就表示第 2 道工序，以此类推。

例如工件 2 一共有 6 道工序，那么编号 2 在整条染色体中会出现 6 次。

这种编码的好处是：

同一工件内部的工艺顺序天然不会被打乱。

机器染色体 M

M 与 P 一一对应，表示当前工序实际选择哪台设备加工。

所以一条完整调度染色体同时决定：

工序排序 + 机器分配

这正是柔性车间调度中最重要的两个决策。

3. 解码时怎样避免工序和机器发生冲突？

decode.m 使用的是一种带“前插”的贪婪解码方法。

对于每一道工序，程序首先考虑两个条件：

这个工件的上一道工序是否已经完成；

当前选择的机器什么时候有空。

如果机器已有加工任务，程序还会检查机器时间轴上是否存在足够长的空闲间隙。

只要某个空档：

位于该工序可以开始的时间之后；

空档长度足够完成当前加工；

程序就会把工序插入这个空闲区间，而不是机械排到机器最后。

因此当前解码方式不仅满足：

工件工艺顺序约束 + 单台机器不能同时加工两道工序

还会主动利用机器已有的空闲时间，提高调度紧凑程度。

4. 程序同时优化哪 4 个目标？

这是这份工程的核心。

目标一：最大完工时间

程序计算所有工件最后一道工序的完成时间，并取最大值：

Cmax = max(C₁, C₂, …, C₈)

Cmax 越小，说明整个车间越早完成本批工件。

这是传统车间调度中最常见的 Makespan 指标。

目标二：总延期时间

每个工件都有自己的交货期 dᵢ。

如果工件提前完成，不产生延期；如果超过交货期，就计算超出的部分：

Tᵢ = max(Cᵢ - dᵢ, 0)

总延期为：

T_total = Σᵢ Tᵢ

因此这个目标关注的不是“整个车间什么时候结束”，而是：

各个订单有没有错过自己的交货期。

这和 Cmax 是两个不同的生产管理目标。

目标三：设备总负荷

程序把所有实际加工工序的加工时间累加：

L_total = Σ ProcessingTime

因为同一道工序放到不同机器上可能需要不同加工时间，所以机器选择会直接改变这个目标。

简单来说：

尽量选择整体加工效率更高的设备组合。

目标四：总能耗

cal_ene_consu.m 将能耗拆成 4 部分：

E_total = E_processing + E_idle + E_transfer + E_workshop

其中包括：

设备实际加工产生的能耗；

加工间隙中的设备空转能耗；

工件在设备之间转移产生的能耗；

整个车间运行期间的固定能耗。

源码中 8 台设备的加工功率和空转功率并不相同，因此：

把工序换到另一台机器，不只会改变加工时间，也可能改变能耗。

这使时间目标和能源目标之间产生真实的权衡关系。

5. 为什么多目标调度不能简单找一个“最小值”？

假设有两个调度方案：

方案 A 完工更快，但能耗更高；

方案 B 能耗更低，但完工稍慢。

此时很难直接说哪一个绝对更好。

NSGA-II 使用 Pareto 支配关系解决这个问题。

如果方案 A 满足：

在所有目标上都不比 B 差，并且至少有一个目标严格优于 B，

那么就说：A 支配 B

反过来，如果：A 的时间更好；B 的能耗更好；二者就可能互不支配。

这样的方案都会被保留在 Pareto 解集中。

6. 什么是 NSGA-II 的“非支配排序”？

程序会给每一个调度方案分配等级。

Rank 1

没有任何其他方案能够支配它。

这些就是当前种群中的：

第一层 Pareto 非支配解

Rank 2

只会被 Rank 1 中的部分方案支配。

Rank 3、Rank 4……

依次继续分层。

竞赛选择时：Rank 越小，优先级越高。

所以 NSGA-II 并不是简单按照某一个目标从小到大排序，而是同时观察 4 个目标之间的支配关系。

7. 为什么还要计算拥挤距离？

如果只保留 Rank 1，很多解可能全部挤在 Pareto 前沿的一小块区域。

为了让最终方案覆盖更多不同权衡情况，程序还计算拥挤距离。

对于某个目标，可以理解成：

dᵢ ≈ (fᵢ₊₁ - fᵢ₋₁) / (fmax - fmin)

再把 4 个目标上的距离相加。

拥挤距离越大，说明：

这个方案周围比较空，它代表了 Pareto 前沿上一个相对不同的权衡区域。

因此竞赛选择遵循：

先比较 Rank → Rank 相同再选择拥挤距离更大的方案

这样既保留优良解，也维持解集多样性。

8. NSGA-II 怎样产生下一代调度方案？

当前程序使用：

竞赛选择 → 工序 / 机器交叉 → 机器变异 → 精英保留

竞赛选择

每次随机抽取两个方案。

优先选择：

非支配等级更高的；

如果等级相同，选择拥挤距离更大的。

工序交叉

程序会选出一部分工件，将这些工件对应的工序位置从一个父代保留下来，再用另一个父代补齐剩余部分。

这样既产生新的工序顺序，又不会破坏每个工件应有的工序数量。

机器交叉

部分工序会交换两个父代中对应的机器选择，使同一工序尝试不同设备组合。

机器变异

源码实际启用的变异主要针对机器染色体：

随机选择工序，并重新从该工序允许的候选机器中选择加工设备。

因此种群能够不断产生新的机器分配方案。

9. 为什么要保留精英解？

每一代生成新的子代后，主程序还会把上一轮排序靠前的：

10 个调度方案

直接加入新的种群。

这样可以避免：

已经找到的优秀 Pareto 方案因为随机交叉和变异突然全部消失。

所以整个搜索过程既会不断产生新方案，也会保留已经找到的较好解。

10. 当前车间数据为什么特别适合做多目标优化？

源码中的 8 台机器具有明显不同的加工功率与空转功率。

例如：

机器 1 加工功率为 20；机器 3 只有 6；机器 6 为 5.5；

不同机器的加工时间也各不相同。

这会出现典型冲突：

某台机器可能加工更快，但耗能更高；另一台机器能耗较低，却需要更长加工时间。

同时工件还有不同交货期。

所以一个好的调度方案必须同时考虑：

速度、交期、加工效率和能源消耗

这正是 NSGA-II 比单目标遗传算法更适合当前问题的原因。

11. 为什么不直接把 4 个目标加权相加？

最简单的多目标处理方式是：

F = w₁Cmax + w₂T + w₃L + w₄E

但问题在于：

权重 w₁～w₄ 很难提前确定；

不同目标单位不同；

换一组权重，就可能得到完全不同的方案；

一个加权值只能得到一种偏好下的结果。

NSGA-II 不需要先写死这些权重。

它先得到：

一组不同时间—延期—负荷—能耗权衡下的 Pareto 方案。

之后管理者再根据实际生产需求进行二次选择。

这更符合多目标生产调度的实际决策方式。

12. 程序最终得到的不是一个“唯一最优解”

最后一次非支配排序完成后，程序会提取：

Rank = 1的所有方案。

这就是当前计算得到的一级 Pareto 解集。

理论上应该根据实际偏好，例如：

更看重交期；更看重节能；更看重生产周期；

从 Pareto 解中再选择一个最终方案。

当前源码为了直接展示调度结果，简单取一级 Pareto 解中的第一个方案作为 best_p。

因此更准确的理解是：

NSGA-II 的主要结果是一组 Pareto 优良调度，而甘特调度只是从这组解里选出的一个代表方案。

源码注释也说明，实际还可以进一步使用 AHP、熵权法或模糊决策等方法从 Pareto 解集中选择最终方案。

13. 这种方法理论上为什么适合车间调度？

优势一：同时处理工序排序和机器分配

柔性车间不仅要决定“谁先做”，还要决定“在哪台机器做”。

程序用 P、M 两层染色体把两类决策放在同一个优化过程中，因此能够搜索完整调度方案。

优势二：非支配排序适合彼此冲突的生产目标

完工时间、延期和能耗往往不能同时达到各自单独最小值。

Pareto 思想允许这些互相冲突的方案共同存在，而不是强迫所有目标变成一个总分。

优势三：拥挤距离保持方案多样性

如果只留下非常相似的调度方案，即使它们都很优，也无法给生产管理者提供丰富选择。

拥挤距离会优先保留分布较稀疏的方案，使 Pareto 解覆盖更多不同权衡区域。

优势四：贪婪前插解码能利用机器空档

遗传算法决定“顺序和机器”，解码器再主动寻找机器空闲区间。

这比简单把所有新工序都排在机器队尾更加紧凑，可以直接改善时间利用率。

14. 程序最终能看到什么结果？

最终选定一个 Pareto 调度方案后，程序会解码得到每一道工序：

分配到哪台机器；从什么时候开始；

到什么时候结束。同时可以得到该方案的：

最大完工时间；总延期；

设备总负荷；总能耗。

因此用户看到的不只是一个抽象目标函数数值，而是一套可以直接映射到车间加工时间轴的调度计划。

15. 它适合用在哪里？

柔性制造车间排产

同一道工序可以由多台不同机器完成时，可以同时优化加工顺序和设备选择。

绿色低碳车间调度

当前模型已经把加工、空转、转移和车间固定能耗纳入目标，非常适合研究生产效率和能源消耗之间的平衡。

订单交期管理

通过总延期目标，可以避免只追求总体完工速度，却让部分订单严重超期。

NSGA-II 多目标优化教学

工程完整包含：

双层编码 → 贪婪解码 → 4 目标评价 → 快速非支配排序 → 拥挤距离 → 竞赛选择 → 交叉 / 变异 → Pareto 解集

非常适合学习 NSGA-II 怎样落地到真实调度问题。

16. 怎么运行？

主程序是：nsga2_scheduling.m

保持 data_pro.m、data_mac.m、解码函数、目标函数和遗传操作函数位于同一 MATLAB 路径后，直接运行主函数即可。

当前主程序使用：

100 个初始父代；10 代迭代；

两两竞赛选择；交叉概率 0.8；

变异概率 0.1；每代额外保留 10 个较优个体。

运行结束后会提取一级 Pareto 解，并选择其中一个方案生成最终调度结果。

17. 一句话看懂这个项目

这是一个 MATLAB NSGA-II 多目标柔性车间调度程序：它针对 8 个工件、28 道工序和 8 台可选设备，用工序染色体 P 决定加工顺序、机器染色体 M 决定设备分配，再通过带前插的贪婪解码计算实际加工时间，同时最小化最大完工时间、总延期、设备总负荷和总能耗；NSGA-II 利用快速非支配排序和拥挤距离保留一组不同权衡关系的 Pareto 调度方案，最终再从一级非支配解中选择一个方案形成具体车间排产。

18. 源程序下载

可二次开发工程包：https://mbd.pub/o/bread/mbd-Zpeckpty

百度网盘链接：

https://pan.baidu.com/s/1WiTtngY2MZbkwDuVLP7liw