多因素柔性作业车间绿色调度的改进进化算法

doi:10.11772/j.issn.1001-9081.2024050727

《计算机应用》唯一官方网站 ›› 2025, Vol. 45 ›› Issue (6): 1954-1962.DOI: 10.11772/j.issn.1001-9081.2024050727

• 先进计算 • 上一篇

多因素柔性作业车间绿色调度的改进进化算法

王建华¹, 吴传宇¹(), 许莉萍²

^1.江苏大学管理学院，江苏镇江 212013
^2.合肥工业大学管理学院，合肥 230009

收稿日期:2024-06-03 修回日期:2024-07-30 接受日期:2024-08-08 发布日期:2024-08-20 出版日期:2025-06-10
通讯作者: 吴传宇
作者简介:王建华（1977—），男，安徽庐州人，副教授，博士，主要研究方向：智能调度优化及运作仿真
吴传宇（1999—），男，江苏南京人，硕士研究生，主要研究方向：车间智能调度优化 w138524679@126.com
许莉萍（1999—），女，福建福州人，博士研究生，主要研究方向：调度理论与算法、智能优化算法。
基金资助:
国家社会科学基金重点项目(23AGL032)

Enhanced evolutionary algorithm for multi-factor flexible job shop green scheduling

Jianhua WANG¹, Chuanyu WU¹(), Liping XU²

^1.School of Management，Jiangsu University，Zhenjiang Jiangsu 212013，China
^2.School of Management，Hefei University of Technology，Hefei Anhui 230009，China

Received:2024-06-03 Revised:2024-07-30 Accepted:2024-08-08 Online:2024-08-20 Published:2025-06-10
Contact: Chuanyu WU
About author:WANG Jianhua， born in 1977， Ph. D.， associate professor. His research interests include intelligent scheduling optimization and operational simulation.
WU Chuanyu， born in 1999， M. S. candidate. His research interests include intelligent job shop scheduling optimization.
XU Liping， born in 1999， Ph. D. candidate. Her research interests include scheduling theory and algorithms， intelligent optimization algorithms.
Supported by:
Key Project of National Social Science Foundation of China(23AGL032)

摘要/Abstract

摘要：

针对考虑设置与运输时间约束且机器加工速度可变的多因素柔性作业车间绿色调度问题（MFJGSP-STVS），构建以完工时间与能源消耗为优化目标的数学模型，并提出一种改进的多目标进化算法（EMoEA）求解该问题。该算法采用三层整数编码方式，在解码中使用机器空闲时间优先（MIP）规则和开关机策略（TOF）优化目标，利用全局搜索（GS）等启发式规则生成初始种群；为了加快算法收敛，基于非支配分层思想设计一种聚类交叉方式；为防止算法过早收敛而陷入局部最优，采用衍生策略扩散非支配解集，通过基于关键路径的自适应局部搜索策略进一步强化算法探索解空间的能力。仿真实验结果表明，与原始的多目标进化算法相比，EMoEA中的每个设计都有更优的超体积（HV）与逆世代距离（IGD）指标；与非支配排序遗传算法（NSGA-Ⅱ）和混合Jaya（HJaya）算法相比，EMoEA在HV与IGD这2个指标上占据优势，且收敛较快，在大多数实例中都获得最优的目标值。可见，EMoEA性能更好，能有效地解决MFJGSP-STVS，为企业提供高质量的调度方案。

关键词: 设置与运输时间, 机器可变加工速度, 柔性作业车间绿色调度, 聚类交叉, 衍生策略, 自适应局部搜索

Abstract:

For Multi-factor Flexible Job shop Green Scheduling Problem with Setup and Transportation time constraints and Variable machine processing Speed （MFJGSP-STVS）， a mathematical model with completion time and energy consumption as optimization objectives was constructed， and an Enhanced Multi-objective Evolutionary Algorithm （EMoEA） was proposed to solve the problem. In the algorithm， a three-layer integer encoding method was adopted， Machine Idle time Preference （MIP） rule and Turning On/Off strategy （TOF） were applied in the decoding to optimize the objectives， and heuristic rules such as Global Search （GS） were employed to generate the initial population； a cluster crossover approach was designed on the basis of non-dominated hierarchy idea， so as to accelerate the algorithm’s convergence； to prevent the algorithm from converging prematurely and falling into the local optimum， a derivation strategy was proposed to diffuse the non-dominated solution set， and an adaptive local search strategy based on critical path was designed to further enhance the exploration capability of the algorithm in solution space. Simulation results show that each design in EMoEA has better Hypervolume （HV） and Inverted Generational Distance （IGD） metrics compared to the original multi-objective evolutionary algorithm， and compared to Non-dominated Sorting Genetic Algorithm Ⅱ （NSGA-Ⅱ） and Hybrid Jaya （HJaya） algorithm， EMoEA achieves advantages in both HV and IGD metrics with faster convergence and the optimal objective value on most instances. It can be seen that EMoEA has better performance， and EMoEA can solve MFJGSP-STVS effectively， providing high-quality scheduling schemes for enterprises.

