考虑交货期的双资源柔性作业车间节能调度

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

摘要/Abstract

摘要：

为解决含有机器和工人双资源约束的柔性作业车间节能调度问题，在考虑交货期的基础上，建立了以总提前和拖期惩罚值及总能耗最小为目标的双资源柔性作业车间节能调度模型。提出了一种改进的非支配排序遗传算法(improved non-dominated sorting genetic algorithm II，INSGA-II)进行求解。针对所优化的目标，设计了一种三阶段解码方法以获得高质量的可行解；利用动态自适应交叉和变异算子以获得更多优良个体；改进拥挤距离以获得收敛性和分布性更优的种群。将INSGA-II与多种多目标优化算法进行对比分析，实验结果表明所提算法可行且有效。

关键词: 双资源约束, 柔性作业车间, 提前/拖期惩罚, 能耗, INSGA-II(improved non-dominated sorting genetic algorithm II)

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)

中图分类号:

TP18

张洪亮, 徐静茹, 谈波, 徐公杰. 考虑交货期的双资源柔性作业车间节能调度[J]. 系统仿真学报, 2023, 35(4): 734-746.

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.

图/表 16

图1

图2

图3

图4

图5

图6

图7

表1

INSGA-II及对比算法的参数设置

参数	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	—

表1

表2

参数水平表

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

表2

表3

表4

图8

表5

表6

算法支配关系的平均SC值

算例	$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

表6

图9

图10

参考文献 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]	张朝阳, 徐莉萍, 李健, 赵义豪, 何奎. 基于改进狼群算法的柔性作业车间调度研究[J]. 系统仿真学报, 2023, 35(3): 534-543.
[2]	欧阳洪才, 吴定会, 范俊岩, 汪晶. 基于改进MOEA/D的钢铁多介质能源计划优化[J]. 系统仿真学报, 2023, 35(3): 568-578.
[3]	张森, 张孟炎, 邵敬平, 普杰信. 基于随机策略搜索的多机三维路径规划方法[J]. 系统仿真学报, 2022, 34(6): 1286-1295.
[4]	龙艳琴, 乔贵方, 宋光明, 张颖, 程琳琳. 二维变刚度蛇形机器人的运动仿真与性能分析[J]. 系统仿真学报, 2022, 34(4): 759-767.
[5]	陈魁, 毕利, 王文雅. 柔性作业车间AGV与机器双资源集成调度研究[J]. 系统仿真学报, 2022, 34(3): 461-469.
[6]	白燕, 武璐璐, 贺引娥, 王玉英. 基于动态温度调控的空调系统能耗预测[J]. 系统仿真学报, 2022, 34(2): 366-375.
[7]	孙宁可, 王艳, 纪志成. 基于深度自编码器的电力能耗异常检测方法[J]. 系统仿真学报, 2022, 34(12): 2557-2565.
[8]	张洪亮, 丁仁曼, 徐公杰. 考虑区间工时的多目标柔性作业车间节能调度[J]. 系统仿真学报, 2022, 34(09): 1976-1987.
[9]	胡蓉, 董钰明, 钱斌. 基于探路者算法的绿色有限缓冲区流水线调度[J]. 系统仿真学报, 2021, 33(6): 1384-1396.
[10]	陈魁, 毕利. 改进粒子群算法在考虑运输时间下的FJSP研究[J]. 系统仿真学报, 2021, 33(4): 845-853.
[11]	李霏, 苏中. 基于自适应免疫优化的污水处理过程控制[J]. 系统仿真学报, 2021, 33(12): 3012-3020.
[12]	尤一琛, 王艳, 纪志成. 基于博弈论的柔性作业车间动态调度研究[J]. 系统仿真学报, 2021, 33(11): 2579-2588.
[13]	张新艳, 周雨晴. 多载量小车节能调度的多目标动态规划算法[J]. 系统仿真学报, 2020, 32(4): 612-619.
[14]	丁宇, 王艳, 纪志成. 柔性作业车间生产与能耗协同优化决策方法[J]. 系统仿真学报, 2020, 32(12): 2426-2437.
[15]	王艳, 丁宇. 动态柔性作业车间优化调度与决策方法[J]. 系统仿真学报, 2020, 32(11): 2073-2083.