多目标混合流水车间调度问题求解算法

王静云，王雷，蔡劲草，李佳路，苏学满; WANG Jingyun; WANG Lei; CAI Jincao; LI Jialu; SU Xueman

2025年4月4日 13:15 星期五

网刊加载中。。。

使用Chrome浏览器效果最佳，继续浏览，你可能不会看到最佳的展示效果，

确定继续浏览么?

复制成功，请在其他浏览器进行阅读

多目标混合流水车间调度问题求解算法 PDF

- ORCID：
王静云 ¹
- ORCID：
王雷 ¹
✉
- ORCID：
蔡劲草 ¹
- ORCID：
李佳路 ¹
- ORCID：
苏学满 ²

1. 安徽工程大学机械工程学院，芜湖241000； 2. 安徽工程大学人工智能学院，芜湖 241000

中图分类号： TP18

最近更新：2023-06-30

DOI：10.16356/j.1005-2615.2023.03.020

摘要

针对多目标不相关并行机混合流水车间调度问题，建立以最小化最大完工时间、机器总能耗和机器加工成本为目标的多目标数学模型。提出一种改进的基于分解的多目标进化算法（Improved multi‑objective evolution algorithm based on decomposition，IMOEAD），采用均匀设计表生成初始权重向量，提高种群多样性，利用正态分布交叉并设计了自适应高斯变异来提高算法的全局搜索能力和局部搜索能力，在权重向量邻域中选择个体产生新解，运用非支配等级和拥挤距离更新外部档案。以反世代距离、世代距离和非支配解个数为性能指标，通过大量案例仿真，与非支配排序遗传算法Ⅱ和基于分解的多目标进化算法进行对比，结果验证了该算法的有效性。

关键词

流水车间调度; 改进的基于分解的多目标进化算法; 正态分布交叉; 自适应高斯变异

混合流水车间调度问题（Hybrid flow shop scheduling problem， HFSP）是车间调度中常见的调度类型，是传统的流水线生产与并行机调度的综合，目前广泛存在于化工、冶金、纺织、机械、装配和运输等行业中^［

1］。近年来，越来越多的智能优化算法应用于HFSP，张源等^{［参考文献 2

百度学术}2］在传统的差分算法上结合了反向学习策略生成初始种群，添加自适应差分因子，并在个体选择时引入Metropolis准则。Zhou等^{［参考文献 3

百度学术}3］运用带分布估计的混合差分进化算法，求解了一种可重入混合流水车间调度问题。Ghaleb和Alharkan^{［参考文献 4

百度学术}4］研究了无等待的两阶段问题，采用粒子群优化算法（Particle swarm optimization，PSO）算法优化了总延迟时间。Meng等^{［参考文献 5

百度学术}5］针对不相关并行机的节能混合流水车间调度问题，提出了改进的遗传算法，通过对比模拟退火算法和迁徙鸟类优化算法，证明其改进遗传算法的有效性。罗函明等^{［参考文献 6

百度学术}6］针对布谷鸟算法常规解码方法难以获得最优解的缺点，提出一种改进的解码方法，通过对比原始规则解码、随机规则解码、改进规则解码所得结果，验证其有效性。杜利珍等^{［参考文献 7

百度学术}7］提出了基于权重的编码方式的果蝇优化算法，来求解混合流水车间调度问题。并通过与经典算法进行对比，验证了其算法的有效性。宋存利^{［参考文献 8

百度学术}8］采用正序解码和逆序解码，提出贪婪交叉算子变异算子，增加了种群的多样性，提高了遗传算法在求解HFSP时的局部搜索能力。

实际生产制造时，制造企业需要考虑的目标指数不止一个，众多学者开始对多目标的混合流水车间调度研究逐渐加深。Mousavi等^［

9］提出了一种基于遗传算法的近似求解方法，求解最大完成时间和总拖延时间最小化的双目标问题。雷德明等^{［参考文献 10

百度学术}10］针对具有总能耗和总延迟时间的低碳HFSP，提出一种合理利用算法搜索过程优化数据的有效策略，进而提出一种新型混合蛙跳算法（Shuffled frog leaping algorithm，SFLA）。在考虑序列设置时间和工序跳跃约束情况下的混合流水车间调度后，黄辉等^{［参考文献 11

百度学术}11］运用改进的非支配排序遗传算法Ⅱ（Non‑dominated sorting genetic algorithm Ⅱ，NSGA‑Ⅱ）求解了以最大完工时间和机器负荷均衡指标的双目标混合流水车间调度问题。Karimi等^{［参考文献 12

百度学术}12］运用改进的典型关联分析（Canonical correlation analysis，CCA）研究了混合流水车间调度问题，解决了钢铁厂释放时间的实际调度问题。Long等^{［参考文献 13

百度学术}13］在NSGA‑Ⅱ的基础上，提出了一种高效的启发式解码和非支配解的构造方法。Dai等^{［参考文献 14

百度学术}14］提出了一种改进的遗传模拟退火算法，求解以完工时间和总能耗为目标的带有不相关并行机的HFSP。

综上研究，针对混合流水车间调度的研究多以效率指标为目标，例如最大完工时间、提前期/拖后期和加工成本等。随着绿色制造的出现，考虑减少能耗的HFSP已被越来越多的企业所重视，而针对以机器能耗为目标的、带有不相关并行机的混合流水车间调度问题的研究较少。本文在考虑最大完工时间、机器总能耗和机器加工成本的基础上，建立多目标带有不相关并行机的HFSP数学模型，提出一种改进的基于分解的多目标进化算法（Improved multi‑objective evolution algorithm based on decomposition，IMOEAD），融合多种策略以提高算法性能。通过实例测试和分析，验证了该算法的有效性。