Key words: setup and transportation time, machine variable processing speed, flexible job shop green scheduling, cluster crossover, derivation strategy, adaptive local search

中图分类号:

TP18

王建华, 吴传宇, 许莉萍. 多因素柔性作业车间绿色调度的改进进化算法[J]. 计算机应用, 2025, 45(6): 1954-1962.

Jianhua WANG, Chuanyu WU, Liping XU. Enhanced evolutionary algorithm for multi-factor flexible job shop green scheduling[J]. Journal of Computer Applications, 2025, 45(6): 1954-1962.

图/表 15

表1 符号与解释

Tab. 1 Symbols and explanations

符号	解释	符号	解释
i，h	工件索引	k，w	机器索引
j，l	工序索引	q， $q'$	机器加工速度索引
$O i j$	工件i的第j个工序	$n i$	工件i的工序数
n	工件数	m	机器数
$C m a x$	最大完工时间	$T i (j - 1) j w k$	工件i在机器k与w之间的运输时间
$C i j k q$	工序 $O i j$ 在速度为q的机器k上的完工时间	$T S i j k q$	机器k在以速度q加工 $O i j$ 之前的设置时间
$C i (j - 1)$	$O i (j - 1)$ 的完工时间	$T D i j h l k$	机器k在加工 $O i j$ 与 $O h l$ 之间的空闲时间
$T i j k q$	机器k以速度q加工 $O i j$ 的时间	$Z k q$	机器k的空闲功率
$P S i j k q$	机器k在以速度q加工 $O i j$ 之前的设置功率	$P k q$	机器k加工功率
$Q g$	开关机总能耗	$Q D i j h l k$	机器k在加工 $O i j$ 与 $O h l$ 之间空闲能耗
$Q s$	机器设置总能耗	$H k$	机器k关机时间阈值
$Q u$	辅助设备总能耗	$T k 1$	机器k开机持续时间
$Q d$	机器空闲总能耗	$T k 2$	机器k关机持续时间
$Q c$	机器加工总能耗	$E k 1$	机器k开机的能耗
$Q t$	工件运输总能耗	$E k 2$	机器k关机的能耗
$P t$	工件运输功率	$X i j k q$	$O i j$ 在速度为q的机器k上加工为1，否则为0
$P 0$	辅助设备功率	$Y i j h l k$	在机器k上， $O i j$ 在 $O h l$ 前面加工为-1， $O i j$ 在 $O h l$ 后面加工为1，不相邻为0
$U i j h l k$	机器k可以在 $O i j$ 与 $O h l$ 之间关机为1，否则为0	$Y i j h l k$

表1 符号与解释

Tab. 1 Symbols and explanations

符号	解释	符号	解释
i，h	工件索引	k，w	机器索引
j，l	工序索引	q， $q'$	机器加工速度索引
$O i j$	工件i的第j个工序	$n i$	工件i的工序数
n	工件数	m	机器数
$C m a x$	最大完工时间	$T i (j - 1) j w k$	工件i在机器k与w之间的运输时间
$C i j k q$	工序 $O i j$ 在速度为q的机器k上的完工时间	$T S i j k q$	机器k在以速度q加工 $O i j$ 之前的设置时间
$C i (j - 1)$	$O i (j - 1)$ 的完工时间	$T D i j h l k$	机器k在加工 $O i j$ 与 $O h l$ 之间的空闲时间
$T i j k q$	机器k以速度q加工 $O i j$ 的时间	$Z k q$	机器k的空闲功率
$P S i j k q$	机器k在以速度q加工 $O i j$ 之前的设置功率	$P k q$	机器k加工功率
$Q g$	开关机总能耗	$Q D i j h l k$	机器k在加工 $O i j$ 与 $O h l$ 之间空闲能耗
$Q s$	机器设置总能耗	$H k$	机器k关机时间阈值
$Q u$	辅助设备总能耗	$T k 1$	机器k开机持续时间
$Q d$	机器空闲总能耗	$T k 2$	机器k关机持续时间
$Q c$	机器加工总能耗	$E k 1$	机器k开机的能耗
$Q t$	工件运输总能耗	$E k 2$	机器k关机的能耗
$P t$	工件运输功率	$X i j k q$	$O i j$ 在速度为q的机器k上加工为1，否则为0
$P 0$	辅助设备功率	$Y i j h l k$	在机器k上， $O i j$ 在 $O h l$ 前面加工为-1， $O i j$ 在 $O h l$ 后面加工为1，不相邻为0
$U i j h l k$	机器k可以在 $O i j$ 与 $O h l$ 之间关机为1，否则为0	$Y i j h l k$

