Research on No-Wait Flow Shop Scheduling Based on Discrete State Transition Algorithm

doi:10.16182/j.issn1004731x.joss.22-0048

Abstract

Abstract:

In view of the no-wait flow shop problem (NWFSP) widely existing in the manufacturing industry, an improved discrete state transition algorithm (IDSTA) is proposed to solve the problem. The coding mode of the workpiece is designed based on the characteristics of the flow shop scheduling problem (FSSP). The initial solution is constructed by the Nawaz-Enscore-Ham (NEH) method with the standard deviation of the processing time of the workpiece as the priority, and a multi-neighborhood combinatorial search strategy based on insertion and exchange is designed to improve the quality of the initial solution. A discrete state transition algorithm (DSTA) based on group state is proposed, and the search range of the algorithm is expanded by using three discrete operators with quadratic state transition operations. In order to further improve the solution performance of DSTA, a local search method based on Levy flight for damage reconstruction is designed, and the high-quality solution detected by global search is searched carefully. The simulation experiments show that IDSTA can effectively solve the NWFSP.

Key words: no-wait constraints, flow shop scheduling problem (FSSP), discrete state transition algorithm (DSTA), variable neighborhood search, Levy flight

CLC Number:

TP301.6

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.

Figures/Tables 13

Table 1

Fig. 1

Fig. 2

Table 2

Table 3

Table 4

Fig. 3

Table 5

Table 6

Comparison of benchmark test results

