基于离散状态转移算法的无等待流水车间调度研究

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

摘要/Abstract

摘要：

针对制造行业中广泛存在的无等待流水车间调度问题，提出一种改进的离散状态转移算法进行求解。基于流水车间调度问题的特性，设计工件的编码方式，采用基于工件加工时间标准差为优先级的NEH(Nawaz-Enscore-Ham)方法构造初始解，设计基于插入和交换的多邻域组合搜索策略以提高初始解的质量；提出一种基于群状态的离散状态转移算法，并利用带二次状态转移操作的三种离散操作算子扩大算法的搜索范围；为进一步提高离散状态转移算法的求解性能，设计了基于莱维飞行的破坏重构局部搜索方法，对全局搜索发现的优质解进行细致搜索。仿真实验表明，改进的离散状态转移算法能够有效求解无等待流水车间调度问题。

关键词: 无等待约束条件, 流水车间调度问题, 离散状态转移算法, 变邻域搜索, 莱维飞行

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

中图分类号:

TP301.6

余佳英, 张宏立, 董颖超. 基于离散状态转移算法的无等待流水车间调度研究[J]. 系统仿真学报, 2023, 35(5): 1034-1045.

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.

图/表 13

表1

图1

图2

表2

表3

表4

图3

表5

表6

基准算例测试结果对比

测试问题	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

表6

图4

图5

图6

图7

参考文献 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]	范厚明, 咸富山, 王怀奇. 动态需求下考虑订单聚类的外卖配送路径优化[J]. 系统仿真学报, 2023, 35(2): 396-407.
[2]	张凯庆, 嵇启春. 速度时变的多中心半开放式车辆路径问题研究[J]. 系统仿真学报, 2022, 34(4): 836-846.
[3]	王伟权, 丁鼎, 曹淑艳. 混合变邻域搜索算法求解大规模电动车辆路径优化问题[J]. 系统仿真学报, 2022, 34(4): 910-919.
[4]	焦业峰, 王艳, 纪志成. 基于BLP-ALO-SVM的风电功率短期预测方法[J]. 系统仿真学报, 2022, 34(12): 2535-2545.
[5]	胡蓉, 董钰明, 钱斌. 基于探路者算法的绿色有限缓冲区流水线调度[J]. 系统仿真学报, 2021, 33(6): 1384-1396.
[6]	蔡敏, 王艳, 纪志成. 基于多策略融合量子粒子群算法的MOFFJSP研究[J]. 系统仿真学报, 2021, 33(11): 2615-2626.
[7]	韩忠华, 刘约翰, 李曼, 孙亮亮, 郑鸿志. 改进狼群算法求解模具在模台上组合分配问题[J]. 系统仿真学报, 2021, 33(1): 127-140.
[8]	刘景森, 刘晓珍, 李煜. 具有动态步长和发现概率的布谷鸟搜索算法[J]. 系统仿真学报, 2020, 32(2): 289-298.
[9]	李荣雨, 王颖. 基于莱维飞行的改进粒子群算法[J]. 系统仿真学报, 2017, 29(8): 1685-1692.