图1 EMoEA的框架

Fig. 1 Framework of EMoEA

图2 编码方式

Fig. 2 Encoding method

图3 应用MIP的例子

Fig. 3 Example of MIP application

图4 开关机策略

Fig. 4 Turning on/off strategy

图5 聚类交叉

Fig. 5 Cluster crossover

图6 交叉算子

Fig. 6 Crossover operators

图7 衍生策略

Fig. 7 Derivation strategy

图8 寻找关键路径

Fig. 8 Finding critical path

表2 成功和失败记忆表

Tab. 2 Success and failure memory table

迭代次数	成功记忆					失败记忆
迭代次数	N₁	N₂	N₃	N₄	N₅	N₁	N₂	N₃	N₄	N₅
1	$n s 1, T - L P$	$n s 2, T - L P$	$n s 3, T - L P$	$n s 4, T - L P$	$n s 5, T - L P$	$n f 1, T - L P$	$n f 2, T - L P$	$n f 3, T - L P$	$n f 4, T - L P$	$n f 5, T - L P$
2	$n s 1, T - L P + 1$	$n s 2, T - L P + 1$	$n s 3, T - L P + 1$	$n s 4, T - L P + 1$	$n s 5, T - L P + 1$	$n f 1, T - L P + 1$	$n f 2, T - L P + 1$	$n f 3, T - L P + 1$	$n f 4, T - L P + 1$	$n f 5, T - L P + 1$
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$
LP	$n s 1, T - 1$	$n s 2, T - 1$	$n s 3, T - 1$	$n s 4, T - 1$	$n s 5, T - 1$	$n f 1, T - 1$	$n f 2, T - 1$	$n f 3, T - 1$	$n f 4, T - 1$	$n f 5, T - 1$

表2 成功和失败记忆表

Tab. 2 Success and failure memory table

迭代次数	成功记忆					失败记忆
迭代次数	N₁	N₂	N₃	N₄	N₅	N₁	N₂	N₃	N₄	N₅
1	$n s 1, T - L P$	$n s 2, T - L P$	$n s 3, T - L P$	$n s 4, T - L P$	$n s 5, T - L P$	$n f 1, T - L P$	$n f 2, T - L P$	$n f 3, T - L P$	$n f 4, T - L P$	$n f 5, T - L P$
2	$n s 1, T - L P + 1$	$n s 2, T - L P + 1$	$n s 3, T - L P + 1$	$n s 4, T - L P + 1$	$n s 5, T - L P + 1$	$n f 1, T - L P + 1$	$n f 2, T - L P + 1$	$n f 3, T - L P + 1$	$n f 4, T - L P + 1$	$n f 5, T - L P + 1$
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$
LP	$n s 1, T - 1$	$n s 2, T - 1$	$n s 3, T - 1$	$n s 4, T - 1$	$n s 5, T - 1$	$n f 1, T - 1$	$n f 2, T - 1$	$n f 3, T - 1$	$n f 4, T - 1$	$n f 5, T - 1$

图9 5种算法在HV与IGD指标上的箱线图

Fig. 9 Box plots of five algorithms in HV and IGD metrics

图10 3种算法在HV与IGD指标上的箱线图

Fig. 10 Box plots of three algorithms in HV and IGD metrics

表3 3种算法的最优目标值

Tab. 3 Optimal objective values of three algorithms

实例	最大完工时间最小值			总能耗最低值
实例	HJaya	NSGA-Ⅱ	EMoEA	HJaya	NSGA-Ⅱ	EMoEA
MK01	77	76	78	156 459	148 806	145 799
MK02	73	69	69	144 907	133 025	129 317
MK03	293	245	243	439 621	437 112	427 446
MK04	132	133	134	271 365	252 168	250 002
MK05	300	292	290	287 710	276 772	274 657
MK06	171	152	151	561 529	521 052	512 383
MK07	498	412	408	476 690	496 564	485 735
MK08	560	548	539	850 754	798 003	786 276
MK09	547	520	509	822 862	794 960	794 008
MK10	466	404	405	999 714	913 659	908 137
MK11	1090	1034	1011	603 962	578 394	584 268
MK12	758	707	681	769 961	710 623	687 939
MK13	606	537	551	602 436	563 349	585 832
MK14	702	685	653	984 809	944 220	922 213
MK15	642	628	609	965 025	903 983	887 329