1 问题描述与建模

带有不相关并行机HFSP可以描述为：N个工件经过S个加工阶段进行加工，所有工件有着相同的加工路径，存在一道或多道加工阶段包含多台不相关并行机，不同并行机的处理性能也不相同。本文以最大完工时间、机器总能耗和机器加工成本为优化目标，确定每一个工件在哪一台机器上加工，对每一台机器的待加工工件进行排序，使得这3个目标值达到最优。

另外，还有如下约束：

（1）生产环境具有稳定性，不考虑工件恶化效应，以及机器故障的情况。

（2）不考虑工件之间的运输时间和准备时间。

（3）两个连续的加工工序有无限的缓冲储存区。

（4）机器设备从零时刻开始加工，同时设备保持空闲状态。

（5）不同工件不存在优先级差别，且相互独立。

根据上述分析，建立的数学模型如式（1~5）所示。

f_{1} = m i n \{m a x \{C_{1}, C_{2}, \dots, C_{N}\}\}

（1）

式中：C_i为工件i的完工时间；N为工件的个数。

f_{2}^{1} = \sum_{i = 1}^{N} \sum_{j = 1}^{S} \sum_{k = 1}^{M_{j}} P_{j k} T_{i j k} X_{i j k}

（2）

式中：S为加工阶段数；M_j $(j \in \{1,2, \dots, S\})$ 为加工阶段j的机器数量，为整数；P_jk $(k \in \{1,2, \dots, M_{j}\})$ 为加工阶段j的第k台机器的单位时间加工功率；T_ijk $(i \in \{1,2, \dots, N\})$ 为工件i在加工阶段j的第k台机器上加工时间；X_ijk为决策变量，当工件i在加工阶段j的第k台机器上加工时其值为1，否则为0。

f_{2}^{2} = \sum_{j = 1}^{S} \sum_{k = 1}^{M_{j}} (E_{j k} - B_{j k} - \sum_{i = 1}^{N} X_{i j k} T_{i j k}) \times P K_{j k}

（3）

式中：E_jk为加工阶段j的第k台机器的停工时间；B_jk为加工阶段j的第k台机器的开工时间；PK_jk为加工阶段j的第k台机器的单位时间空载功率。

f_{2} = f_{2}^{1} + f_{2}^{2}

（4）

f_{3} = \sum_{i = 1}^{N} \sum_{j = 1}^{S} \sum_{k = 1}^{M_{j}} T_{i j k} X_{i j k} O_{j k}

（5）

式中O_jk为加工阶段j的第k台机器的单位时间加工成本。

约束条件如式（6~10）所示。

E_{i j k} \leq B_{i (j + 1) k_{2}}

（6）

式中：E_ijk为工件i在加工阶段j的第k台机器完成加工的时间； $B_{i (j + 1) k_{2}}$ $(k_{2} \in \{1,2, \dots, M_{j + 1}\})$ 为工件i在加工阶段j+1的第k₂台机器开始加工的时间。

E_{i j k} = T_{i j k} + B_{i j k}

（7）

C_{i} > 0

（8）

\sum_{j = 1}^{S} M_{j} > S

（9）

\sum_{k = 1}^{M_{j}} X_{i j k} = 1

（10）

式（1）表示目标函数最大完工时间，式（2）表示所有机器加工时的能耗，式（3）表示所有机器空载时的能耗，式（4）表示所有机器的能耗总和，式（5）表示所有机器加工成本，式（6）表示工件在完成前一道工序才能开始下一道工序，式（7）表示在同一道工序工件的加工完工时间的计算公式，式（8）表示所有工件的完工时间均大于0，式（9）表示至少有一道工序有多台并行机，式（10）表示限定工件i在加工阶段j只能在该阶段的其中一台机器上加工。

2 IMOEAD算法

基于分解的多目标进化算法（Multi‑objective evolution algorithm based on decomposition，MOEA/D）利用权重向量将多目标问题（Multi‑objective problem， MOP）分解成若干个单目标的子问题，再对分解的子问题进行优化，接着计算各权重向量间的欧式距离，并根据欧式距离划分每个子问题的邻域，每个子问题都利用邻域的其他个体信息完成迭代进化。由于每个子问题利用邻域的信息迭代优化，使得MOEA/D算法在每一代的计算复杂度上要低于传统的多目标优化算法。

针对传统的MOEA/D在生成权重向量的个数不灵活、分布不均匀，本文引用均匀设计表生成权重向量。本文应用正态分布交叉和自适应高斯变异，分别加强了算法全局搜索能力和跳出局部最优能力，运用非支配等级和拥挤距离更新外部档案。IMOEAD流程图如图1所示。

图1 IMOEAD流程图

Fig.1 Flowchart of IMOEAD

2.1　编码与解码

