Dual Resource Constrained Flexible Job Shop Energy-saving Scheduling Considering Delivery Time

doi:10.16182/j.issn1004731x.joss.21-1306

Abstract

Abstract:

To handle the flexible job shop energy-saving scheduling with machines and workers constraints, on the considering of delivery time, the optimization model of dual resource constrained flexible job shop energy-saving scheduling is established with the goal of minimizing the total earliness and tardiness penalties, and total energy consumption. An improved non-dominated sorting genetic algorithm II(INSGA-II) is proposed. Aiming at the optimized objectives, a three-stage decoding method is designed to gain more feasible solutions. The dynamic adaptive crossover and mutation operators are applied to get more excellent individuals. The crowding distance is improved to obtain a population with better convergence and distribution. The result of comparing INSGA-II with several other multi-objective optimization algorithms, verifies the feasibility and effectiveness of the proposed algorithm.

Key words: dual resource constrains, flexible job shop, earliness/tardiness penalties, energy consumption, INSGA-II(improved non-dominated sorting genetic algorithm II)

CLC Number:

TP18

Hongliang Zhang, Jingru Xu, Bo Tan, Gongjie Xu. Dual Resource Constrained Flexible Job Shop Energy-saving Scheduling Considering Delivery Time[J]. Journal of System Simulation, 2023, 35(4): 734-746.

Figures/Tables 16

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Table 1

Parameters setting of INSGA-II and comparison algorithms

参数	INSGA-II	NSGA-II	SPEA2	Jaya
选择算子	锦标赛选择	锦标赛选择	锦标赛选择	锦标赛选择
交叉概率	$p c = 0.8 × (1 - i t / i t m a x)$	0.8	0.8	—
变异概率	$p m = h 1 + h 2 × (p s - N l / p s)$	0.2	0.2	—

Table 1

Table 2

Parameters level table

参数水平	it_max	n_pop
1	$2 × m × w$	50
2	$3 × m × w$	100
3	$4 × m × w$	150
4	$5 × m × w$	200

Table 2

Table 3

Table 4

Fig. 8

Table 5

Table 6

Average SC values of dominance relationship between algorithms

算例	$S C (A, B)$	$S C (B, A)$	$S C (A, C)$	$S C (C, A)$	$S C (A, D)$	$S C (D, A)$
DSP-DT01	0.798	0.055	0.500	0.215	0.712	0.056
DSP-DT02	1.000	0	0.800	0.101	1.000	0
DSP-DT03	0.900	0.090	0.710	0.129	0.800	0.056
DSP-DT04	1.000	0	1.000	0	1.000	0
DSP-DT05	1.000	0	1.000	0	1.000	0
DSP-DT06	1.000	0	1.000	0	1.000	0
DSP-DT07	0.900	0.100	0.600	0.252	0.700	0.202
DSP-DT08	1.000	0	1.000	0	0.950	0.028
DSP-DT09	0.400	0.333	0.800	0.037	0.652	0.027
DSP-DT10	0.702	0.155	0.704	0.150	1.000	0
DSP-DT11	0.697	0.194	0.570	0.194	0.906	0.048
DSP-DT12	0.700	0.213	0.700	0.046	0.702	0.149
DSP-DT13	0.608	0.238	0.690	0.173	0.999	0.001
DSP-DT14	0.550	0.245	0.500	0.403	1.000	0
DSP-DT15	1.000	0	0.776	0.081	0.844	0.078
DSP-DT16	1.000	0	0.900	0.003	0.948	0.046

Table 6

Fig. 9

Fig. 10

References 33

1	International Energy Agency: World Energy Outlook 2021 [R/OL]. (2021-10-13) [2021-10-25]. .
2	段建国, 李豪晨, 张青雷. 面向绿色制造的半组合式船用曲轴结构件生产车间多目标调度优化[J]. 计算机集成制造系统, 2021, 27(6): 1714-1727.
	Duan Jianguo, Li Haochen, Zhang Qinglei. Green Manufacturing-oriented Multi-objective Scheduling Optimization for Half Built-up Marine Crank Shaft Component Workshop[J]. Computer Integrated Manufacturing Systems, 2021, 27(6): 1714-1727.