图11 3种算法在2种目标上的收敛曲线

Fig. 11 Convergence curves of three algorithms in two objectives

图12 3种算法的帕累托前沿

Fig. 12 Pareto fronts of three algorithms

参考文献 22

1	PEZZELLA F， MORGANTI G， CIASCHETTIG. A genetic algorithm for the Flexible Job-Shop Scheduling Problem［J］. Computers and Operations Research， 2008， 35（10）： 3202-3212.
2	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 ［J］. Computers and Operations Research， 2021， 135： No.105431.
3	孟冠军，黄江涛，魏亚博. 混合白鲸优化算法求解柔性作业车间调度问题［J］. 计算机工程与应用， 2024， 60（12）：325-333.
	MENG G J， HUANG J T， WEI Y B. Hybrid beluga whale optimization algorithm for flexible job shop scheduling problem［J］. Computer Engineering and Applications， 2024， 60（12）： 325-333.
4	LI J Q， PAN Q K， LIANG Y C. An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems［J］. Computers and Industrial Engineering， 2010， 59（4）： 647-662.
5	CALDEIRA R H， GNANAVELBABU A. A Pareto based discrete Jaya algorithm for multi-objective flexible job shop scheduling problem［J］. Expert Systems with Applications， 2021， 170： No.114567.
6	王秋莲，段星皓. 基于高维多目标候鸟优化算法的柔性作业车间调度［J］. 中国机械工程， 2022， 33（21）：2601-2612.
	WANG Q L， DUAN X H. Scheduling of flexible job shop based on high-dimension and multi-objective migrating bird optimization algorithm［J］. China Mechanical Engineering， 2022， 33（21）： 2601-2612.
7	胡晓阳，姚锡凡，黄鹏，等. 改进迭代局部搜索算法求解多AGV柔性作业车间调度问题［J］. 计算机集成制造系统， 2022， 28（7）： 2198-2112.
	HU X Y， YAO X F， HUANG P， et al. Improved iterative local search algorithm for solving multi-AGV flexible job shop scheduling problem［J］. Computer Integrated Manufacturing Systems， 2022， 28（7）： 2198-2112.
8	张国辉，胡一凡，孙靖贺. 改进遗传算法求解多时间约束的柔性作业车间调度问题［J］. 工业工程， 2020， 23（2）： 19-25， 48.
	ZHANG G H， HU Y F， SUN J H. An improved genetic algorithm for flexible job shop scheduling problem with multiple time constraints［J］. Industrial Engineering Journal， 2020， 23（2）： 19-25， 48.
9	LI J Q， DENG J W， LI C Y， et al. An improved Jaya algorithm for solving the flexible job shop scheduling problem with transportation and setup times［J］. Knowledge-Based Systems， 2020， 200： No.106032.
10	李晓辉，资湖海，徐坷鑫，等. 带有充电约束的多AGV柔性作业车间调度［J/OL］. 计算机工程［2024-07-11］..
	LI X H， ZI H H， XU K X， et al. Multi-AGV flexible job shop scheduling with charging constraints［J/OL］. Computer Engineering ［2024-07-11］..
11	MOUZON G， YILDIRIM M B， TWOMEY J. Operational methods for minimization of energy consumption of manufacturing equipment［J］. International Journal of Production Research， 2007， 45（18/19）： 4247-4271.
12	WU X， SUN Y. A green scheduling algorithm for flexible job shop with energy-saving measures［J］. Journal of Cleaner Production， 2018， 172： 3249-3264.
13	DUAN J， WANG J. Energy-efficient scheduling for a flexible job shop with machine breakdowns considering machine idle time arrangement and machine speed level selection［J］. Computers and Industrial Engineering， 2021， 161： No.107677.
14	WEI Z， LIAO W， ZHANG L. Hybrid energy-efficient scheduling measures for flexible job-shop problem with variable machining speeds［J］. Expert Systems with Applications， 2022， 197： No.116785.
15	马训德，毕利，王俊杰. 基于离散冠状病毒群体免疫算法的多转速绿色柔性车间调度研究［J/OL］. 系统仿真学报［2024-07-11］..
	MA X D， BI L， WANG J J. Discrete coronavirus immunity optimizer algorithm for green flexible job shop scheduling with multi-speed machines［J/OL］. Journal of System Simulation ［2024-07-11］..
