Multi-objective Energy-efficient No-wait Flow Shop Scheduling Based on Hybrid Discrete State Transition Algorithm

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

Abstract

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

CLC Number:

TP301.6

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.

Figures/Tables 22

Table 1

Relevant parameters of the model

模型参数	参数含义
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$	总能源消耗

Table 1

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Table 2

Table 3

Table 4

Fig. 6

Table 5

Comparison of C between HDSTA and ARI

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

Table 5

Table 6

Comparison of C between HDSTA and ARS

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

Table 6

Table 7

Comparison of C between HDSTA and AWD

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

Table 7

Fig. 7

Fig. 8

Fig. 9

Table 8

Comparison of the average value of C index of each algorithm

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

Table 8

Table 9

Table 10

Fig. 10

Fig. 11

Fig. 12

References 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]	Li Feixing, Xing Lining, Zhou Yu. Adversarial Simulation Testing Algorithm for SVM Based on Multi-objective Evolutionary Optimization [J]. Journal of System Simulation, 2024, 36(9): 2016-2031.
[2]	Li Erchao, Zhang Shenghui. UAV Online Track Planning Based on DMOEA-APTC Algorithm [J]. Journal of System Simulation, 2024, 36(9): 2086-2099.
[3]	Zhang Wenqiang, Wang Xiaomeng, Zhang Xiaoxiao, Zhang Guohui. Hybrid Evolutionary Multi-objective Optimization Algorithm for Vehicle Routing Problem with Simultaneous Delivery and Pickup [J]. Journal of System Simulation, 2024, 36(8): 1914-1928.
[4]	Jiang Quan, Wei Jingxuan. Real-time Scheduling Method for Dynamic Flexible Job Shop Scheduling [J]. Journal of System Simulation, 2024, 36(7): 1609-1620.
[5]	Deng Mingjun, Hu Xinxia, Li Xiang, Xu Liping. Arterial Coordination Optimization Method Based on Vehicle Speed Guidance and Inductive Control [J]. Journal of System Simulation, 2024, 36(6): 1309-1321.
[6]	Wen Tingxin, Guan Tingyu. Hybrid Flow Shop Scheduling with Limited Buffers Considering Energy Consumption and Transportation [J]. Journal of System Simulation, 2024, 36(6): 1344-1358.
[7]	Zhao Jia, Lai Zhizhen, Wu Runxiu, Cui Zhihua, Wang Hui. Hierarchical Guided Enhanced Multi-objective Firefly Algorithm [J]. Journal of System Simulation, 2024, 36(5): 1152-1164.
[8]	Wang Yubo, Hu Chengyu, Gong Wenyin. Handling Constrained Multi-objective Optimization Problems Based on Relationship Between Pareto Fronts [J]. Journal of System Simulation, 2024, 36(4): 901-914.
[9]	Zeng Shaoda, Liu Hailin. Planning Modeling and Optimization Algorithm for 5G Indoor Distribution System [J]. Journal of System Simulation, 2024, 36(3): 659-672.
[10]	An Jing, Si Guangya, Zeng Miaoting. Construction of Surrogate Model Driven by Model and Data [J]. Journal of System Simulation, 2024, 36(3): 756-769.
[11]	Wang Hui, Peng Le. Improved Multi-objective Swarm Algorithm to Optimize Wash-out Motion and its Simulation Experiment [J]. Journal of System Simulation, 2024, 36(2): 436-448.
[12]	Xu Yigang, Chen Yong, Wang Chen, Peng Yunxian. Improving NSGA-III Algorithm for Solving High-dimensional Many-objective Green Flexible Job Shop Scheduling Problem [J]. Journal of System Simulation, 2024, 36(10): 2314-2329.
[13]	Li Zhang, Mingling He, Qiushuang Yin, Ning Li, Le'an Yu. Research on Period Emergency Supply Distribution Optimization Under Uncertainty [J]. Journal of System Simulation, 2023, 35(8): 1669-1680.
[14]	Jiaying Yu, Hongli Zhang, Yingchao Dong. Research on No-Wait Flow Shop Scheduling Based on Discrete State Transition Algorithm [J]. Journal of System Simulation, 2023, 35(5): 1034-1045.
[15]	Xu Wang, Weidong Ji, Guohui Zhou, Jiahui Yang. Multi-objective Optimization Algorithm Based on Multi-index Elite Individual Game Mechanism [J]. Journal of System Simulation, 2023, 35(3): 494-514.