3	李聪波, 王睿, 寇阳, 等. 考虑设备预维护的柔性作业车间调度节能优化方法[J]. 机械工程学报, 2021, 57(10): 220-230.
	Li Congbo, Wang Rui, Kou Yang, et al. An Energy Saving Optimization Method of Flexible Job Shop Scheduling Considering Preventive Maintenance[J]. Journal of Mechanical Engineering, 2021, 57(10): 220-230.
4	魏鑫, 张泽群, 唐敦兵, 等. 面向节能的导弹结构件混线生产作业车间多目标调度研究[J]. 机械工程学报, 2018, 54(9): 45-54.
	Wei Xin, Zhang Zequn, Tang Dunbing, et al. Energy-saving Oriented Multi-objective Shop Floor Scheduling for Mixed-line Production of Missile Components[J]. Journal of Mechanical Engineering, 2018, 54(9): 45-54.
5	陈超, 王艳, 严大虎, 等. 面向能耗的柔性作业车间动态调度研究[J]. 系统仿真学报, 2017, 29(9): 2168-2174, 2181.
	Chen Chao, Wang Yan, Yan Dahu, et al. Research on Dynamic Flexible Job Shop Scheduling Problem for Energy Consumption[J]. Journal of System Simulation, 2017, 29(9): 2168-2174, 2181.
6	Jiang T H, Zhu H Q, Deng G L. Improved African Buffalo Optimization Algorithm for the Green Flexible Job Shop Scheduling Problem Considering Energy Consumption[J]. Journal of Intelligent & Fuzzy Systems(S1064-1246), 2020, 38(4): 4573-4589.
7	朱光宇, 徐文婕. 考虑能耗与质量的机床构件生产线多目标柔性作业车间调度方法[J]. 控制与决策, 2019, 34(2): 252-260.
	Zhu Guangyu, Xu Wenjie. Multi-objective Flexible Job Shop Scheduling Method for Machine Tool Component Production Line Considering Energy Consumption and Quality[J]. Control and Decision, 2019, 34(2): 252-260.