本文采用的是矩阵编码，这种编码能很好地解决工序之间的约束，使得染色体与可行调度一一对应。N×S的矩阵中元素表示工件在某阶段，某台机器上的加工顺序。矩阵元素a_ij是在区间（1，M_j+1）上的一个实数，其中整数部分表示工件i在工序j的加工机器序号，小数部分表示工件机器的加工顺序，当整数部分相同时，根据小数部分的大小来加工，数值大先加工。解码采用置换解码，即每阶段按照生成的编码序列在相应的机器上进行加工。例如对于3个工件，每个工件有2道工序，每道工序的并行机器数量为2的混合流水车间，按照如上编码，产生如下的编码矩阵

[\begin{matrix} \begin{matrix} 1.9 & 2.8 \end{matrix} \\ \begin{matrix} 2.1 & 2.2 \end{matrix} \\ \begin{matrix} 1.6 & 1.5 \end{matrix} \end{matrix}]

可得：第1列1.9、1.6表示1和工件3在第1道工序的第1台并行机上进行加工， $1.9 > 1.6$ ，工件1优先在此机器上加工，第1列2.1表示工件2在第1道工序的第2台并行机上进行加工，第2列同理。编码矩阵对应的调度甘特图如图2所示。

图2 编码调度甘特图

Fig.2 Scheduling Gantt chart corresponding to coding

2.2　生成权重向量

针对原始的MOEA/D算法运用单纯形法生成权重向量受限于用户自定义参数H，导致种群规模难以规定，本文引入均匀设计表的好格子点算法及其生成原理，生成可以满足任意条件的试验次数n、因素数s和因素水平数q的均匀设计表 $U_{n} (q^{s})$ ，运用如下变换计算，求s=3时的权重向量^［

15］

λ_{a}^{1} = 1 - \sqrt[]{\frac{U_{a, 1} - 0.5}{n}} a \in \{1,2, \dots, n\}

（11）

λ_{a}^{2} = \sqrt[]{\frac{U_{a, 1} - 0.5}{n}} \times (1 - \frac{U_{a, 2} - 0.5}{n})

（12）

λ_{a}^{3} = \sqrt[]{\frac{U_{a, 1} - 0.5}{n}} \times (\frac{U_{a, 2} - 0.5}{n})

（13）

式中： $λ_{a}^{1}$ 、 $λ_{a}^{2}$ 、 $λ_{a}^{3}$ 分别为3个目标值对应的权重向量；U_a，₁为均匀设计表的第 $a$ 行、第1列的元素；U_a，₂为均匀设计表的第 $a$ 行、第2列的元素。

2.3　初始种群的生成

初始种群对进化算法有显著影响，为保证种群的多样性，本文选用随机方式生成初始种群，分别计算出初始种群中个体的3个目标函数值，得到初始参考点，即当前种群个体3个目标函数值的最优值。

2.4　交叉和变异操作

2.4.1　交叉

MOEA/D算法的交叉操作是在权重向量的邻域随机找出2个体进行交叉。原始算法的交叉进化，选用模拟二进制交叉算子，本文引用正态分布交叉（Normal distribution crossover，NDC）算子^［

16］，对2个父代个体x₁和x₂，利用式（15，16），生成相应子代

