欢迎访问《控制理论与应用》期刊网站！

面向分布式同构混合流水车间绿色调度的多目标优化方法

doi: 10.7641/CTA.2024.40443

颜雪松，张峻华，胡成玉

中国地质大学(武汉) 计算机学院, 湖北武汉 430074

基金项目: 国家重点研发计划项目(2022YFB4501402), 湖北省重点研发计划项目(2023BAB065), 国家自然科学基金项目(62073300)资助.

详细信息

作者简介

颜雪松博士,教授,博士生导师,研究方向为智能优化算法及应用、人工智能及其应用,E-mail: yanxs@cug.edu.cn;

张峻华硕士研究生,研究方向为智能优化算法及应用,E-mail: junhuazhang@cug.edu.cn;

胡成玉博士,教授,博士生导师,研究方向为智能优化及其应用、强化学习,E-mail: huchengyu@cug.edu.cn.

通信作者

胡成玉，E-mail: huchengyu@cug.edu.cn;Tel.:+8615927160586.

Multi-objective optimization method for distributed homogeneous hybrid flow-shop green scheduling

YAN Xue-song ， ZHANG Jun-hua ， HU Cheng-yu

School of Computer Science, China University of Geosciences (Wuhan), Wuhan Hubei 430074 , China

Funds: Supported by the National Key Research and Development Program of China (2022YFB4501402), the Key Research and Development Program of Hubei Province (2023BAB065) and the National Natural Science Foundation of China (62073300).

摘要

在双碳目标的背景下, 制造业的发展既面临挑战又面临机遇, 为响应国家政策, 大力减少碳排放量, 本文以分布式混合流水车间绿色调度问题作为研究对象, 对于具有相同加工能力的工厂车间, 本文构建了一个分布式同构混合流水车间绿色调度问题模型, 结合实际工厂特点, 给出加工期间碳排放量的计算公式. 结合问题特性提出了改进的NSGA-II算法, 设计了算法的混合初始化策略、更新策略和降碳策略以提高算法的性能, 在算法的实验验证中, 设计消融实验验证了所提策略的有效性, 并与多种先进的多目标优化算法进行对比实验, 验证了改进算法在求解该问题上的有效性.

关键词

分布式混合流水车间调度 / 双碳目标 / 多目标优化 / NSGA-II

Abstract

Under the background of the dual carbon goals, the development of the manufacturing industry faces both challenges and opportunities. In response to national policies, vigorously reducing carbon emissions, this paper focuses on the green scheduling problem of distributed hybrid flow shops. For factory workshops with the same processing capabilities, this paper constructs a green scheduling problem model for distributed homogeneous hybrid flow-shops. Combining the characteristics of actual factories, a formula for calculating carbon emissions during processing is provided. An improved NSGA-II algorithm is proposed, including a hybrid initialization strategy, an update strategy, and a carbon reduction strategy to enhance the algorithm’s performance. In the experimental validation of the algorithm, ablation studies were designed to verify the effectiveness of the proposed strategies. Additionally, comparative experiments with various advanced multiobjective optimization algorithms validate the effectiveness of the improved algorithm in solving this problem.

Keywords

distributed hybrid flow-shop scheduling / dual carbon goals / multiobjective optimization / NSGA-II

1 引言 2 问题描述与数学模型 2.1 问题描述 2.2 数学模型 2.2.1 最大完工时间计算 2.2.2 总碳排放量计算 3 改进的多目标优化方法 3.1 混合初始化策略 3.2 更新操作 3.3 降碳策略 4 实验结果与分析 4.1 实验设置 4.2 参数设置 4.3 策略有效性实验 4.4 算法对比实验 5 结论

1 引言

分布式混合流水车间调度问题，也被称作分布式柔性流水车间调度问题，其问题特性是一个阶段内具有多台机器的流水车间，一个工件可以在此阶段的任意机器上进行加工. 针对此问题，目前热门的研究方向是转化为结合无等待、模糊等特殊约束的多目标问题.

多目标的分布式混合流水车间调度问题是研究的热点，是非常复杂的组合优化问题 ^[1] . 因此，只有规模比较小的问题才能求出精确解. 所以，对该问题的求解方法几乎都是元启发式算法，元启发式可以分为基于单一解决方案的元启发式（也称为局部搜索或轨迹方法）、基于群体的元启发式和混合元启发式，混合元启发式集成了几种（元）启发式方法的概念 ^[2] . 特别是对于像多目标的分布式混合流水车间调度这样复杂的规划问题，基本的元启发式方法能被来自其他元启发式框架的元素所增强. 一个常见的例子是将基于局部搜索的改进方法集成到基于群体的元启发式方法中. 此外，一些元启发式方法，如水波纹算法（water flow-like algorithm，WFA）或人工蜂群算法（artificial bee colony，ABC），是基于种群的，但它们的基本设计已经包含了某种改进方法. 同时，多目标单解方法需要存储非支配解，这是在帕累托档案或某种种群中完成的. 这使得对混合方法的明确区分变得困难. 因此，本文需要对单解和群体进行区分.

