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

doi:10.11772/j.issn.1001-9081.2024050727

Journal of Computer Applications ›› 2025, Vol. 45 ›› Issue (6): 1954-1962.DOI: 10.11772/j.issn.1001-9081.2024050727

• Advanced computing • Previous Articles

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)

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP18

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.

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

Figures/Tables 15

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$

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$

Fig. 1 Framework of EMoEA

Fig. 2 Encoding method

Fig. 3 Example of MIP application

Fig. 4 Turning on/off strategy

Fig. 5 Cluster crossover

Fig. 6 Crossover operators

Fig. 7 Derivation strategy

Fig. 8 Finding critical path

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$

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$

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

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

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

Fig. 11 Convergence curves of three algorithms in two objectives

Fig. 12 Pareto fronts of three algorithms

References 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]	. Survey of Federated Learning Based on Differential Privacy [J]. Journal of Computer Applications, 0, (): 0-0.
[2]	Wenjing YAN, Ruidong WANG, Min ZUO, Qingchuan ZHANG. Recipe recommendation model based on hierarchical learning of flavor embedding heterogeneous graph [J]. Journal of Computer Applications, 2025, 45(6): 1869-1878.
[3]	Longbo YAN, Wentao MAO, Zhihong ZHONG, Lilin FAN. Robust unsupervised multi-task anomaly detection method for defect diagnosis of urban drainage pipe network [J]. Journal of Computer Applications, 2025, 45(6): 1833-1840.
[4]	Lanhao LI, Haojun YAN, Haoyi ZHOU, Qingyun SUN, Jianxin LI. Multi-scale information fusion time series long-term forecasting model based on neural network [J]. Journal of Computer Applications, 2025, 45(6): 1776-1783.
[5]	Yulin HE, Xu LI, Yingting HE, Laizhong CUI, Zhexue HUANG. Subspace Gaussian mixture model clustering ensemble algorithm based on maximum mean discrepancy [J]. Journal of Computer Applications, 2025, 45(6): 1712-1723.
[6]	XIONG Qianlong, QIN Jin. Neural network architecture search algorithm guided by hybrid heuristic information [J]. Journal of Computer Applications, 0, (): 0-0.
[7]	JIANG Yongwei, CHEN Xiaoqing, FU Linjie. Medical image deformable registration model with high frequency holding based on spectrum decomposition [J]. Journal of Computer Applications, 0, (): 0-0.
[8]	. Regional electricity price forecasting method based on Mamba model [J]. Journal of Computer Applications, 0, (): 0-0.
[9]	. Improved Q-learning-based Algorithm for Safe Braking of Intelligent Vehicles in Multiple Scenarios [J]. Journal of Computer Applications, 0, (): 0-0.
[10]	FU Jincheng, YANG Shiyou. Short-term wind power prediction using hybrid model based on Bayesian optimization and feature fusion [J]. Journal of Computer Applications, 0, (): 0-0.
[11]	. Method for entity discovery for non-smart sensors by integrating knowledge graphs and large models [J]. Journal of Computer Applications, 0, (): 0-0.
[12]	Hansong ZHANG, Yichao HE, Fei SUN, Guoxin CHEN, Ju CHEN. Improved ring theory-based evolutionary algorithm with new repair optimization operator for solving multi-dimensional knapsack problem [J]. Journal of Computer Applications, 2025, 45(5): 1595-1604.
[13]	Biqing ZENG, Guangbin ZHONG, James Zhiqing WEN. Few-shot named entity recognition based on decomposed fuzzy span [J]. Journal of Computer Applications, 2025, 45(5): 1504-1510.
[14]	Quan WANG, Qixiang LU, Pei SHI. Multi-graph diffusion attention network for traffic flow prediction [J]. Journal of Computer Applications, 2025, 45(5): 1472-1479.
[15]	Xin CHEN, Zhonghui LIU, Fan MIN. Concept set construction of reduced formal context and its recommendation application [J]. Journal of Computer Applications, 2025, 45(5): 1415-1423.

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 15

References 22

Related Articles 15

Recommended Articles

Metrics