基于混合离散状态转移算法的多目标节能无等待流水车间调度

doi:10.16182/j.issn1004731x.joss.23-0743

摘要/Abstract

摘要：

针对以完工时间和总能耗为目标的节能无等待流水车间调度问题(energy-efficient no-wait flow shop scheduling problem，EENWFSP)，设计一种混合离散状态转移算法(hybrid discrete state transition algorithm，HDSTA)进行求解。根据问题特性设计工序和速度矩阵的编码方式，采用启发式算法获得优质的初始解。根据EENWFSP性质，对4个离散操作算子进行任务分配，将嵌入二次状态转移的交换、移动、对称算子用于工序优化，替换算子用于机器速度优化，并在替换算子中嵌入基于关键路径的速度替换策略。设计了一种改进的破坏重构操作，用于进一步提高Pareto解的质量。通过与4种算法在测试实例上的实验结果分析，表明HDSTA在解决EENWFSP时具有较强优势。

关键词: 无等待流水车间, 节能调度, 状态转移算法, 总能量消耗, 最大完工时间, 多目标优化

Abstract:

A hybrid discrete state transition algorithm (HDSTA) is designed to solve the energy-efficient no-wait flow shop scheduling problem (EENWFSP) minimizing makespan and total energy consumption. According to the characteristics of the problem, the coding method of job sequence and speed matrix is designed, and the heuristic algorithm is used to obtain the high-quality initial solution. According to the properties of EENWFSP, solving and allocating four discrete operators. The swap, shift and symmetry operators are embedded in secondary state transition are used for job sequence optimization, and the substitute operators are used for machine speed optimization. The speed substitute strategy based on critical path is embedded in the substitute operators. An improved destructive reconstruction operation is designed to further improve the quality of Pareto solution. Experimental results of four algorithms on test cases show that HDSTA has strong advantages in solving EENWFSP.

Key words: no-wait flow shop scheduling problem, energy-efficient scheduling, state transition algorithm, total energy consumption, makespan, multi-objective optimization

中图分类号:

TP301.6

王聪,余佳英,张宏立 . 基于混合离散状态转移算法的多目标节能无等待流水车间调度[J]. 系统仿真学报, 2024, 36(10): 2345-2358.

Wang Cong,Yu Jiaying,Zhang Hongli . Multi-objective Energy-efficient No-wait Flow Shop Scheduling Based on Hybrid Discrete State Transition Algorithm[J]. Journal of System Simulation, 2024, 36(10): 2345-2358.

图/表 22

表1

模型相关参数

模型参数	参数含义
N	工件总数
M	机器总数
$p j, i$	工件j在机器i上的标准加工时间
$v l$	速度等级l的速度系数， $l ∈ L$ ， $L = {1,2, 3}$
$φ i$	处于待机模式的机器i单位时间的能量消耗， $i ∈ M$
$τ i, l$	机器i以速度l运行时单位时间的能量消耗， $i ∈ M$
D	一个极大正数
$y j, i, l$	0~1变量，若机器i上以速度l加工工件j时为1，否则为0
$x j, k$	0~1变量，若工件j在工件k之前加工时为1，否则为0
$C j, i$	工件j在机器i的完工时间
$θ i$	机器i上的空闲时间
$t m a x$	最大完工时间
$T E C$	总能源消耗

表1

图1

图2

图3

图4

图5

表2

表3

表4

图6

表5

HDSTA和ARI的C指标对比

算例	$C (H D S T A, A R I)$	$C (A R I, H D S T A)$	p
20×5	0.770	0.091	0
20×10	0.761	0.010	0
20×20	0.668	0.204	0.002
50×5	0.708	0.102	0
50×10	0.467	0.118	0.005
50×20	0.828	0.248	0.001
100×5	0.460	0.106	0.006
100×10	0.261	0.086	0.018
100×20	0.608	0.148	0.004
200×10	0.629	0.071	0
200×20	0.776	0.134	0.001

表5

表6

HDSTA和ARS的C指标对比

算例	$C (H D S T A, A R S)$	$C (H D S T A, A R S)$	p
20×5	0.820	0.084	0
20×10	0.864	0.052	0
20×20	0.835	0.060	0
50×5	0.936	0.176	0
50×10	0.872	0.128	0.001
50×20	0.896	0.052	0
100×5	0.704	0.056	0
100×10	0.732	0.128	0.001
100×20	0.850	0.179	0
200×10	0.772	0.072	0
200×20	0.883	0.074	0

表6

表7

HDSTA和AWD的C指标对比