x_{1}^{'}

和

x_{2}^{'}

。

当 $μ_{i} \leq 0.5$ 时，有

\{\begin{matrix} \begin{array}{l} x_{1}^{'} = 0.5 \times [(x_{1} + x_{2}) + 1.481 \times (x_{1} - x_{2}) \times \\ |N (0,1)|] \end{array} \\ \begin{array}{l} x_{2}^{'} = 0.5 \times [(x_{1} + x_{2}) - 1.481 \times (x_{1} - x_{2}) \times \\ |N (0,1)|] \end{array} \end{matrix}

（14）

当 $μ_{i} > 0.5$ 时，有

\{\begin{matrix} \begin{array}{l} x_{1}^{'} = 0.5 \times [(x_{1} + x_{2}) - 1.481 \times (x_{1} - x_{2}) \times \\ |N (0,1)|] \end{array} \\ \begin{array}{l} x_{2}^{'} = 0.5 \times [(x_{1} + x_{2}) + 1.481 \times (x_{1} - x_{2}) \times \\ |N (0,1)|] \end{array} \end{matrix}

（15）

式中： $μ_{i}$ 为［0，1］的随机数；N（0，1）表示服从均值为0，标准差为1的正态分布的随机数。相较于模拟二进制交叉算子，正态分布交叉的搜索范围更加广泛，全局寻优能力更为优秀，从而在Pareto前沿更具拓展性。

2.4.2　变异

高斯变异由高斯分布衍生而来，在进行高斯变异操作时，用一个均值 $μ$ 和方差 $σ^{2}$ 的正态分布的随机数来代替原值。高斯变异在上一代的某一区间内进行搜索，具有很好的局部搜索能力^［

17］，本文基于高斯变异提出一种自适应的高斯变异，表达式为

X_{n e w} = X + [\frac{i_{t}}{M a x_{t}} \times \frac{u_{i} - x_{i}}{u_{i} - w_{i}}] \times N (0,1)

（16）

式中：i_t为当前迭代次数；Max_t为最大迭代次数；u_i为当前种群个体距离参考点的欧式距离最大值；w_i为当前种群个体距离参考点的欧式距离最小值；x_i为当前个体距离参考点的欧式距离。自适应高斯变异使得变异结果与迭代结果相关联，在迭代初期，个体变化幅度相对较小，在迭代后期，变化幅度逐渐变大，随着i_t增大，高斯变异杰出的局部探索能力使候选解在局部范围进行精确搜索，提高了算法的寻优精度。

2.5　更新

交叉变异得到新解，更新参考点，更新邻域解，本文选用切比雪夫聚合分解法更新邻域，其表达式为

m i n g^{t e} (x | λ, z^{*}) = \underset{_{1 \leq i \leq m}}{m a x} \{λ_{i} | f_{i} (x) - z_{i}^{*}\}

（17）

式中：g^te为切比雪夫分解法的子问题表示方法； $λ = (λ_{1}, λ_{2}, \dots, λ_{m})$ 为权重向量； $z^{*} = (z_{1}^{*}, z_{2}^{*}, \dots, z_{m}^{*})$ 为参考点，可设置 $z_{i}^{*} = m i n \{f_{i} (x)\}$ ， $f_{i} (x)$ 为MOP的第i个子目标值。切比雪夫聚合法使个体与理想点在各维度上的目标值之差不断缩小，加速了种群的收敛速度。本文通过非劣排序解和小生境技术的拥挤距离来更新外部档案，每次迭代结束将当前解和外部档案合并，再从合并解集中移除所有被新解支配的向量，当合并数量达到外部档案数量上限，考虑其中的各个个体间的拥挤距离，保留较大拥挤距离的非劣解，剔除较小拥挤距离的非劣解，保证外部档案种群的多样性和优异性。

3 试验仿真与实际案例分析

3.1　试验构造及参数设置

本文算法采用MATLAB R2016a编写，程序运行环境为操作系统Windows7，处理器Inter i5‑8700H，主频2.80 GHz，内存8 GB。本文案例采用j*c*a命名，其中*代表一个正整数，例如j10c3a1，代表10个工件经过3个加工阶段加工，1则表示类型案例1，加工数据随机产生，其中工件的加工时间为在区间［5，15］之间的整数，每阶段的机器数量为在区间［2，4］之间的整数，机器加工时的单位时间能耗为在区间［5，10］之间的整数，机器空载时的单位时间能耗是在区间［1，3］之间的整数，机器加工的单位时间成本是在区间［10，20］之间的整数。随机生成20个案例，在j10c3a1~j10c3a5、j20c4a1~j20c4a5、j30c5a1~ j20c5a5、j50c5a1~j50c5a5案例中，运用IMOEAD、MOEA/D算法^［

18］和NSGA‑Ⅱ算法^{［参考文献 19

百度学术}19］求解并作对比。

3种算法的参数设置为：种群规模均设为50，迭代次数均设为200，IMOEAD和MOEA/D的外部档案大小设为50，IMOEAD的因素水平数q设为50，MOEA/D用户自定义参数H设为50。NSGA‑Ⅱ的交叉概率设为0.75，变异概率设为0.1。

3.1.1　评价指标

本文以反转世代距离（Inverted generational distance，IGD）^［

20］、欧式距离（Generational distance，GD）^{［参考文献 20

百度学术}20］和非支配解（Non‑dominated solution，NDS）^{［参考文献 21

百度学术}21］为评价性能指标。IGD表示真实帕累托前沿上的每个点到求得的帕累托前沿上距离最近的点，将这些点之间距离相加并取平均，用于评价算法的收敛性和多样性。GD表示求得的帕累托前沿的每个点到最近的真实帕累托前沿上的点的欧式距离取平均，用于评价算法的收敛性。NDS表示非支配解的个数，用于评价算法的多样性。其中IGD和GD的Pareto前沿参考点通过将所有算法所得的非支配解组成一个合集，移除集合中的被支配解，得到的集合即为Pareto前沿参考点。

3.1.2　结果对比

表1~3分别给出3种算法在每个案例独立运行10次后得到的IGD、GD和NDS表1中展示了20组试验案例的每个指标的最小值、最大值和平均值，粗体字表示每个指标的最优值。图3~5分别给出3种算法的IGD箱线图、GD箱线图和NDS箱线图。

表1 IGD实验结果对比

Table 1 Comparison of experimental results for IGD

案例	设备布局	IMOEAD			MOEA/D			NSGA‑Ⅱ
案例	设备布局	最小值	最大值	平均值	最小值	最大值	平均值	最小值	最大值	平均值
j10c3a1	2，2，3	0.008 3	0.010 7	0.009 1	0.013 6	0.022 3	0.018 9	0.014 2	0.022 1	0.019 2
j10c3a2	2，3，2	0.008 1	0.013 1	0.009 8	0.014 9	0.025 7	0.017 9	0.015 4	0.025 5	0.019 7
j10c3a3	3，3，2	0.007 9	0.014 5	0.010 3	0.016 6	0.024 6	0.020 0	0.015 9	0.026 1	0.020 7
j10c3a4	4，2，3	0.007 5	0.014 5	0.009 9	0.018 0	0.022 3	0.019 8	0.016 7	0.024 5	0.020 1
j10c3a5	4，3，2	0.007 0	0.014 6	0.010 2	0.016 9	0.023 8	0.019 8	0.017 8	0.026 6	0.019 7
j20c4a1	2，2，2，3	0.008 4	0.014 4	0.010 3	0.017 3	0.022 1	0.018 9	0.016 5	0.025 7	0.019 8
j20c4a2	2，3，3，2	0.007 7	0.014 2	0.010 4	0.017 5	0.026 3	0.021 0	0.018 4	0.026 6	0.021 7
j20c4a3	3，4，2，2	0.007 8	0.012 2	0.010 2	0.015 2	0.026 5	0.020 2	0.018 7	0.028 9	0.023 2
j20c4a4	4，2，2，3	0.007 8	0.015 6	0.011 3	0.017 6	0.028 5	0.022 5	0.017 8	0.029 6	0.023 0
j20c4a5	4，2，3，4	0.007 5	0.014 7	0.010 7	0.017 7	0.025 5	0.021 8	0.018 7	0.028 7	0.021 8
j30c5a1	2，3，2，2，2	0.006 2	0.010 2	0.008 4	0.022 5	0.029 9	0.026 8	0.022 0	0.029 9	0.025 9
j30c5a2	3，2，3，2，3	0.007 1	0.013 3	0.009 5	0.018 9	0.028 9	0.025 2	0.019 5	0.032 1	0.026 2
j30c5a3	2，2，4，2，3	0.007 2	0.016 3	0.011 1	0.018 8	0.029 8	0.022 9	0.020 1	0.030 0	0.025 3
j30c5a4	4，2，3，2，3	0.006 2	0.013 9	0.010 0	0.019 4	0.029 9	0.025 6	0.019 7	0.029 9	0.026 5
j30c5a5	3，4，2，2，3	0.007 0	0.010 2	0.008 8	0.019 8	0.027 8	0.024 7	0.016 8	0.029 4	0.025 8
j50c5a1	2，3，2，2，3	0.006 5	0.013 8	0.011 0	0.020 6	0.030 8	0.027 2	0.024 5	0.032 2	0.029 2
j50c5a2	3，2，3，2，3	0.008 0	0.013 8	0.009 3	0.019 9	0.031 1	0.027 9	0.025 3	0.032 1	0.029 0
j50c5a3	2，4，2，3，2	0.006 8	0.016 5	0.009 6	0.018 2	0.038 8	0.027 3	0.018 4	0.031 3	0.026 5
j50c5a4	3，4，2，2，3	0.006 4	0.010 9	0.008 7	0.018 9	0.030 1	0.026 2	0.022 1	0.033 5	0.027 3
j50c5a5	4，2，4，3，2	0.005 8	0.013 5	0.008 5	0.020 6	0.036 4	0.027 8	0.017 9	0.032 5	0.026 7
平均值		0.007 2	0.013 5	0.009 9	0.018 1	0.028 1	0.023 1	0.018 8	0.028 9	0.023 9

表2 GD实验结果对比

Table 2 Comparison of experimental results for GD

案例	设备布局	IMOEAD			MOEA/D			NSGA‑Ⅱ
案例	设备布局	最小值	最大值	平均值	最小值	最大值	平均值	最小值	最大值	平均值
j10c3a1	2，2，3	0.016 3	0.039 7	0.022 9	0.041 8	0.088 7	0.064 0	0.037 1	0.108 6	0.065 6
j10c3a2	2，3，2	0.010 6	0.036 5	0.024 1	0.041 8	0.090 8	0.070 1	0.048 2	0.094 2	0.061 2
j10c3a3	3，3，2	0.016 5	0.044 2	0.027 9	0.045 8	0.109 2	0.070 1	0.049 2	0.096 4	0.069 2
j10c3a4	4，2，3	0.016 4	0.032 9	0.020 5	0.049 3	0.095 4	0.069 0	0.045 1	0.110 4	0.077 4
j10c3a5	4，3，2	0.013 5	0.033 7	0.022 0	0.054 6	0.094 6	0.074 8	0.052 8	0.099 1	0.080 3
j20c4a1	2，2，2，3	0.016 9	0.038 7	0.024 1	0.058 9	0.107 1	0.078 1	0.045 4	0.132 8	0.086 6
j20c4a2	2，3，3，2	0.017 1	0.037 1	0.025 2	0.057 8	0.108 3	0.082 0	0.058 6	0.137 6	0.090 2
j20c4a3	3，4，2，2	0.018 4	0.036 3	0.026 5	0.053 4	0.124 9	0.082 3	0.048 9	0.128 8	0.086 0
j20c4a4	4，2，2，3	0.011 3	0.039 8	0.023 6	0.056 0	0.125 2	0.074 0	0.058 9	0.111 7	0.086 0
j20c4a5	4，2，3，4	0.012 7	0.036 9	0.023 6	0.053 3	0.115 3	0.079 8	0.060 3	0.140 1	0.090 6
j30c5a1	2，3，2，2，2	0.014 3	0.035 5	0.021 7	0.062 3	0.132 8	0.095 5	0.072 9	0.130 3	0.095 3
j30c5a2	3，2，3，2，3	0.013 2	0.038 2	0.023 9	0.071 0	0.132 0	0.089 5	0.069 4	0.134 6	0.092 8
j30c5a3	2，2，4，2，3	0.015 3	0.035 9	0.022 4	0.073 4	0.125 1	0.084 6	0.067 1	0.136 4	0.098 0
j30c5a4	4，2，3，2，3	0.016 5	0.030 6	0.024 8	0.070 0	0.139 9	0.105 7	0.084 6	0.133 9	0.118 1
j30c5a5	3，4，2，2，3	0.010 4	0.036 5	0.023 0	0.084 2	0.139 4	0.115 2	0.082 6	0.140 0	0.109 6
j50c5a1	2，3，2，2，3	0.011 2	0.037 8	0.025 2	0.091 9	0.138 8	0.124 4	0.081 3	0.148 6	0.122 2
j50c5a2	3，2，3，2，3	0.011 9	0.038 8	0.024 4	0.081 3	0.149 4	0.122 1	0.084 3	0.161 7	0.115 7
j50c5a3	2，4，2，3，2	0.012 4	0.034 1	0.022 3	0.087 1	0.164 1	0.130 0	0.098 5	0.169 9	0.127 5
j50c5a4	3，4，2，2，3	0.011 3	0.038 4	0.024 8	0.101 5	0.151 5	0.122 4	0.096 2	0.193 7	0.148 1
j50c5a5	4，2，4，3，2	0.012 1	0.035 4	0.024 6	0.103 0	0.165 9	0.138 7	0.119 7	0.201 9	0.166 2
平均值		0.013 9	0.036 9	0.023 9	0.066 9	0.124 9	0.093 6	0.068 1	0.135 5	0.099 3

表3 NDS实验结果对比

Table 3 Comparison of experimental results for NDS

案例	设备布局	IMOEAD			MOEA/D			NSGA‑Ⅱ
案例	设备布局	最小值	最大值	平均值	最小值	最大值	平均值	最小值	最大值	平均值
j10c3a1	2，2，3	26	35	31.9	11	20	15.6	6	15	9
j10c3a2	2，3，2	26	38	33.3	14	24	18.1	6	15	12
j10c3a3	3，3，2	26	37	32.7	11	17	15	8	16	11.9
j10c3a4	4，2，3	27	40	32	16	22	17.9	14	22	17.7
j10c3a5	4，3，2	25	38	34.2	13	20	17.4	11	20	15.9
j20c4a1	2，2，2，3	27	39	33.1	16	25	18.9	12	24	19.6
j20c4a2	2，3，3，2	30	38	33.9	12	23	17.9	8	19	15
j20c4a3	3，4，2，2	29	35	32.2	14	23	17	11	24	17.7
j20c4a4	4，2，2，3	30	38	33.2	13	21	16.6	12	26	17.3
j20c4a5	4，2，3，4	31	42	37.2	14	23	18.1	10	26	17.1
j30c5a1	2，3，2，2，2	29	38	33	12	22	16	13	21	16.1
j30c5a2	3，2，3，2，3	28	41	34	11	22	16.9	9	16	12
j30c5a3	2，2，4，2，3	30	37	33.8	12	27	18.3	13	26	19
j30c5a4	4，2，3，2，3	28	39	32.4	12	24	17.5	11	18	14.5
j30c5a5	3，4，2，2，3	29	37	32.9	15	22	17.6	12	18	15.1
j50c5a1	2，3，2，2，3	28	38	32.3	14	21	16.5	9	20	15.6
j50c5a2	3，2，3，2，3	31	37	34.9	13	25	17.4	12	25	16.4
j50c5a3	2，4，2，3，2	32	41	35.8	15	25	20.8	17	28	21.7
j50c5a4	3，4，2，2，3	27	40	33.3	14	25	18.7	12	22	17.9
j50c5a5	4，2，4，3，2	25	36	31.6	14	24	19.5	14	28	20
平均值		28.20	38.20	33.39	13.30	22.75	17.59	11.00	21.45	16.08

图3 3种算法IGD箱线图

Fig.3 IGD box diagram of three algorithms

图4 3种算法GD箱线图

Fig.4 GD box diagram of three algorithms

图5 3种算法NDS箱线图

Fig.5 NDS box diagram of three algorithms

由表1的结果可以看出，20组案例独立运行10次，IMOEAD得到的IGD最小值、最大值和平均值的均值分别为0.007 2、0.013 5、0.009 9，远小于MOEA/D求得的结果0.018 1、0.028 1、0.023 1和NSGA‑Ⅱ求得的结果0.018 8、0.028 9、0.023 9。由表2的结果可以看出，20组案例独立运行10次，IMOEAD得到的GD最小值、最大值和平均值的均值分别为0.013 9、0.036 9、0.023 9，远小于MOEA/D求得的结果0.066 9、0.124 9、0.093 6和NSGA‑Ⅱ求得的结果0.068 1、0.135 5、0.099 3。由表3的结果可以看出，20组案例独立运行10次，IMOEAD得到的NDS最小值、最大值和平均值的均值分别为28.20、38.20、33.39，远大于MOEA/D求得的结果13.30、22.75、17.59和NSGA‑Ⅱ求得的结果11.00、21.45、16.08。从3个性能指标平均值结果可以看出，IMOEAD的收敛性和多样性相较于其他两种算法更优。

从表1~3中的IGD值和GD值看出，随着问题规模的增加，3种算法所得两个评价指标的差距也越来越大，在案例j10c3a1中，IMOEAD求得IGD和GD平均值分别为0.009 1和0.002 29，MOEA/D求得IGD和GD平均值分别为0.018 9、0.064 0，NSGA‑Ⅱ求得IGD和GD平均值分别为0.019 2、0.065 6；在案例j50c5a1中，IMOEAD求得IGD和GD平均值分别为0.011 0和0.025 2，MOEA/D求得IGD和GD平均值分别为0.026 8、0.124 4，NSGA‑Ⅱ求得IGD和GD平均值分别为0.025 9、0.122 2，随着问题规模增加，IMOEAD求得的非支配解集与非劣解越贴近，MOEA/D和NSGA‑Ⅱ求得的非支配解集与非劣解相距越远。

由图3，4可以看出，IMOEAD的箱线图相较于其他两种算法更加扁平，表明方差更小，其稳定性更好。由图3~5可以看出，图3，4中IMOEAD的箱线图相较于其他两种算法中位线明显更低，图5中更高，说明其得到的非劣解集质量更加良好。

图6，7分别为j20c4a5案例和j50c5a1案例运用3种算法求解出的非劣解。从图6中可以看出，IMOEAD求解所得解集对应的3个目标值相较其他两种算法更优。非劣解图的点对应不同的调度方案，如图6中圈出的解［132，9 555，4 324］，分别对应完工时间、机器加工成本和机器总能耗，该解对应的完工时间调度甘特图如图8所示。类似地，图7中圈出的解对应的完工时间调度甘特图如图9所示。

图6 j20c4a5案例3种算法的非劣解

Fig.6 Non‑inferior solutions of three algorithms forj20c4a5 case

图7 j50c5a1案例3种算法的非劣解

Fig.7 Non inferior solutions of three algorithms for j50c5a1 case

图8 j20c4a5案例调度甘特图

Fig.8 Gantt chart for j20c4a5 case

图9 j50c5a1案例调度甘特图

Fig.9 Gantt chart for j50c5a1 case

3.2　实际案例应用

某汽车制造企业，发动机生产车间拥有汽车发动机缸体、缸盖、部装和总装等多条生产线，具有高效率的特点。随着中国政府排放法规的出台，公司不得不考虑绿色指标，实现绿色制造，提高公司竞争力。本文着重研究曲轴、缸盖、缸体、齿轮箱和连杆共5个工件的加工，这些工件采用铣床、车床和磨床分别进行加工，目前该公司混合流水线有3台铣床、2台车床和2台磨床。工件在各机器上的加工时间如表4所示，各台机器的单位时间成本和加工空载能耗如表5所示。

表4 工件在各机器上的加工时间

Table 4 Processing time of workpieces on each machine ( min )

工件	铣			车		磨
工件	1‑1	1‑2	1‑3	2‑1	2‑2	3‑1	3‑2
曲轴	4	5	4	4	3	2	3
缸盖	4	5	4	3	4	4	3
缸体	5	3	4	2	2	3	2
齿轮箱	5	4	6	4	3	3	2
连杆	2	2	3	3	2	2	2

表5 各台机器性能指标

Table 5 Performance index of each machine

指标	可选机器
指标	1‑1	1‑2	1‑3	2‑1	2‑2	3‑1	3‑2
单位成本/元	8	9	7	5	6	4	3
空载能耗/（kW·h）	1.8	2	1.5	1.1	1	0.8	1
加工能耗/（kW·h）	10	13	12	5	13	16	15

算法种群数量、迭代次数等参数设置同3.1节。3种算法求解实例所得非劣解图如图10所示。由图10看出，IMOEAD求解实际的车间调度案例所得非劣解相较于MOEA/D和NSGA‑Ⅱ求得的非劣解更优，在实际的混合流水车间生产制造过程中，同时优化多个目标，车间调度人员需要在各目标之间进行权衡取得权值，以获得一组最优的生产调度方案。

图10 实例非劣解图

Fig.10 Non inferiority solutions of actual case

4 结论

（1）考虑能耗且带有不相关并行机的HFSP，建立以最大完工时间、机器总能耗和机器加工成本为求解目标的问题模型，提出IMOEAD算法求解此问题。

（2）基于原MOEA/D算法的缺陷，结合均匀设计表、正态分布和自适应高斯变异，加强了算法的全局搜索能力和局部搜索能力。

（3）通过随机生成的20组不同规模案例，分别运用IMOEAD、MOEA/D和NSGA‑Ⅱ求解，结合试验结果数据表格和箱线图，可以看出IMOEAD相较于其他两种算法所求的非支配解集更优，更贴近于真实Pareto前沿。实际案例进一步验证了IMOEAD求解考虑能耗的HFSP，具有优良的收敛性、多样性和稳定性。

参考文献

王圣尧，王凌，许烨，等.求解混合流水车间调度问题的分布估计算法［J］.自动化学报，2012，38（3）： 437-443. [百度学术]

WANG Shengyao，WANG Ling，XU Ye ，et al. An estimation of distribution algorithm for solving hybrid flow-shop scheduling problem［J］. Acta Automatica Sinica， 2012， 38（3）： 437-443. [百度学术]

张源，陶翼飞，王加冕.改进差分进化算法求解混合流水车间调度问题［J］.中国机械工程，2021，32（6）：714-720. [百度学术]

ZHANG Yuan， TAO Yifei， WANG Jiamian. An improved DE algorithm for solving hybrid flow-shop scheduling problems［J］. China Mechanical Engineering， 2021， 32（6）： 714-720. [百度学术]

Zhou B H， Hu L M， ZHONG Z Y. A hybrid differential evolution algorithm with estimation of distribution algorithm for reentrant hybrid flow shop scheduling problem［J］. Neural Computing and Applications， 2018， 30（1）：193-209. [百度学术]

GHALEB M A， ALHARKAN I M. Particle swarm optimization algorithms for two-stage hybrid flow-shop scheduling problem with no-wait［J］. Universal Journal of Electrical and Electronic Engineering， 2019， 6（2）：46-60. [百度学术]

MENG L L， ZHANG C Y， SHAO X Y， et al. Mathematical modelling and optimization of energy-conscious hybrid flow shop scheduling problem with unrelated parallel machines［J］. International Journal of Production Research， 2019， 57（4）： 1119-1145. [百度学术]

罗函明，罗天洪，吴晓东，等.求解混合流水车间调度问题的离散布谷鸟算法［J］.计算机工程与应用，2020，56（22）： 264-271. [百度学术]

LUO Hanming， LUO Tianhong， WU Xiaodong， et al. Discrete cuckoo search algorithm for solving hybrid flow-shop scheduling problem［J］. Computer Engineering and Applications， 2020， 56（22）： 264-271. [百度学术]

杜利珍，王震，柯善富，等.混合流水车间调度问题的果蝇优化算法求解［J］.中国机械工程，2019，30（12）：1480-1485. [百度学术]

DU Lizhen，WANG Zhen， KE Shanfu， et al. Fruit fly optimization algorithm for solving hybrid flow-shop scheduling problems［J］. China Mechanical Engineering， 2019，30（12）：1480-1485. [百度学术]

宋存利.求解混合流水车间调度的改进贪婪遗传算法［J］.系统工程与电子技术，2019，41（5）：1079-1086. [百度学术]

SONG Cunli. Improved greedy genetic algorithm for solving the hybrid flow-shop scheduling problem［J］. Systems Engineering and Electronics， 2019， 41（5）：1079-1086. [百度学术]

Mousavi S M， Mahdavi I， Rezaeian J， et al. An efficient bi-objective algorithm to solve re-entrant hybrid flow shop scheduling with learning effect and setup times［J］. Operational Research， 2018， 18（1）：123-158. [百度学术]

雷德明，杨冬婧.基于新型蛙跳算法的低碳混合流水车间调度［J］.控制与决策，2020，35（6）：1329-1337. [百度学术]

LEI Deming， YANG Dongjing. A novel shuffled frog-leaping algorithm for low carbon hybrid flow shop scheduling［J］. Control and Decision， 2020，35（6）：1329-1337. [百度学术]

黄辉，李梦想，严永.考虑序列设置时间的混合流水车间多目标调度研究［J］.运筹与管理，2020，29（12）：215-221. [百度学术]

HUANG Hui， LI Mengxiang， YAN Yong. Research on multi-objective scheduling of hybrid flow production shop considering sequence setting time［J］. Operations Research and Management Science， 2020，29（12）： 215-221. [百度学术]

KARIMI N， DAVOUPOUR H. Multi-objective colonial competitive algorithm for hybrid flow-shop problem［J］. Applied Soft Computing， 2016， 49：725-733. [百度学术]

LONG J， ZHENG Z， GAO X，et al. A hybrid multi-objective evolutionary algorithm based on NSGA-Ⅱfor practical scheduling with release times in steel plants［J］. Journal of the Operational Research Society， 2016，67（9）： 1184-1199. [百度学术]

DAI M， TANG D B， GIRET A， et al. Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm［J］. Robotics and Computer-Integrated Manufacturing， 2013， 29（5）： 418-429. [百度学术]

曹慧荣，李莉.均匀设计表的MATLAB实现［J］.统计与决策，2008，21（6）： 144-146. [百度学术]

CAO Huirong， LI Li. Uniform design table in Matlab ［J］. Statistics and Decision， 2008，21（6）： 144-146. [百度学术]

李进，李二超.基于正态分布和自适应变异算子的ε截断算法［J］.山东大学学报（工学版），2019，49（2）：47-53. [百度学术]

LI Jin， LI Erchao. Epsilon truncation algorithm based on NDX and adaptive mutation operator［J］. Journal of Shandong University（Engineering Science）， 2019， 49（2）： 47-53. [百度学术]

陈雷，尹钧圣.高斯差分变异和对数惯性权重优化的鲸群算法［J］.计算机工程与应用，2021，57（2）：77-90. [百度学术]

CHEN Lei， YIN Junsheng. Whale swarm optimization algorithm based on Gaussian difference mutation and logarithmic inertia weight［J］. Computer Engineering and Applications， 2021， 57（2）： 77-90. [百度学术]

ZHANG Q， LI H. MOEA/D： A multiobjective evolutionary algorithm based on decomposition［J］. IEEE Transactions on Evolutionary Computation， 2007， 11（6）： 712-731. [百度学术]

DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGA-II［J］. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197. [百度学术]

WANG G， GAO L， LI X Y， et al. Energy-efficient distributed permutation flow shop scheduling problem using a multi-objective whale swarm algorithm［J］. Swarm and Evolutionary Computation， 2020， 57： 1-17. [百度学术]

牟健慧，郭前建，高亮，等.基于混合的多目标遗传算法的多目标流水车间逆调度问题求解方法［J］.机械工程学报，2016，52（22）： 186-197. [百度学术]

MOU Jianhui， GUO Qianjian， GAO Liang， et al. Multi-objective genetic algorithm for solving multi-objective flow-shop inverse scheduling problems［J］. Journal of Mechanical Engineering， 2016，52（22）：186-197. [百度学术]

请使用 Firefox、Chrome、IE10、IE11、360极速模式、搜狗极速模式、QQ极速模式等浏览器，其他浏览器不建议使用!

多目标混合流水车间调度问题求解算法 PDF

摘要

关键词

1 问题描述与建模

2 IMOEAD算法

2.1 编码与解码

2.2 生成权重向量

2.3 初始种群的生成

2.4 交叉和变异操作

2.5 更新