测试问题	n,m	C^*	IDSTA			DHK			DPSO			DSTA
测试问题	n,m	C^*	BRE	ARE	WRE	BRE	ARE	WRE	BRE	ARE	WRE	BRE	ARE	WRE
合计			-148.21	-140.80	-132.53	-138.15	-119.11	-98.79	-126.52	-109.72	-90.37	-100.82	-84.52	-70.56
$C a r 1$	11, 5	8 142	0	0	0	0	0	0	0	0.24	0.85	0	0.17	0.72
$C a r 2$	13, 4	8 242	0	0	0	0	0.05	0.17	0	0.30	0.65	0.17	0.17	0.17
$C a r 3$	12, 5	8 866	0	0	0	0	0.09	0.25	0	0.14	0.63	0	0.17	0.27
$C a r 4$	14, 4	9 195	0	0	0	0	0.29	1.13	0	1.83	4.77	3.02	3.02	3.02
$C a r 5$	10, 6	9 159	0	0	0	0	0	0	0	0	0	0	0	0
$C a r 6$	8, 9	9 690	0	0	0	0	0	0	0	0	0	0	0	0
$C a r 7$	7, 7	7 705	0	0	0	0	0	0	0	0	0	0	0	0
$C a r 8$	8, 8	9 372	0	0	0	0	0	0	0	0	0	0	0	0
$R e c 01$	20, 5	1 590	-4.03	-4.03	-4.03	-4.03	-3.89	-3.52	-3.58	-3.44	-2.89	-3.33	-1.13	-0.25
$R e c 03$	20, 5	1 457	-6.59	-6.59	-6.59	-6.59	-5.57	-4.60	-4.80	-4.64	-4.32	-3.57	-2.76	-1.92
$R e c 05$	20, 5	1 637	-7.70	-7.42	-7.21	-7.51	-6.84	-6.29	-7.15	-6.17	-5.62	-6.17	-6.17	-6.17
$R e c 07$	20, 10	2 119	-3.59	-3.57	-3.40	-3.63	-2.94	-2.08	-3.59	-3.20	-2.69	-2.94	-2.03	-2.29
$R e c 09$	20, 10	2 141	-4.62	-4.50	-3.64	-4.62	-4.18	-3.64	-4.11	-3.12	-0.93	-1.17	-0.79	-0.56
$R e c 11$	20, 10	1 946	-3.34	-3.34	-3.34	-3.34	-2.81	-2.42	-3.34	-2.53	-1.54	-1.64	-1.03	-0.36
$R e c 13$	20, 15	2 709	-6.05	-5.93	-5.65	-6.05	-5.36	-4.02	-5.65	-5.27	-4.25	-4.21	-2.81	-0.50
$R e c 15$	20, 15	2 691	-6.02	-6.02	-6.02	-6.02	-5.42	-4.98	-6.02	-5.54	-5.05	-5.43	-5.43	-5.43
$R e c 17$	20, 15	2 740	-5.58	-5.58	-5.58	-5.58	-5.53	-5.47	-5.51	-5.27	-5.04	-3.01	-1.86	-1.71
$R e c 19$	30, 10	3 157	-9.72	-9.28	-9.00	-8.55	-8.08	-7.60	-8.20	-7.79	-7.32	-7.82	-7.03	-6.37
$R e c 21$	30, 10	3 015	-6.24	-5.81	-5.24	-5.67	-5.02	-4.31	-4.88	-4.38	-4.01	-4.11	-4.05	-4.01
$R e c 23$	30, 10	3 030	-10.89	-10.04	-8.81	-10.83	-8.84	-6.93	-8.91	-8.78	-8.12	-7.79	-6.93	-5.61
$R e c 25$	30, 15	3 835	-6.21	-5.80	-5.29	-6.21	-5.59	-4.64	-5.27	-4.60	-4.02	-3.52	-3.34	-3.16
$R e c 27$	30, 15	3 655	-6.13	-5.74	-5.28	-5.64	-4.71	-3.78	-4.49	-3.53	-3.31	-3.94	-3.42	-2.76
$R e c 29$	30, 15	3 583	-7.45	-7.45	-7.45	-7.01	-4.67	-3.38	-6.67	-6.32	-5.97	-6.61	-6.08	-5.94
$R e c 31$	50, 10	4 631	-5.81	-5.25	-4.79	-5.38	-3.67	-2.50	-4.90	-4.29	-3.63	-4.20	-1.03	-0.12
$R e c 33$	50, 10	4 770	-6.00	-4.76	-3.77	-4.61	-4.05	-3.27	-4.23	-3.12	-2.05	-2.96	-2.96	-2.96
$R e c 35$	50, 10	4 718	-5.74	-4.77	-3.84	-5.19	-4.54	-3.88	-4.49	-3.77	-3.18	-4.03	-3.66	-2.08
$R e c 37$	75, 20	8 979	-8.29	-7.57	-7.33	-8.23	-7.16	-4.44	-8.16	-7.48	-6.86	-6.97	-6.80	-6.78
$R e c 39$	75, 20	9 158	-5.46	-5.22	-4.71	-4.83	-4.23	-3.72	-5.57	-5.05	-4.58	-4.46	-3.89	-2.78
$R e c 41$	75, 20	9 344	-7.48	-7.22	-6.93	-7.06	-5.77	-4.98	-6.62	-6.10	-5.57	-5.69	-5.47	-4.66
$H e l 1$	100, 10	780	-6.28	-5.92	-5.64	-6.28	-5.59	-5.13	-6.15	-5.59	-5.26	-4.62	-4.62	-4.62
$H e l 2$	20, 10	189	-8.99	-8.99	-8.99	-5.29	-5.08	-4.76	-4.23	-2.25	-1.06	-5.82	-4.76	-3.70

Table 6

Fig. 4

Fig. 5

Fig. 6

Fig. 7

References 25

1	Chen Y C, Kuo C Y, Shu F L, et al. Minimizing Makespan in Mixed No-wait Flowshops with Sequence-Dependent Setup Times[J]. Computers & Industrial Engineering (S0360-8352), 2019, 130: 338-347.
2	Ying K C, Lin S W. Minimizing Makespan for No-wait Flowshop Scheduling Problems with Setup Times[J]. Computers & Industrial Engineering (S0360-8352), 2018, 121: 73-81.
3	Shao W S, Pi D C, Shao Z S. An Extended Teaching-Learning Based Optimization Algorithm for Solving No-wait Flow Shop Scheduling Problem[J]. Applied Soft Computing (S1568-4946), 2017, 61: 193-210.
4	裴小兵, 赵衡. 基于区块进化算法求解置换流水车间调度问题[J]. 系统仿真学报, 2018, 30(8): 3170-3178.
	Pei Xiaobing, Zhao Heng. Block-based Evolutionary Algorithm for Permutation Flow-shop Scheduling Problem[J]. Journal of System Simulation, 2018, 30(8): 3170-3178.
5	胡蓉, 董钰明, 钱斌. 基于探路者算法的绿色有限缓冲区流水线调度[J]. 系统仿真学报, 2021, 33(6): 1384-1396.
	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.