算例	$C (H D S T A, A W D)$	$C (H D S T A, A W D)$	p
20×5	0.764	0.081	0.001
20×10	0.840	0.000	0.001
20×20	0.913	0.007	0
50×5	0.852	0.062	0
50×10	0.608	0.136	0.001
50×20	0.820	0.072	0
100×5	0.850	0.064	0
100×10	0.573	0.233	0.034
100×20	0.632	0.041	0
200×10	0.750	0.171	0.001
200×20	0.816	0.113	0

表7

图7

图8

图9

表8

各算法的C指标平均值对比

算例	$A 1$	$A 2$	$A 3$	$A 4$
平均	0.99	0.70	0.63	0.99
20×5	1.00	0.98	0.87	0.99
20×10	1.00	0.83	0.76	1.00
20×20	1.00	0.63	0.77	1.00
50×5	1.00	0.71	0.56	1.00
50×10	1.00	0.71	0.48	0.96
50×20	1.00	0.63	0.49	1.00
100×5	1.00	0.58	0.53	0.95
100×10	1.00	0.67	0.45	1.00
100×20	1.00	0.65	0.46	1.00
200×10	0.96	0.55	0.84	1.00
200×20	0.98	0.71	0.72	1.00

表8

表9

表10

图10

图11

图12

参考文献 26

1	Gahm Christian, Denz Florian, Dirr Martin, et al. Energy-efficient Scheduling in Manufacturing Companies: A Review and Research Framework[J]. European Journal of Operational Research, 2016, 248(3): 744-757.
2	王凌, 王晶晶, 吴楚格. 绿色车间调度优化研究进展[J]. 控制与决策, 2018, 33(3): 385-391.
	Wang Ling, Wang Jingjing, Wu Chuge. Advances in Green Shop Scheduling and Optimization[J]. Control and Decision, 2018, 33(3): 385-391.
3	Lei Deming, Gao Liang, Zheng Youlian. A Novel Teaching-learning-based Optimization Algorithm for Energy-efficient Scheduling in Hybrid Flow Shop[J]. IEEE Transactions on Engineering Management, 2018, 65(2): 330-340.
4	Gu Wenbin, Li Zhuo, Dai Min, et al. An Energy-efficient Multi-objective Permutation Flow Shop Scheduling Problem Using an Improved Hybrid Cuckoo Search Algorithm[J]. Advances in Mechanical Engineering, 2021, 13(6): 16878140211023603.
5	任彩乐, 杨旭东, 张超勇, 等. 面向节能的混合流水车间调度问题建模与优化[J]. 计算机集成制造系统, 2019, 25(8): 1965-1980.
	Ren Caile, Yang Xudong, Zhang Chaoyong, et al. Modeling and Optimization for Energy-efficient Hybrid Flow-shop Scheduling Problem[J]. Computer Integrated Manufacturing Systems, 2019, 25(8): 1965-1980.
6	艾子义, 雷德明. 基于新型蛙跳算法的低碳柔性作业车间调度[J]. 控制理论与应用, 2017, 34(10): 1361-1368.
	Ai Ziyi, Lei Deming. A Novel Shuffled Frog Leaping Algorithm for Low Carbon Flexible Job Shop Scheduling[J]. Control Theory & Applications, 2017, 34(10): 1361-1368.