针对多目标的绿色混合流水车间调度问题，研究人员提出了各种高效的优化程序来进行求解. 在启发式算法中，Lu等人 ^[3] 通过应用基于迭代贪心算法的过程来最小化完工时间和总能耗. Liu等人 ^[4] 提出带有偏好的自适应选择多目标优化算法，以最大完工时间最小、总能耗最小、调整时间剩余值最大为目标函数. Biel等人 ^[5] 用混合整数线性规划方法来优化能量成本和流动时间最小化的目标函数. Schulz等人 ^[6] 采用了相同的程序，尽量减少延误和能源成本. Lu等人 ^[7] 开发了灰狼优化算法来优化最小化时间跨度（makespan）、最小化总能耗（total energy consumption）和最小化噪声污染（noise pollution）3个目标函数. Zhang等人 ^[8] 提出了帝国主义竞争算法，以最小化时间跨度和总能耗为目标函数. Li等人 ^[9] 也提出了同样的算法来优化3个目标函数: 最小化时间跨度（makespan）、最小化迟到时间（tardiness）和最小化总能耗（total energy consumption）. 雷德明等人 ^[10] 基于教学–学习的新型优化算法和非支配排序遗传算法（non-dominated sorting genetic algorithm II，NSGA-II）对最小化迟到时间和总能耗进行了优化 ^[11] .

Liu等人 ^[12] 也提出了一种改进的NSGA-II，以尽量减少总能耗和碳足迹. Wang等人 ^[13] 以及Shao等人 ^[14] 也通过实施记忆算法研究了最小化延迟和最小化总能耗的目标函数. Shao等人 ^[15] 也应用了Memetic算法程序来解决3个目标函数. Geng等人 ^[16] 使用人工蜂群最小化工期和总能耗. 此外，Dong 等人 ^[17] 使用 salp swarm算法优化了3 个目标函数: 最小化时间跨度、最小化总能耗和最小化碳排放.

2 问题描述与数学模型

2.1 问题描述

分布式同构混合流水车间绿色调度问题（distributed homogeneous hybrid flow-shop green scheduling problem，DHHFSGSP）描述如下: 有n个工件需要分配给F个加工能力相同的工厂，每个工件有m道工序，每个工厂对于每道工序都有多台加工能力相同机器并行组成的混合流水车间. 所有的工厂都可以加工所有的工件，一旦工件被分配到某个工厂中，该工件的所有工序必须在指定的工厂中进行，不能转移到其他工厂. 同时，DHHFSGSP需要满足以下约束条件:

1）所有工件独立，都可以在零时刻进行加工;

2）所有工件可以在任意工厂进行加工，工件一旦被分配到某一工厂，该工件的所有加工过程必须在此工厂内完成;

3）每台机器在某一时刻只能处理一个工件，每个工件在某一时刻只能被一台机器处理;

4）工件一旦开始在指定机器上加工，则不允许被抢占和中断;

5）整个生产调度过程中的总碳排放量包含3个部分，分别为工件加工时产生的碳排放量、机器闲置时产生的碳排放量以及辅助物料（如机器的润滑剂、冷却剂）消耗产生的碳排放量;

6）机器的设置时间和工件工序之间的转移时间忽略不计，不考虑机器故障和内存不足的情况;

7）允许机器在待加工产品未达到时闲置，允许产品在工序间等待.

2.2 数学模型

本文以最小化最大完工时间和总碳排放量为优化目标，建立分布式同构混合流水车间绿色调度问题模型，模型定义过程如下，参数定义如表1所示.

1）决策变量:

x_{f, j} = \{\begin{array}{l} 1, 任务 j 被分配在工厂 f 上时, \\ 0, 其他, \end{array}

(1)

y_{f, k, j, i} = \{\begin{array}{l} 1, 工件 j 在工厂 f 里第 k 阶段的 \\ i 号机器上处理时, \\ 0, 其他, \end{array}

(2)

z_{f, k, j, j^{'}} = \{\begin{array}{l} 1, 工件 j 在工厂 f 里第 k 阶段的 i 号 \\ 机器上在工件 j^{'} 之前处理时, \\ 0, 其他. \end{array}

(3)

2）目标函数:

m i n \{C_{m a x}, C E\} .

(4)

3）约束条件:

\sum_{f = 1}^{F} x_{f, j} = 1, j \in {1,2, \dots, n},

(5)

\begin{matrix} \sum_{i = 1}^{l_{f, k}} y_{f, k, j, i} = x_{f, j}, j \in {1,2, \dots, n}, \\ f \in {1,2, \dots, F}, k \in {1,2, \dots, m}, \end{matrix}

(6)

S_{j, 1} ⩾ 0, j \in {1,2, \dots, n},

(7)

\begin{matrix} C_{j, k} = S_{j, k} + \sum_{f = 1}^{f} \sum_{i = 1}^{l_{f, k}} y_{f, k, j, i} \times p_{j, k} \\ j \in {1,2, \dots, n}, k \in {1,2, \dots, m}, \end{matrix}

(8)

S_{j, k + 1} ⩾ C_{j, k}, j \in {1, 2, \dots, n},

k \in {1,2, \dots, m}

(9)

\begin{matrix} z_{f, k, j, j^{'}} + z_{f, k, j^{'}, j} ⩽ 1, f \in {1,2, \dots, F}, \\ j, j^{'} \in {1,2, \dots, n}, k \in {1,2, \dots, m}, \end{matrix}

(10)

\begin{matrix} z_{f, k, j, j^{'}} + z_{f, k, j^{'}, j} ⩾ y_{f, k, j, i} + y_{f, k, j^{'}, i} - 1, \\ f \in {1,2, \dots, F}, j^{'} \in {j, \dots, n}, \\ k \in {1,2, \dots, m}, \end{matrix}

(11)

\begin{matrix} S_{j^{'}, k} - C_{j, k} + M \times (3 - y_{f, k, j, i} - y_{f, k, j^{'}, i} - \\ z_{f, k, j, j^{'}}) ⩾ 0, j \neq j^{'}, f \in {1,2, \dots, F}, \\ i \in \{1,2, \dots, l_{f, k}\}, k \in {1,2, \dots, m}, \end{matrix}

(12)

其中: 式（1）–（3）定义了决策变量x_f_，_j，y_f_，_k_，_j_，_i和z_f_，_k_，_j_，_j_′ 的取值范围; 式（4）为目标函数，最小化最大完工时间和总碳排放量; 式（5）确保每个工件都必须分配给一个工厂; 式（6）确保每个工件在每个阶段只能由一台机器处理; 式（7）保证了每个工件的第1阶段的开始时间不小于0; 式（8）定义每个操作的完成时间; 式（9）确保只有在前一阶段的操作完成后，才能开始作业的操作; 式（10）–（12）确保每台机器一次只能处理一项作业.

表1DHHFSGSP模型参数

Table1DHHFSGSP model parameters

2.2.1 最大完工时间计算

在DHHFSGSP问题模型中，令最后的求解序列为 Π，其表示为n个工件在f个工厂的分配结果，Π = {π¹，π²，· · ·，π^f}其中表示f工厂里工件的加工顺序. 求解整个序列的最大完工时间，只需求解每个工厂的完工时间即可，具体计算流程如下:

1）定义每个工厂的第1工件完成时间:

C_{π^{f} (1), 1} = p_{π^{f} (1), 1}, f = 1,2, \dots, F;

(13)

2）求解此机器上一工件完成时间:

C_{π^{f} (i), 1} = C_{π^{f} (i - 1), 1} + p_{π^{f} (i), 1}, f = 1,2, \dots, F;

(14)

3）求解此工件上一阶段完成时间:

C_{π^{f} (1), j} = C_{π^{f} (1), j - 1} + p_{π^{f} (1), j}, f = 1,2, \dots, F;

(15)

4）求解工件实际完成时间:

C_{π^{f} (i), j} = m a x \{C_{π^{f} (i - 1), j}, C_{π^{f} (i), j - 1}\} + p_{π^{f} (i), j},

f = 1,2, \dots, F;

(16)

5）求解所有工厂最大完成时间:

C_{m a x} (Π) = m a x (C_{n_{f}, m}) .

(17)

通过这样的步骤，可以求出针对本问题模型的最终求解序列Π的最大完成时间为C_max（Π），其为f个工厂中最后一个工件在最后一阶段的完工时间的最大值.

2.2.2 总碳排放量计算

计算碳排放量能有效的推进各项碳减排工作，是促进经济绿色转型的基本前提，是积极参与应对气候变化国际谈判的重要支撑. 碳核算可以直接量化碳排放的数据，还可以通过分析各环节碳排放的数据，找出潜在的减排环节和方式，对碳中和目标的实现、碳交易市场的运行至关重要.

目前碳排放量的计算主要有3种方式: 排放因子法、质量平衡法以及实测法. 由于实测法要求较高，并且易测出非因生产而产出的二氧化碳，故本文依据生产调度过程的碳排放来源，采用排放因子法和质量平衡法结合使用. 生产调度过程中的碳排放有4种来源，分别为工件加工时产生的碳排放、机器待机时产生的碳排放、工件在各机器之间运输时产生的碳排放以及工件在加工过程中辅助物料消耗产生的碳排放. 由于在混合流水车间调度问题中，不同的调度序列对于工件在运输期间产生的碳排放量影响不大，因此本文不考虑此项碳排放.

对于CE_run和CE_idle，采用排放因子法进行计算. 具体公式如式（18）–（19）.

\begin{matrix} {C E}_{run} = \\ \sum_{j = 1}^{n} \sum_{k = 1}^{m} \sum_{f = 1}^{F} (y_{f, k, j, i} \times p_{j, k} \times {P P}_{f, k, i}) \times ε_{elec}, \end{matrix}

(18)

工件加工时的能耗等于所有工件在机器上实际的加工时间和加工机器的额定功率的乘积，最后将能耗乘以碳排放因子就能得到最终的碳排放量.

\begin{matrix} {C E}_{i d l e} = \\ \sum_{f = 1}^{F} [C (π_{f}) - \sum_{j = 1}^{n} \sum_{k = 1}^{n} p_{i, k} \times x_{f, j}] \times S P \times ε_{e l e c} . \end{matrix}

(19)

机器待机时的能耗等于所有机器的待机时间与机器的待机的额定功率的乘积，最后将能耗乘以碳排放因子就能得到最终的待机碳排放量.

对于在加工过程的辅助物料消耗产生的碳排放量采用质量平衡法计算，在机器加工时，通常会消耗一些矿化剂、助溶剂和研磨剂. 具体公式如下，其中，

T_{i ， j}^{cool}

表示加工工件O_i_，_j的机器研磨剂更新的平均间隔时间;

{E F}_{i ， j}^{c o o l}

表示机器研磨剂的碳排放系数; p_i_，_j表示工件 i 在机器j 上的加工时间;

T_{i ， j}^{lu}

表示加工工件 O_i_，_j的机器助溶剂排出的平均间隔时间;

{L O}_{i ， j}^{l u}

表示加工工件O_i_，_j的机器初始助溶剂量;

{E F}_{i ， j}^{l u}

表示机器助溶剂的碳排放系数;

{I C}_{i ， j}^{c o o l}

表示加工工件O_i_，_j的机器初始研磨剂量，具体计算公式如式（20）所示:

\begin{matrix} {C E}_{a u} = \sum_{j = 1}^{n_{i}} (\frac{p_{i, j}}{T_{i, j}^{c o o l}} \times {I C}_{i, j}^{c o o l} \times {E F}_{i, j}^{c o o l} + \\ \frac{p_{i, j}}{T_{i, j}^{l u}} \times {L O}_{i, j}^{l u} \times {E F}_{i, j}^{l u}) = \\ \sum_{j = 1}^{n_{i}} p_{i, j} \times (\frac{{I C}_{i, j}^{c o o l} \times {E F}_{i, j}^{c o o l}}{T_{i, j}^{c o o l}} + \\ \frac{{L O}_{i, j}^{l u} \times {E F}_{i, j}^{l u}}{T_{i, j}^{l u}}) = \sum_{j = 1}^{n_{i}} p_{i, j} \times ε_{a u} . \end{matrix}

(20)

3 改进的多目标优化方法

本文提出了一种改进的NSGA-II算法来求解DHHFSGSP，该算法主要针对初始化策略进行了优化，协同使用多种交叉变异算子，并设计了用于绿色调度的降碳策略，改进的NSGA-II算法流程如图1所示.

3.1 混合初始化策略

对于元启发式算法来说，初始解的选择会对算法的性能产生重大的影响，Zhang等人 ^[18] 证明如果makespan是需要优化的目标之一，使用NEH（Nawaz，Enscore and Ham）启发式算法能获取高质量的初始解. 对于基于种群的元启发式算法来说，除了追求解的高质量，确保种群的多样性也是十分的重要. 一般来说，很难找到满足双目标（即最大完工时间和总碳排放量）的最优解. 所以使用多种初始化策略协同使用，以保证解的多样性.

混合初始化策略的执行过程是初始解1使用NEH 生成，生成一个最小最大完成时间的初始解; 初始解2 使用降低总能耗（reduce total energy consumption，ReduceTEC）^[3] 策略生成，生成一个最小碳排放的初始解. 其余初始解使用随机法生成，直到完成种群的生成为止. 通过这样一个混合初始化生成策略，能同时保证初始种群的高质量性和多样性. 该策略的执行步骤如下:

NEH算法:

步骤 1 计算所有的工件的总加工时间，按照总加工时间进行非增顺序排序各个工件，得到初始的工件加工序列;

步骤 2 取出初始加工序列的前两个工件，将其排列可得到两个序列，评价两个序列，将其中最大完成时间最小的序列当作当前调度;

步骤 3 从初始序列继续取出工件，将其插入当前调度里所有可能的位置，然后评价所得到的序列，将其中最大完成时间最小的序列当作当前调度. 直到初始序列里的所有工件被选择.

图1改进的NSGA-II算法流程图

Fig.1Flowchart of improved NSGA-II algorithm

ReduceTEC策略，其步骤如下:

步骤 1 将每个工件按照其加工的额定功率进行从大到小排序，就可以得到初始工件序列;

步骤 2 按照排序顺序，将各个工件尝试插入到所有可能的位置，并计算各个位置的碳排放量;

步骤 3 选择其中碳排放量最小的位置作为工件最终分配位置，直到所有工件分配完毕.

3.2 更新操作

在大多数元启发式框架中，一般使用各种算子来生成新的解，并在解空间里进行搜索，一般在基于种群的元启发式算法中，会选择两个解进行重组，也就是选择交叉变异操作.

针对本问题模型，所用的选择算子为锦标赛选择算子. 锦标赛选择算子相对于轮盘赌选择策略来说，是一个确定的选择方式，能更好的保持解的多样性; 当问题的Pareto前沿分布较为均匀时，二元锦标赛可以有效地选择个体，不会受到适应度值范围的影响.

而在选择交叉，变异算子时，只选择一组交叉变异算子时，种群的多样性显得十分有限，而选择多种交叉变异算子一起使用的话，会导致解的空间过于庞大，从而影响获取解的时间. 因为并不是所有算子在每个进化过程中都是有效的，因此，本文设计了一种交叉变异算子的选择策略，当使用该组合的算子生成的解能支配之前的解时，它就能获得奖励，随着进化过程的进行，能生成更优秀的解的组合能被更多地选择. 本文选择的交叉算子有部分映射交叉算子（partial mapped cossover，PMX）、循环交叉算子（cycle crossover，CX）、基于位置的交叉算子（position-based crossover，PBX）和基于顺序的交叉算子（order-based crossover，OBX）; 变异算子有交换算子和插入算子.

上述4种交叉算子和2种变异算子，一共能组成8种组合方式，每种组合方式被选择的初始概率为1/8，采用轮盘赌策略进行算子选择，若通过算子产生的子代能不被原解支配，则该算子组合的选择概率将会获得一个奖励，具体算法流程如表2所示.

3.3 降碳策略

在本文的问题模型中，最主要的碳排放量是由机器加工所产生的碳排放，机器空闲产生的碳排放以及辅助物料产生的碳排放. 由于各个工件在机器加工时产生的碳排放和辅助物料产生的碳排放在每个工厂都相同，所以本文选择的降碳策略主要是针对机器空闲产生的碳排放.

对于一个完整的调度，可以观察到能够通过延迟某些操作的进程而不影响makespan来减少空闲时间. 由图2可以看出，其中阴影部分是通过右移策略所节约的等待时间，修改后的计划比原始计划的总空闲时间更短，从而，能在不影响最大完成时间的前提下减少碳排放量.

4 实验结果与分析

4.1 实验设置

为了验证改进的NSGA-II算法在求解分布式同构混合流水车间绿色调度问题的有效性，本文设计了相应的对比实验，实验运行在Microsoft Windows 10下的Intel core i5-10500 CPU@3.10 GHz /16 GB RAM的 PC上.

表2更新算法伪代码

Table2Pseudocode of the update algorithm

图2工序右移策略示例图

Fig.2Example diagram of procedure right shift strategy

同时，由于本文研究的分布式同构混合流水车间绿色调度问题暂时没有标准的测试数据集，因此本文根据问题性质和主要参数，构建了一组测试数据集. 其中工厂的数量F = {2，3，4，5}，工件数量n = {30，60，90}，阶段数量m = {2，3，5}，每阶段的机器数量k = {1，2，3}. 其中每个（F，n，m）生成 10个实例，共 360个实例，对于每阶段的机器数量在k中随机选择，每个工件的每个阶段的标准处理时间p_i_，_j从[30，60]中离散均匀选择，每个工件的每个阶段的标准加工功率从^[10，20]中离散均匀选择，并设定每台机器的空闲功率为SP = 2. 根据《企业温室气体排放核酸方法与报告指南–发电设施（2022年修订版）》，本文设置电能碳排放系数. 此外，机器加工时消耗辅助物料的能力与机器类型相关，所以每台机器的电能碳排放系数 ε_elec = 0.581 kgCO₂/kWh. 物料碳排放系数 ε_au 从[0.05，0.1]（kgCO₂/s）中均匀采样.

为了对所提算法的性能和对解的多样性和收敛性进行评估，选取了3个评估多目标算法性能的指标，分别是广泛性（spread，SP）（该指标用来评估算法计算得出的Pareto解集在目标空间中分布的广泛程度）、超体积（hypervolume，HV）（该指标用于度量一个目标空间的体积，该目标空间至少被非占优解集中的一个解占优）、反向世代距离（inversed generation distance，IGD）（该指标计算每个参考点到最近解的距离的平均值，反映算法的综合性能，值越小，说明算法综合性能越好）.

4.2 参数设置

在本算法当中包含了3个超参数需要设置: 1）种群大小（population size，PS）; 2）交叉概率 p_c（probability of crossover）; 3）变异概率p_m（probability of mutation）. 由于这3个参数过高或过低都会对算法性能产生影响，为了找到一个合适的取值组合，使算法性能最高，本文采取田口实验设计方法对每个参数设计了4个等级的数值，如表3所示， PS = {50，100，200，300}，p_c = {0.6，0.7，0.8，0.9}，p_m = {0.1，0.2，0.3，0.4}，由此得到的正交数组L₁₆（4³）被用于参数校准实验中. 此处使用指标IGD来衡量算法性能，对于每个实例中的每组参数组合分别执行10次算法.

表3参数等级对应表

Table3Corresponding table of parameter levels

表4中给出了指标值和参数的显著性等级，其中 delta值表示最大指标值与最小指标值之间的差值，delta值越大，表明相应的参数越重要. 图3给出3个参数在不同参数等级下的性能指标图.

从表4可以看出，种群规模PS的delta是最大的，所以它对算法的影响是最大的; 其次，是变异概率p_m; 最后，是交叉概率p_c. 然后根据图3可以得出，对这3个参数的最佳选择为PS= 100，p_c = 0.9，p_m = 0.1.

表4各参数的平均指标值

Table4Average index value of each parameter

图3不同参数等级下参数性能指标比较图

Fig.3Comparison of parameter performance indicators at different parameter levels

4.3 策略有效性实验

为了验证本文所提出的策略的有效性，针对不同的策略分别进行消融实验.

1）初始化策略: 本文将使用了协同初始化策略的本算法与只使用随机生成策略的本算法进行对比实验;

2）交叉变异策略: 本文将本算法与只使用部分映射交叉算子（PMX）和交换变异算子的本算法进行对比实验;

3）局部搜索策略: 本文将本算法与不使用局部搜索策略的本算法进行实验;

4）降碳策略: 本文将本算法在使用与不使用降碳策略进行对比实验.

通过上述所设计的4种对比实验，分别验证各策略的有效性. 每个算法在每个实例上运行10次，每个算法都采取相同的结束标准即最大运行代数到 10 000代. 采用上述所选的3个指标SP，HV和IGD值对算法的性能进行评估，运行结果如图4–6所示.

如图4所示，在所有的数据集上，使用全策略的算法的指标值SP是明显优于无初始化策略和无更新策略的，表明了本文提出的初始化策略和更新策略对提高解的多样性是十分有帮助的; 只使用初始化策略和只使用更新策略的算法的性能近似，说明其对算法性能的提升能力相近，但是使用更新策略的算法的指标值分布更加集中，说明了更新策略在各个规模上的提升比较稳定.

图4策略有效性实验的SP值对比图

Fig.4Comparison of SP values of strategy effectiveness experiment

图5策略有效性实验的HV值对比图

Fig.5Comparison of HV values of strategy effectiveness experiment

图6策略有效性实验的IGD值对比图

Fig.6Comparison of IGD values of strategy effectiveness experiment

如图5–6所示，在所有的数据集上，使用全策略的算法的指标值HV和IGD明显优于没有使用策略的两种算法，表明了本文提出的初始化策略和更新策略对算法的收敛性和多样性有很好的提升，而只使用初始化策略比只使用更新策略的算法的性能好，说明了初始化策略对算法有更好的提升.

本文还对比了不同规模数据集上的Pareto前沿图，结果如图7–9所示. 根据前沿图可知，在使用了全策略的算法之后，所求的Pareto前沿图，大多都能支配只使用部分策略的算法，这表明了本文所提出的更新策略和初始化策略都能很好的提高算法的求解性能. 同时，通过前沿图的形状可以得出，使用全策略的算法所求出的前沿图分布更加均匀，算法更加稳定，未出现较为异常的点.

图7F = 2，M = 5，J = 60 Pareto前沿图

Fig.7Pareto front diagram when F = 2, M = 5, J = 60

图8F = 3，M = 3，J = 60 Pareto前沿图

Fig.8Pareto front diagram when F = 2, M = 5, J = 60

为了验证降碳策略的有效性，本文将使用降碳策略的算法与没有使用降碳策略的算法（记为 non-carbon）进行对比实验. 每个算法在每个实例中独立运行10次，算法都采用相同的终止标准（最大函数评估次数设为25 000次）. 统计两种算法的总碳排放结果数据，并按照不同的工厂数量，分别求出各类工厂的平均碳排放量. 图10为两种算法在不同工厂数量下的平均碳排放量值. 从图10中可以明显看出，无论工厂数量有多少，使用了降碳策略的算法的平均碳排放量值均低于没有使用降碳策略的算法，说明所提出的降碳策略能有效降低分布式同构流水车间调度问题的碳排放量.

4.4 算法对比实验

为了验证本文算法的有效性，与多种经典的多目标优化算法进行了对比实验. 本文选取了融合了强化学习思想在混合流水车间调度问题上具有优秀性能的协同模因算法（cooperative memetic algorithm，CMA）^[13]，在求解大规模全局优化问题上有很好性能的多种群人工蜂群（multi-population ABC，MPABC）算法 ^[19] 和给予分解的并带有多领域局部搜索策略的基于局部搜索的多目标进化算法（multi-objective evolutionary algorithm based on local search，MOEA-LS）^[20] 进行比较. 所选的对比算法所涉及的思想都有不同，且各自都在其领域具有优秀的性能，全局的比较更能说明对比结果具有普遍性.

图9F = 5，M = 5，J = 60 Pareto前沿图

Fig.9Pareto front diagram when F = 2, M = 5, J = 60

图10不同工厂数量下平均碳排放量对比图

Fig.10Comparison of average carbon emissions under different number of factories

实验均在生成的实例数据集上进行，算法的参数选取参数实验所求出最优秀的组合PS = 100，p_c = 0.9，p_m = 0.1，终止条件设置为最大代数为10 000代. 由于DHHFSGSP属于新问题，没有标准参考前沿，本文将4个算法分别运行10次，将所求的所有解集合在一起并进行非支配排序，将排序后的结果作为该数据集的近似前沿. 每个算法在每个数据集上独立运行 10次，结果取10次的平均值，通过对比SP，HV，IGD这3个指标，验证本文的算法在本问题上的有效性，表5–7分别列出了4种算法的SP，HV，IGD指标值.

表5平均SP值对比

Table5Comparison of average SP values

从表5中可以看出，在36种（F，m，n）组合中，改进的NSGA-II得到34个最优SP值，CMA得到1个最优SP 值，MPABC得到1个最优 SP值，MOEA-LS 没有得到最优SP值，可以得出改进的NSGA-II在各种规模上的解的多样性是优于对比算法的.

从表6中可以看出，在36种（F，m，n）组合中，改进的NSGA-II得到29个最优IGD 值，CMA 得到4个最优 IGD值，MPABC得到2个最优IGD值，MOEA-LS得到 1个最优IGD值，可以得出改进的NSGA-II在各种规模上的解的收敛性是优于这几个热门算法的.

表6平均IGD值对比

Table6Comparison of average IGD values

在表7的36个平均HV值中，改进的NSGA-II有36 个最小值，CMA，MPABC，MOEA-LS都没有最优值. 显然改进的 NSGA-II拥有更多的平均 HV最优值; 对于整体的平均 HV值，改进的 NSGA-II的平均值（0.317 298）大于其他3种算法. 因此，改进的NSGA-II在求解DHHFSGSP问题上的综合性能要优于其他3种算法，并且在大规模的数据集上，改进的NSGA-II拥有很大的优势.

表7平均HV值对比

Table7Comparison of average HV values

5 结论

分布式混合流水车间调度在车间调度问题里属于比较热门的一个方向，因为其能很好的适应现实生产环境，例如，纺织、化工、造纸和钢铁行业，本质上，它是关于在几个生产阶段处理一组作业，所有作业都具有相同的机器顺序. 在至少一个阶段中，有几台机器可用，因此必须做出两个决策. 一方面，必须在每个阶段将订单分配给机器; 另一方面，分配给机器的订单必须按顺序排列. 目前，分布式流水车间调度问题的研究已经十分广泛，涉及多种特殊约束条件. 本文提出了一种改进的NSGA-II算法求解分布式同构混合流水车间绿色调度问题. 首先，根据问题特点构建相应的数学模型，以最小化最大完成时间和最小化总碳排放量为优化目标，给出相应的适应度计算函数. 设计了协同初始化策略，保证初始解的高质量性和多样性; 同时，为了增强算法的全局搜索能力，设计了多种交叉变异组合算子，使用概率矩阵进行选择，在高效求解的情况下能同时避免解空间过大. 为了减少碳排放，提出了右移策略; 最后，根据问题模型的特点，通过田口实验设计方式对算法的主要参数进行标定，构建各种对照组以验证策略的有效性; 同时，与多种先进的算法进行对比实验，来验证算法在该问题模型上的优越性.

图1改进的NSGA-II算法流程图

Fig.1Flowchart of improved NSGA-II algorithm

下载: 全尺寸图片

图2工序右移策略示例图

Fig.2Example diagram of procedure right shift strategy

下载: 全尺寸图片

图3不同参数等级下参数性能指标比较图

Fig.3Comparison of parameter performance indicators at different parameter levels

下载: 全尺寸图片

图4策略有效性实验的SP值对比图

Fig.4Comparison of SP values of strategy effectiveness experiment

下载: 全尺寸图片

图5策略有效性实验的HV值对比图

Fig.5Comparison of HV values of strategy effectiveness experiment

下载: 全尺寸图片

图6策略有效性实验的IGD值对比图

Fig.6Comparison of IGD values of strategy effectiveness experiment

下载: 全尺寸图片

图7F = 2，M = 5，J = 60 Pareto前沿图

Fig.7Pareto front diagram when F = 2, M = 5, J = 60

下载: 全尺寸图片

图8F = 3，M = 3，J = 60 Pareto前沿图

Fig.8Pareto front diagram when F = 2, M = 5, J = 60

下载: 全尺寸图片

图9F = 5，M = 5，J = 60 Pareto前沿图

Fig.9Pareto front diagram when F = 2, M = 5, J = 60

下载: 全尺寸图片

图10不同工厂数量下平均碳排放量对比图

Fig.10Comparison of average carbon emissions under different number of factories

下载: 全尺寸图片

表1DHHFSGSP模型参数

Table1DHHFSGSP model parameters

下载: 全尺寸图片

表2更新算法伪代码

Table2Pseudocode of the update algorithm

下载: 全尺寸图片

表3参数等级对应表

Table3Corresponding table of parameter levels

下载: 全尺寸图片

表4各参数的平均指标值

Table4Average index value of each parameter

下载: 全尺寸图片

表5平均SP值对比

Table5Comparison of average SP values

下载: 全尺寸图片

表6平均IGD值对比

Table6Comparison of average IGD values

下载: 全尺寸图片

表7平均HV值对比

Table7Comparison of average HV values

下载: 全尺寸图片

图1改进的NSGA-II算法流程图

Fig.1Flowchart of improved NSGA-II algorithm

图2工序右移策略示例图

Fig.2Example diagram of procedure right shift strategy

图3不同参数等级下参数性能指标比较图

Fig.3Comparison of parameter performance indicators at different parameter levels

图4策略有效性实验的SP值对比图

Fig.4Comparison of SP values of strategy effectiveness experiment

图5策略有效性实验的HV值对比图

Fig.5Comparison of HV values of strategy effectiveness experiment

图6策略有效性实验的IGD值对比图

Fig.6Comparison of IGD values of strategy effectiveness experiment

图7F = 2，M = 5，J = 60 Pareto前沿图

Fig.7Pareto front diagram when F = 2, M = 5, J = 60

图8F = 3，M = 3，J = 60 Pareto前沿图

Fig.8Pareto front diagram when F = 2, M = 5, J = 60

图9F = 5，M = 5，J = 60 Pareto前沿图

Fig.9Pareto front diagram when F = 2, M = 5, J = 60

图10不同工厂数量下平均碳排放量对比图

Fig.10Comparison of average carbon emissions under different number of factories

表1DHHFSGSP模型参数

Table1DHHFSGSP model parameters

表2更新算法伪代码

Table2Pseudocode of the update algorithm

表3参数等级对应表

Table3Corresponding table of parameter levels

表4各参数的平均指标值

Table4Average index value of each parameter

表5平均SP值对比

Table5Comparison of average SP values

表6平均IGD值对比

Table6Comparison of average IGD values

表7平均HV值对比

Table7Comparison of average HV values

图1改进的NSGA-II算法流程图

Fig.1Flowchart of improved NSGA-II algorithm

图2工序右移策略示例图

Fig.2Example diagram of procedure right shift strategy

图3不同参数等级下参数性能指标比较图

Fig.3Comparison of parameter performance indicators at different parameter levels

图4策略有效性实验的SP值对比图

Fig.4Comparison of SP values of strategy effectiveness experiment

图5策略有效性实验的HV值对比图

Fig.5Comparison of HV values of strategy effectiveness experiment

图6策略有效性实验的IGD值对比图

Fig.6Comparison of IGD values of strategy effectiveness experiment

图7F = 2，M = 5，J = 60 Pareto前沿图

Fig.7Pareto front diagram when F = 2, M = 5, J = 60

图8F = 3，M = 3，J = 60 Pareto前沿图

Fig.8Pareto front diagram when F = 2, M = 5, J = 60

图9F = 5，M = 5，J = 60 Pareto前沿图

Fig.9Pareto front diagram when F = 2, M = 5, J = 60

图10不同工厂数量下平均碳排放量对比图

Fig.10Comparison of average carbon emissions under different number of factories

表1DHHFSGSP模型参数

Table1DHHFSGSP model parameters

表2更新算法伪代码

Table2Pseudocode of the update algorithm

表3参数等级对应表

Table3Corresponding table of parameter levels

表4各参数的平均指标值

Table4Average index value of each parameter

表5平均SP值对比

Table5Comparison of average SP values

表6平均IGD值对比

Table6Comparison of average IGD values

表7平均HV值对比

Table7Comparison of average HV values

FERNANDEZ-VIAGAS V, PEREZ-GONZALEZ P, FRAMINAN J M. Efficiency of the solution representations for the hybrid flow shop scheduling problem with makespan objective. Computers & Operations Research,2019,109:77-88.

LIU Z, WANG J, ZHANG C,et al. A hybrid genetic-particle swarm algorithm based on multilevel neighbourhood structure for flexible job shop scheduling problem. Computers & Operations Research,2021,135:105431.

LU C, LIU Q, ZHANG B,et al. A Pareto-based hybrid iterated greedy algorithm for energy-efficient scheduling of distributed hybrid flowshop. Expert Systems with Applications,2022,204:117555.

LIU Z, YAN J, CHENG Q,et al. Adaptive selection multi-objective optimization method for hybrid flow shop green scheduling under finite variable parameter constraints: Case study. International Journal of Production Research,2022,60(12):3844-3862.

BIEL K, ZHAO F, SUTHERLAND J W,et al. Flow shop scheduling with grid-integrated onsite wind power using stochastic milp. International Journal of Production Research,2018,56(5):2076-2098.

SCHULZ S, BUSCHER U, SHEN L. Multi-objective hybrid flow shop scheduling with variable discrete production speed levels and time-of-use energy prices. Journal of Business Economics,2020,90:1315-1343.

LU C, GAO L, PAN Q,et al. A multi-objective cellular grey wolf optimizer for hybrid flowshop scheduling problem considering noise pollution. Applied Soft Computing,2019,75:728-749.

ZHANG B, PAN Q K, GAO L,et al. A multiobjective evolutionary algorithm based on decomposition for hybrid flowshop green scheduling problem. Computers & Industrial Engineering,2019,136:325-344.

LI M, LEI D, CAI J. Two-level imperialist competitive algorithm for energy-efficient hybrid flow shop scheduling problem with relative importance of objectives. Swarm & Evolutionary Computation,2019,49:34-43.

LEI Deming. Low carbon flexible job shop scheduling based on new teaching-learning-based optimization algorithm. Control & Decision,2017,32(9):1621-1627.(雷德明. 基于新型教学优化算法的低碳柔性作业车间调度. 控制与决策,2017,32(9):1621-1627.)

NASIRI M M, ABDOLLAHI M, RAHBARI A,et al. Minimizing the energy consumption and the total weighted tardiness for the flexible flowshop using NSGA-II and NRGA. Journal of Industrial and Systems Engineering,2018,11:150-162.

LIU C H, HUANG D H. Reduction of power consumption and carbon footprints by applying multi-objective optimisation via genetic algorithms. International Journal of Production Research,2014,52(2):337-352.

WANG J J, WANG L. A cooperative memetic algorithm with feedback for the energy-aware distributed flow-shops with flexible assembly scheduling. Computers & Industrial Engineering,2022,168:108126.

SHAO W, SHAO Z, PI D. A multi-neighborhood-based multiobjective memetic algorithm for the energy-efficient distributed flexible flow shop scheduling problem. Neural Computing & Applications,2022,34(24):22303-22330.

SHAO W, SHAO Z, PI D. A network memetic algorithm for energy and labor-aware distributed heterogeneous hybrid flow shop scheduling problem. Swarm & Evolutionary Computation,2022,75:101190.

GENG K, LIU L, WU Z. Energy-efficient distributed heterogeneous re-entrant hybrid flow shop scheduling problem with sequence dependent setup times considering factory eligibility constraints. Scientific Reports,2022,12(1):18741.

DONG J, YE C. Green scheduling of distributed two-stage reentrant hybrid flow shop considering distributed energy resources and energy storage system. Computers & Industrial Engineering,2022,169:108146.

ZHANG B, PAN Q K, MENG L L,et al. An automatic multiobjective evolutionary algorithm for the hybrid flowshop scheduling problem with consistent sublots. Knowledge-Based Systems,2022,238:107819.

WANG H, WANG W, CUI Z. A new artificial bee colony algorithm for solving large-scale optimization problems. Algorithms and Architectures for Parallel Processing: The 18th International Conference. Guangzhou, China: Springer,2018:329-337.

SHAO W, SHAO Z, PI D. Multi-objective evolutionary algorithm based on multiple neighborhoods local search for multi-objective distributed hybrid flow shop scheduling problem. Expert Systems with Applications,2021,183:115453.