6	常俊林, 邵惠鹤. 两机零等待流水车间调度问题的启发式算法[J].计算机集成制造系统, 2005, 11(8): 1147-1153, 1162.
	Chang Junling, Shao Huihe. A Heuristic Algorithm for Two-Machine No-wait Flow Shop Scheduling Problem[J]. Computer Integrated Manufacturing Systems, 2005, 11(8): 1147-1153, 1162.
7	王柏琳, 李铁克. 等待时间受限的置换流水车间调度启发式算法[J]. 管理科学学报, 2012, 15(6): 22-32.
	Wang Bolin, Li Tieke. Heuristic Algorithm for Permutation Flow Shop Scheduling with Limited Waiting Time[J]. Journal of Management Science and Engineering, 2012, 15(6): 22-32.
8	宋存利, 刘晓冰, 王伟. 大规模无等待流水调度问题的邻域迭代搜索算法[J]. 控制与决策, 2011, 26(4): 535-539, 547.
	Song Cunli, Liu Xiaobing, Wang Wei. An Iterative Neighborhood Search Algorithm for Large Scale No-wait Flow Shop[J] Control and Decision, 2011, 26(4): 535-539, 547.
9	齐学梅, 王宏涛, 杨洁, 等. 量子萤火虫算法及在无等待流水调度上的应用[J]. 信息与控制, 2016, 45(2): 211-217.
	Qi Xuemei, Wang Hongtao, Yang Jie, et al. Quantum Glowworm Swarm Algorithm and Its Applicationto No-wait Flowshop Scheduling[J]. Information and Control, 2016, 45(2): 211-217.
10	Rani D S, Subrahmanyam N, Sydulu M. A Hybrid Particle Swarm Optimization Algorithm for a No-wait Flow Shop Scheduling Problem with the Total Flow Time[J]. International Journal of Advanced Manufacturing Technology (S0268-3768), 2014, 70(5/8): 1181-1188.
11	Allahverdi A, Aydilek H, Aydilek A. No-wait Flow Shop Scheduling Problem with Two Criteria; Total Tardiness and Makepan[J]. European Journal of Operational Research (S0377-2217), 2018, 269(2): 590-601.
12	Riahi V, Kazemi M. A New Hybrid Ant Colony Algorithm for Scheduling of No-wait Flowshop[J]. Operational Research (S1109-2858), 2018, 18(1): 55-74.
13	裴小兵, 李依臻. 新型混合改进遗传算法求解零等待流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(3): 815-827.
	Pei Xiaobing, Li Yizhen. A New Hybrid Improved Genetic Algorithm for Solving the No-wait Flow Shop Scheduling Problem[J]. Computer Integrated Manufacturing Systems, 2021, 27(3): 815-827.