8	Nelson R T. Labor and Machine Limited Production Systems[J]. Management Science(S0025-1909), 1967, 13(9): 648-671.
9	郭鹏, 赵文超, 雷坤. 基于改进Jaya算法的双资源约束柔性作业车间优化调度[J]. 吉林大学学报(工学版), 2021, 65: 1-11.
	Guo Peng, Zhao Wenchao, Lei Kun. Dual-resource Constrainted Flexible Job Shop Optimal Scheduling Based on an Improved Jaya Algorithm[J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 65: 1-11.
10	Renna P, Thurer M, Stevenson M. A Game Theory Model Based on Gale-shapley for Dual-resource Constrained (DRC) Flexible Job Shop Scheduling[J]. International Journal of Industrial Engineering Computations(S1923-2926), 2020, 11(2): 173-184.
11	Zhu H, Deng Q W, Zhang L K, et al. Low Carbon Flexible Job Shop Scheduling Problem Considering Worker Learning Using a Memetic Algorithm[J]. Optimization and Engineering(S1389-4420), 2020, 21(4): 1691-1716.
12	Meng L, Zhang C, Zhang B, et al. Mathematical Modeling and Optimization of Energy-conscious Flexible Job Shop Scheduling Problem with Worker Flexibility[J]. IEEE Access(S2169-3536), 2019, 7: 68043-68059.
13	Gong G, Deng Q, Gong X, et al. A New Double Flexible Job-shop Scheduling Problem Integrating Processing Time, Green Production, and Human Factor Indicators[J]. Journal of Cleaner Production(S0959-6526), 2018, 174: 560-576.
14	Gao K Z, Suganthan P N, Pan Q K, et al. Discrete Harmony Search Algorithm for Flexible Job Shop Scheduling Problem with Multiple Objectives[J]. Journal of Intelligent Manufacturing(S0956-5515), 2016, 27(2): 363-374.
15	Zhang F F, Mei Y, Nguyen S, et al. Surrogate-assisted Evolutionary Multitask Genetic Programming for Dynamic Flexible Job Shop Scheduling[J]. IEEE Transactions on Evolutionary Computation(S1089-778X), 2021, 25(4): 651-665.
16	Piroozfard H, Wong K Y, Wong W P. Minimizing Total Carbon Footprint and Total Late Work Criterion in Flexible Job Shop Scheduling by Using an Improved Multi-objective Genetic Algorithm[J]. Resources Conservation and Recycling(S0921-3449), 2018, 128: 267-283.
17	姜天华, 邓冠龙, 朱惠琦. 离散猫群优化算法求解带交货期的FJSP问题[J]. 控制与决策, 2020, 35(1): 161-168.
	Jiang Tianhua, Deng Guanlong, Zhu Huiqi. Discrete Cat Swarm Optimization Algorithm for Solving the FJSP with Due Date[J]. Control and Decision, 2020, 35(1): 161-168.
18	关叶青, 朱颖, 谢乃明. 考虑多成本约束的柔性作业车间制造资源动态分配模型[J]. 控制与决策, 2018, 33(11): 2037-2044.
	Guan Yeqing, Zhu Ying, Xie Naiming. Dynamic Allocation Model of Manufacturing Resources in Flexible Job Shop Considering Multi-cost Constraints[J]. Control and Decision, 2018, 33(11): 2037-2044.
19	李兢尧, 黄媛, 王军强. 基于压缩时窗的双资源约束作业车间调度策略[J]. 计算机集成制造系统, 2016, 22(12): 2827-2835.
	Li Jingyao, Huang Yuan, Wang Junqiang. Scheduling Strategy of Dual Resource Constrained Job Shop Based on Compressed Time Window[J]. Computer Integrated Manufacturing Systems, 2016, 22(12): 2827-2835.
20	Andrade-Pineda J L, Canca D, Gonzalez-R P L, et al. Scheduling a Dual-resource Flexible Job Shop with Makespan and Due Date-related Criteria[J]. Annals of Operations Research(S0254-5330), 2020, 291(1/2): 5-35.
21	Zhang G, Gao L, Shi Y. An Effective Genetic Algorithm for the Flexible Job-shop Scheduling Problem[J]. Expert Systems with Applications(S0957-4174), 2011, 38(4): 3563-3573.
22	胡成玉, 余果, 颜雪松, 等. 基于改进多目标优化算法的分布式数据中心负载调度[J]. 控制与决策, 2021, 36(1): 159-165.
	Hu Chengyu, Yu Guo, Yan Xuesong, et al. Multi-objective Optimization of Energy and Performance Management in Distributed Data Centers[J]. Control and Decision, 2021, 36(1): 159-165.
23	Dai M, Tang D, Giret A, et al. Multi-objective Optimization for Energy-efficient Flexible Job Shop Scheduling Problem with Transportation Constraints[J]. Robotics and Computer Integrated Manufacturing(S0736-5845), 2019, 59: 143-157.
24	Zhang J, Wang W, Xu X. A Hybrid Discrete Particle Swarm Optimization for Dual-resource Constrained Job Shop Scheduling with Resource Flexibility[J]. Journal of Intelligent Manufacturing(S0956-5515), 2017, 28(8): 1961-1972.
25	Wei F F, Cao C Y, Zhang H P. An Improved Genetic Algorithm for Resource-constrained Flexible Job-shop Scheduling[J]. International Journal of Simulation Modelling(S1726-4529), 2021, 20(1): 201-211.
26	Wang X J, Gao L, Zhang C Y, et al. A Multi-objective Genetic Algorithm Based on Immune and Entropy Principle for Flexible Job-shop Scheduling Problem[J]. International Journal of Advanced Manufacturing Technology(S0268-3768), 2010, 51(5-8): 757-767.
27	鞠录岩, 杨建军, 张建兵, 等. 改进NSGA算法求解多目标柔性车间作业调度问题[J]. 计算机工程与应用, 2019, 55(13): 260-265, 270.
	Ju Luyan, Yang Jianjun, Zhang Jianbing, et al. Improved NSGA for Multi-objective Flexible Job-shop Scheduling Problem[J]. Computer Engineering and Applications, 2019, 55(13): 260-265, 270.
28	杨宏安, 王周锋, 吕阳阳, 等. 工序加工时间不确定条件下作业车间调度问题的区间数求解方法[J]. 计算机集成制造系统, 2014, 20(9): 2231-2240.
	Yang Hongan, Wang Zhoufeng, Lu Yangyang, et al. Interval Number Solving Method for Job-shop Scheduling Problem with Processing Time Variability[J]. Computer Integrated Manufacturing Systems, 2014, 20(9): 2231-2240.
29	Na H, Park J. Multi-level Job Scheduling in a Flexible Job Shop Environment[J]. International Journal of Production Research(S0020-7543), 2014, 52(13): 3877-3887.
30	肖华军. 考虑能效的双资源柔性作业车间调度问题研究[D]. 武汉: 华中科技大学, 2018.
	Xiao Huajun. Research on Dual Resource Constrained Flexible Job Shop Scheduling Problem with Energy-efficient[D]. Wuhan: Huazhong University of Science and Technology, 2018.
31	Czyzzak P, Jaszkiewicz A. Pareto Simulated Annealing-A Metaheuristic Technique for Multiple-objective Combinatorial Optimization[J]. Journal of Multi-criteria Decision Analysis(S1099-1360), 1998, 7(1): 34-47.
32	肖世昌, 吴自高, 孙树栋, 等. 双资源约束的鲁棒Job Shop调度问题研究[J]. 机械工程学报, 2021, 57(4): 227-239.
	Xiao Shichang, Wu Zigao, Sun Shudong, et al. Research on the Dual-resource Constrainted Robust Job Shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2021, 57(4): 227-239.
33	宋存利. 求解多目标混合流水车间调度的改进NSGAII算法[J]. 计算机集成制造系统, 2020, 26: 1-19.
	Song Cunli. An Improved NSGAII Algorithm for Hybrid Flow Shop Scheduling Problem with Multi-objective[J]. Computer Integrated Manufacturing Systems, 2020, 26: 1-19.

参数组合	it_max	n_pop	平均IGD
1	1	1	570.892
2	1	2	943.269
3	1	3	791.291
4	1	4	949.525
5	2	1	645.158
6	2	2	364.970
7	2	3	179.257
8	2	4	536.350
9	3	1	283.331
10	3	2	685.949
11	3	3	779.737
12	3	4	1 201.793
13	4	1	822.474
14	4	2	150.880
15	4	3	630.113
16	4	4	471.710

水平	it_max	n_pop
等级	1	2
1	813.744	580.464
2	431.434	536.267
3	737.703	595.099
4	518.794	789.844
极差	382.310	253.577

算例	INSGA-II	NSGA-II	SPEA2	Jaya	算例	INSGA-II	NSGA-II	SPEA2	Jaya
DSP-DT01	916.326	644.115	1 395.033	1 303.204	DSP-DT09	534.298	5 778.712	5 520.644	6 734.012
DSP-DT02	621.514	502.095	1 538.221	945.809	DSP-DT10	612.453	8 843.959	4 764.178	9 082.816
DSP-DT03	586.896	1 260.381	2 051.342	2 129.274	DSP-DT11	100.955	228.609	394.438	600.947
DSP-DT04	793.655	1 636.360	2 372.599	1 711.077	DSP-DT12	24.040	438.651	297.930	819.338
DSP-DT05	869.020	1 266.660	2 061.577	2 078.353	DSP-DT13	0	4 489.957	3 360.143	6 169.582
DSP-DT06	808.923	1 359.701	1 968.949	2 055.113	DSP-DT14	0	1 070.113	625.553	1 559.655
DSP-DT07	2 747.832	4 560.563	3 457.670	4 886.967	DSP-DT15	524.124	945.546	870.706	1 031.969
DSP-DT08	1 370.674	2 803.459	3 032.543	3 115.835	DSP-DT16	20.152	4 133.212	1 856.580	3 637.362

[1]	Hongcai Ouyang, Dinghui Wu, Junyan Fan, Jing Wang. Multi-media Energy Planning Optimization of Steel Based on Improved MOEA/D [J]. Journal of System Simulation, 2023, 35(3): 568-578.
[2]	Sen Zhang, Mengyan Zhang, Jingping Shao, Jiexin Pu. Multi-UAVs 3D Path Planning Method Based on Random Strategy Search [J]. Journal of System Simulation, 2022, 34(6): 1286-1295.
[3]	Yanqin Long, Guifang Qiao, Guangming Song, Ying Zhang, Linlin Cheng. Motion Simulation and Performance Analysis of 2D Variable Stiffness Snake-like Robot [J]. Journal of System Simulation, 2022, 34(4): 759-767.
[4]	Kui Chen, Li Bi, Wenya Wang. Research on Integrated Scheduling of AGV and Machine in Flexible Job Shop [J]. Journal of System Simulation, 2022, 34(3): 461-469.
[5]	Zi'an Zhao, Hong Zhou, Yingjian Lei. Modeling and Optimization for Manufacturing Cell Scheduling Based on Improved Wolf Pack Algorithm and Simulation [J]. Journal of System Simulation, 2022, 34(2): 201-211.
[6]	Yan Bai, Lulu Wu, Yin'e He, Yuying Wang. Energy Consumption Prediction for Air-conditioning System Based on Dynamic Temperature Control [J]. Journal of System Simulation, 2022, 34(2): 366-375.
[7]	Ningke Sun, Yan Wang, Zhicheng Ji. Anomaly Detection Method of Electrical Power Consumption Based on Deep Autoencoder [J]. Journal of System Simulation, 2022, 34(12): 2557-2565.
[8]	Hongliang Zhang, Renman Ding, Gongjie Xu. Energy-Efficient Scheduling of Multi-objective Flexible Job Shop Considering Interval Processing Time [J]. Journal of System Simulation, 2022, 34(09): 1976-1987.
[9]	Hu Rong, Dong Yuming, Qian Bin. Pathfinder Algorithm for Green Pipeline Scheduling with Limited Buffers [J]. Journal of System Simulation, 2021, 33(6): 1384-1396.
[10]	Sun Weiqing, Song He, Han Dong, Tian Kunpeng. Deep Peak-shaving Transformation Planning of Thermal Power Units Based on Approximate Dynamic Programming [J]. Journal of System Simulation, 2021, 33(6): 1415-1426.
[11]	Chen Kui, Bi Li. Research on FJSP of Improved Particle Swarm Optimization Algorithm Considering Transportation Time [J]. Journal of System Simulation, 2021, 33(4): 845-853.
[12]	Li Fei, Su Zhong. Intelligent Control of Wastewater Treatment Processes Based on Adaptive Immune Optimization [J]. Journal of System Simulation, 2021, 33(12): 3012-3020.
[13]	Zhang Xiang, Wang Yan, Ji Zhicheng. Research on Dynamic Flexible Job Shop Scheduling Problem Based on Dynamic Interaction Layer [J]. Journal of System Simulation, 2020, 32(11): 2129-2137.
[14]	Li Junxuan, Wang Yan, Ji Zhicheng. Research on Fuzzy Flexible Job Shop Scheduling Problem Based on Hybrid QPSO [J]. Journal of System Simulation, 2020, 32(10): 2010-2021.
[15]	Meng Qinglong, Zhang Zhibo, Xiong Cheng. Simulation Research on Operation Effect of VAV Air-conditioning System with Variable Water Temperature Strategy [J]. Journal of System Simulation, 2019, 31(8): 1617-1626.