7	Tang Dunbing, Dai Min, Salido Miguel A, et al. Energy-efficient Dynamic Scheduling for a Flexible Flow Shop Using an Improved Particle Swarm Optimization[J]. Computers in Industry, 2016, 81: 82-95.
8	Shao Weishi, Pi Dechang, Shao Zhongshi. An Extended Teaching-learning Based Optimization Algorithm for Solving No-wait Flow Shop Scheduling Problem[J]. Applied Soft Computing, 2017, 61: 193-210.
9	Zhao Fuqing, Liu Huan, Zhang Yi, et al. A Discrete Water Wave Optimization Algorithm for No-wait Flow Shop Scheduling Problem[J]. Expert Systems with Applications, 2018, 91: 347-363.
10	Lin S W, Ying K C. Optimization of Makespan for No-wait Flowshop Scheduling Problems Using Efficient Matheuristics[J]. Omega, 2016, 64: 115-125.
11	Benini L, Bogliolo A, De Micheli G. A Survey of Design Techniques for System-level Dynamic Power Management[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2000, 8(3): 299-316.
12	Liu C H, Huang D H. Reduction of Power Consumption and Carbon Footprints by Applying Multi-objective Optimisation via Genetic Algorithms[J]. International Journal of Production Research, 2014, 52(2): 337-352.
13	Ding Jianya, Song Shiji, Wu Cheng. Carbon-efficient Scheduling of Flow Shops by Multi-objective Optimization[J]. European Journal of Operational Research, 2016, 248(3): 758-771.
14	Jiang Enda, Wang Ling. An Improved Multi-objective Evolutionary Algorithm Based on Decomposition for Energy-efficient Permutation Flow Shop Scheduling Problem with Sequence-dependent Setup Time[J]. International Journal of Production Research, 2019, 57(6): 1756-1771.
15	Fatih Tasgetiren M, Yüksel Damla, Gao Liang, et al. A Discrete Artificial Bee Colony Algorithm for the Energy-efficient No-wait Flowshop Scheduling Problem[J]. Procedia Manufacturing, 2019, 39: 1223-1231.
16	Wang Jingjing, Wang Ling. A Knowledge-based Cooperative Algorithm for Energy-efficient Scheduling of Distributed Flow-shop[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2020, 50(5): 1805-1819.
17	潘子肖, 雷德明. 基于问题性质的分布式低碳并行机调度算法研究[J]. 自动化学报, 2020, 46(11): 2427-2438.
	Pan Zixiao, Lei Deming. Research on Property-based Distributed Low Carbon Parallel Machines Scheduling Algorithm[J]. Acta Automatica Sinica, 2020, 46(11): 2427-2438.
18	Zhou Xiaojun, Yang Chunhua, Gui Weihua. State Transition Algorithm[J]. Journal of Industrial and Management Optimization, 2012, 8(4): 1039-1056.
19	阳春华, 唐小林, 周晓君, 等. 一种求解旅行商问题的离散状态转移算法[J]. 控制理论与应用, 2013, 30(8): 1040-1046.
	Yang Chunhua, Tang Xiaolin, Zhou Xiaojun, et al. A Discrete State Transition Algorithm for Traveling Salesman Problem[J]. Control Theory & Applications, 2013, 30(8): 1040-1046.
20	Zhou Xiaojun, Gao D Y, Simpson A R. Optimal Design of Water Distribution Networks by a Discrete State Transition Algorithm[J]. Engineering Optimization, 2016, 48(4): 603-628.
21	董天雪, 阳春华, 周晓君, 等. 一种求解企业员工指派问题的离散状态转移算法[J]. 控制理论与应用, 2016, 33(10): 1378-1388.
	Dong Tianxue, Yang Chunhua, Zhou Xiaojun, et al. A Novel Discrete State Transition Algorithm for Staff Assignment Problem[J]. Control Theory & Applications, 2016, 33(10): 1378-1388.
22	Gui Lin, Gao Liang, Li Xinyu. Anomalies in Special Permutation Flow Shop Scheduling Problems[J]. Chinese Journal of Mechanical Engineering, 2020, 33(1): 46.
23	Mansouri S A, Aktas E, Besikci Umut. Green Scheduling of a Two-machine Flowshop: Trade-off Between Makespan and Energy Consumption[J]. European Journal of Operational Research, 2016, 248(3): 772-788.
24	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.
25	钟祾充, 钱斌, 胡蓉, 等. 混合布谷鸟算法求解绿色流水车间调度问题[J]. 中国机械工程, 2018, 29(22): 2674-2681.
	Zhong Lingchong, Qian Bin, Hu Rong, et al. HCS Algorithm for Multi-objective Flow Shop Scheduling Problems with Energy Consumption[J]. China Mechanical Engineering, 2018, 29(22): 2674-2681.
26	Öztop Hande, Fatih Tasgetiren M, Deniz Türsel Eliiyi, et al. Green Permutation Flowshop Scheduling: A Trade-off-between Energy Consumption and Total Flow Time[C]//Intelligent Computing Methodologies. Cham: Springer International Publishing, 2018: 753-759.

参数组合	水平				RV/%
参数组合	NP	d	K	SE	RV/%
1	20(1)	2(1)	30(1)	30(1)	8.25
2	20(1)	4(2)	40(2)	60(2)	7.92
3	20(1)	8(3)	50(3)	100(3)	4.95
4	30(2)	2(1)	40(2)	100(3)	15.51
5	30(2)	4(2)	50(3)	30(1)	10.23
6	30(2)	8(3)	30(1)	60(2)	10.23
7	50(3)	2(1)	50(3)	60(2)	19.14
8	50(3)	4(2)	30(1)	100(3)	15.84
9	50(3)	8(3)	40(2)	30(1)	7.92

水平	NP	d	K	SE
1	7.04	14.3	11.44	8.8
2	11.99	11.33	10.45	12.43
3	14.31	7.7	11.44	12.1
极差	7.27	6.6	0.99	3.63
等级	1	2	4	3

算例	HDSTA	HCS	DABC	IG_ALL	NSGA-II
平均	61.48	14.14	23.67	57.48	26.26
20×5	85.20	12.80	18.80	66.60	43.20
20×10	73.80	13.00	34.60	83.60	22.40
20×20	60.00	12.20	35.00	48.60	25.40
50×5	73.00	28.25	36.28	84.25	35.20
50×10	74.60	17.00	25.61	58.02	34.00
50×20	41.00	8.60	15.10	42.20	11.60
100×5	66.40	15.10	17.24	84.80	43.40
100×10	68.70	19.20	9.21	58.20	23.32
100×20	49.80	12.20	12.15	42.20	18.60
200×10	36.20	8.00	37.84	27.00	20.00
200×20	47.60	9.20	18.54	36.80	11.71

算例	HDSTA	HCS	DABC	IG_ALL	NSGA-II
平均	5.77	36.80	25.09	18.14	24.30
20×5	5.99	23.40	15.10	8.40	9.72
20×10	5.72	33.6	24.71	14.29	14.91
20×20	4.99	34.37	32.57	26.96	18.49
50×5	7.04	21.28	31.24	9.31	19.27
50×10	6.07	49.57	32.53	9.78	25.66
50×20	5.12	40.61	17.84	21.13	32.69
100×5	7.60	50.40	31.60	13.58	22.00
100×10	4.32	39.12	14.34	9.65	23.20
100×20	5.05	31.94	24.31	23.40	41.49
200×10	6.63	38.29	16.30	29.62	48.44
200×20	4.93	42.18	35.40	33.45	11.38

[1]	李飞行, 邢立宁, 周宇. 基于多目标演化优化的SVM对抗仿真测试算法[J]. 系统仿真学报, 2024, 36(9): 2016-2031.
[2]	李二超, 张生辉. 基于DMOEA-APTC算法的无人机在线航迹规划[J]. 系统仿真学报, 2024, 36(9): 2086-2099.
[3]	张闻强, 王晓萌, 张晓晓, 张国辉. 集配一体化车辆路径规划的混合进化多目标优化[J]. 系统仿真学报, 2024, 36(8): 1914-1928.
[4]	蒋权, 魏静萱. 用于动态柔性作业车间调度的实时调度方法[J]. 系统仿真学报, 2024, 36(7): 1609-1620.
[5]	邓明君, 胡辛瑕, 李响, 徐丽萍. 基于车速引导和感应控制的干线协调优化方法[J]. 系统仿真学报, 2024, 36(6): 1309-1321.
[6]	温廷新, 关婷誉. 考虑能耗和运输的有限缓冲区混合流水车间调度[J]. 系统仿真学报, 2024, 36(6): 1344-1358.
[7]	赵嘉, 赖智臻, 吴润秀, 崔志华, 王晖. 层级引导的增强型多目标萤火虫算法[J]. 系统仿真学报, 2024, 36(5): 1152-1164.
[8]	王昱博, 胡成玉, 龚文引. 基于帕累托前沿关系求解约束多目标优化问题[J]. 系统仿真学报, 2024, 36(4): 901-914.
[9]	曾少达, 刘海林. 5G室内分布系统规划建模及优化算法[J]. 系统仿真学报, 2024, 36(3): 659-672.
[10]	安靖, 司光亚, 曾妙婷. 模型与数据混合驱动的代理模型构建方法研究[J]. 系统仿真学报, 2024, 36(3): 756-769.
[11]	王辉, 彭乐. 改进多目标蜂群算法优化洗出运动及仿真实验[J]. 系统仿真学报, 2024, 36(2): 436-448.
[12]	徐宜刚, 陈勇, 王宸, 彭运贤. 改进NSGA-III求解高维多目标绿色柔性作业车间调度问题[J]. 系统仿真学报, 2024, 36(10): 2314-2329.
[13]	钟麟, 佟明安, 李盛. 特定多任务下飞机航迹规划研究[J]. 系统仿真学报, 2023, 35(9): 1909-1917.
[14]	张立, 贺明玲, 尹秋霜, 李宁, 余乐安. 不确定条件下多周期应急物资配送优化研究[J]. 系统仿真学报, 2023, 35(8): 1669-1680.
[15]	余佳英, 张宏立, 董颖超. 基于离散状态转移算法的无等待流水车间调度研究[J]. 系统仿真学报, 2023, 35(5): 1034-1045.