14	Zhou X J, Yang C H, Gui W H. State Transition Algorithm[J]. Journal of Industrial and Management Optimization (S1547-5816), 2012, 8(4): 1039-1056.
15	Yang C H, Tang X L, Zhou X J, et al. A Discrete State Transition Algorithm for Traveling Salesman Problem[J]. Control Thetory and Applications (S1000-8152), 2013, 30(8): 1040-1046.
16	Zhou X J, Gao D, Simpson A. Optimal Design of Water Distribution Networks by a Discrete State Transition Algorithm[J]. Engineering Optimization (S0305-215X), 2015, 48(4): 1-26.
17	董天雪, 阳春华, 周晓君, 等. 一种求解企业员工指派问题的离散状态转移算法[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 Thetory and Applications, 2016, 33(10): 1378-1388.
18	Shao W, Pi D, Shao Z. An Extended Teaching-Learning Based Optimization Algorithm for Solving No-wait Flow Shop Scheduling Problem[J]. Applied Soft Computing (S1568-4946), 2017, 61: 193-210.
19	Nawaz M, Enscore J, Ham I. A Heuristic Algorithm for the M-machine, N-job Flow-Shop Sequencing Problem[J]. Omega (S0305-0483), 1983, 11(1): 91-95.
20	Gao K Z, Li J Q, Pan Q K. Discrete Harmony Search Algorithm for the No-wait Flow Shop Scheduling Problem with Total Flow Time Criterion[J]. The International Journal of Advanced Manufacturing Technology (S0268-3768), 2011, 56(5): 683-692.
21	Blum C, Roli A. Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison[J]. ACM Computing Surveys (S0360-0300), 2003, 35(3): 268-308.
22	Wang Y M, Li X P, Ruiz R, et al. An Iterated Greedy Heuristic for Mixed No-wait Flowshop Problems[J]. IEEE Transactions on Cybernetics (S2168-2267), 2017, 48(5): 1553-1566.
23	Ding J Y, Chiong R M, Zhang R, et al. An Improved Iterated Greedy Algorithm with a Tabu-Based Reconstruction Strategy for the No-wait Flowshop Scheduling Problem[J]. Applied Soft Computing (S1568-4946), 2015, 30: 604-613.
24	刘长平, 简祯富, 傅文翰. 求解零等待流水线调度问题的离散磷虾群算法[J]. 系统仿真学报, 2020, 32(6): 1051-1059.
	Liu Changping, Jian Zhenfu, Fu Wenhan. A Discrete Krill Herd Algorithm for the No-wait Flow Shop Scheduling Problem[J]. Journal of System Simulation, 2020, 32(6): 1051-1059.
25	Pan Q K, Tasgetiren M, Liang Y C. A Discrete Particle Swarm Optimization Algorithm for the No-wait Flowshop Scheduling Problem[J]. Computers & Operations Research (S0305-0548), 2008, 35(9): 2807-2839.

局部搜索	邻域结构
局部搜索	N₁	N₂	N₃	N₄
VND₁	CINS	—	—	—
VND₂	SSNS	CINS	—	—
VND₃	SSNS	CINS	CPINS	—
VND₄	SSNS	CINS	PSNS	CPINS

参数	水平
参数	1	2	3
NP	5	8	10
SE	10	20	30
m_a	2	3	4
m_b	1	2	3

参数组合	水平				Avg
参数组合	NP	SE	m_a	m_b	Avg
1	1	1	1	1	2 878.5
2	1	2	2	2	2 873.1
3	1	3	3	3	2 868.3
4	2	1	2	3	2 882.1
5	2	2	3	1	2 869.8
6	2	3	1	2	2 867.0
7	3	1	3	2	2 887.7
8	3	2	1	3	2 864.5
9	3	3	2	1	2 866.0

水平	NP	SE	m_a	m_b
等级	4	1	2	3
1	2 873.3	2 882.7	2 870.0	2 871.4
2	2 872.9	2 869.1	2 873.7	2 875.9
3	2 872.7	2 867.1	2 875.3	2 871.6

[1]	Kaiqing Zhang, Qichun Ji. Research on Multi-depot Half-open Vehicle Routing Problem with Time-varying Speed [J]. Journal of System Simulation, 2022, 34(4): 836-846.
[2]	Weiquan Wang, Ding Ding, Shuyan Cao. Hybrid Variable Neighborhood Search algorithm for the Multi-trip and Heterogeneous-fleet Electric Vehicle Routing Problem [J]. Journal of System Simulation, 2022, 34(4): 910-919.
[3]	Yefeng Jiao, Yan Wang, Zhicheng Ji. Short-term Prediction Method of Wind Power Based on BLP-ALO-SVM [J]. Journal of System Simulation, 2022, 34(12): 2535-2545.
[4]	Han Zhonghua, Liu Yuehan, Li Man, Sun Liangliang, Zheng Hongzhi. Improved Wolf Pack Algorithm for Distribution of Molds on Molds Table [J]. Journal of System Simulation, 2021, 33(1): 127-140.
[5]	Liu Jingsen, Liu Xiaozhen, Li Yu. Cuckoo Search Algorithm with Dynamic Step and Discovery Probability [J]. Journal of System Simulation, 2020, 32(2): 289-298.
[6]	Chen Jinbao, Li Jie, Wang Yan, Ji Zhicheng. PMSM Parameter Identification Using Teaching-Learning-Based Optimization with Levy Flight [J]. Journal of System Simulation, 2018, 30(4): 1456-1463.
[7]	Zhang Xin, Li Ke, Yan Dahu, Ji Zhicheng. Improved Intrusion Weed Algorithm for Solving Flexible Job Shop Scheduling Problem [J]. Journal of System Simulation, 2018, 30(11): 4469-4476.