16	王亚昆，刘应波，吴永明，等. 改进 NSGA-Ⅱ 算法求解考虑运输约束的柔性作业车间节能调度问题［J］. 计算机集成制造系统， 2023， 29（9）： 3028-3034.
	WANG Y K， LIU Y B， WU Y M， et al. Improved NSGA-Ⅱ algorithm to solve energy-saving scheduling problem of flexible job shop considering transportation constraints［J］. Computer Integrated Manufacturing Systems， 2023， 29（9）： 3028-3034.
17	徐宜刚，陈勇，王宸，等. 改进NSGA-Ⅲ求解高维多目标绿色柔性作业车间调度问题［J］. 系统仿真学报， 2024， 36（10）：2314-2329.
	XU Y G， CHEN Y， WANG C， et al. Improving NSGA-Ⅲ algorithm for solving high-dimensional many-objective green flexible job shop scheduling problem［J］. Journal of System Simulation， 2024， 36（10）：2314-2329.
18	ZHANG G， GAO L， SHI Y. An effective genetic algorithm for the flexible job-shop scheduling problem［J］. Expert Systems with Applications， 2011， 38（4）： 3563-3573.
19	GAO J， SUN L， GEN M. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems［J］. Computers and Operations Research， 2008， 35（9）： 2892-2907.
20	QIN A K， HUANG V L， SUGANTHAN P N. Differential evolution algorithm with strategy adaptation for global numerical optimization ［J］. IEEE Transactions on Evolutionary Computation， 2009， 13（2）： 398-417.
21	BRANDIMARTE P. Routing and scheduling in a flexible job shop by tabu search［J］. Annals of Operations Research， 1993， 41（3）： 157-183.
22	FAN J， SHEN W， GAO L， et al. A hybrid Jaya algorithm for solving flexible job shop scheduling problem considering multiple critical paths［J］. Journal of Manufacturing Systems， 2021， 60： 298-311.

[1]	张淑芬汤本建田子坤秦肖阳. 基于差分隐私的联邦学习研究综述[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	颜文婧, 王瑞东, 左敏, 张青川. 基于风味嵌入异构图层次学习的食谱推荐模型[J]. 《计算机应用》唯一官方网站, 2025, 45(6): 1869-1878.
[3]	闫龙博, 毛文涛, 仲志鸿, 范黎林. 面向城市排水管网缺陷诊断的鲁棒无监督多任务异常检测方法[J]. 《计算机应用》唯一官方网站, 2025, 45(6): 1833-1840.
[4]	李岚皓, 严皓钧, 周号益, 孙庆赟, 李建欣. 基于神经网络的多尺度信息融合时间序列长期预测模型[J]. 《计算机应用》唯一官方网站, 2025, 45(6): 1776-1783.
[5]	何玉林, 李旭, 贺颖婷, 崔来中, 黄哲学. 基于最大均值差异的子空间高斯混合模型聚类集成算法[J]. 《计算机应用》唯一官方网站, 2025, 45(6): 1712-1723.
[6]	熊前龙秦进. 混合启发信息指导神经网络架构搜索算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[7]	姜勇维陈晓清付麟杰. 基于频谱分解的高频保持医学图像弹性配准模型[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[8]	白晓磊张雪元王智永全力刘欣. 基于Mamba模型的区域电价预测方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[9]	周贤文龙潇余欣磊张依恋. 基于改进Q学习的智能车辆多场景安全刹车算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[10]	付锦程杨仕友. 基于贝叶斯优化和特征融合混合模型的短期风电功率预测[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[11]	何金栋及宇轩陈天赐许恒铭耿技曹明生梁员宁. 基于大模型的非智能传感器的实体发现方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[12]	张寒崧, 贺毅朝, 孙菲, 陈国新, 陈炬. 基于新修复优化算子的改进环论优化算法求解多维背包问题[J]. 《计算机应用》唯一官方网站, 2025, 45(5): 1595-1604.
[13]	曾碧卿, 钟广彬, 温志庆. 基于分解式模糊跨度的小样本命名实体识别[J]. 《计算机应用》唯一官方网站, 2025, 45(5): 1504-1510.
[14]	王泉, 陆啟想, 施珮. 用于交通流量预测的多图扩散注意力网络[J]. 《计算机应用》唯一官方网站, 2025, 45(5): 1472-1479.
[15]	陈昕, 刘忠慧, 闵帆. 约简形式背景下的概念集构造及其推荐应用[J]. 《计算机应用》唯一官方网站, 2025, 45(5): 1415-1423.

多因素柔性作业车间绿色调度的改进进化算法

Enhanced evolutionary algorithm for multi-factor flexible job shop green scheduling

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 22

相关文章 15

编辑推荐

Metrics