求解置换流水车间调度问题的混合鸟群算法

doi:10.11772/j.issn.1001-9081.2021091650

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (9): 2952-2959.DOI: 10.11772/j.issn.1001-9081.2021091650

• 前沿与综合应用 • 上一篇

求解置换流水车间调度问题的混合鸟群算法

闫红超¹, 汤伟¹(), 姚斌²

^1.陕西科技大学电气与控制工程学院，西安 710021
^2.陕西科技大学电子信息与人工智能学院，西安 710021

收稿日期:2021-09-22 修回日期:2022-01-05 接受日期:2022-01-13 发布日期:2022-09-19 出版日期:2022-09-10
通讯作者: 汤伟
作者简介:闫红超（1980—），男，河南新乡人，工程师，硕士，主要研究方向：智能优化、生产调度；
姚斌（1981—），男，陕西咸阳人，副教授，博士，主要研究方向：智能优化、图像处理。
基金资助:
国家自然科学基金资助项目(62073206);陕西省技术创新引导专项(2020CGHJ?007)

Hybrid bird swarm algorithm for solving permutation flowshop scheduling problem

Hongchao YAN¹, Wei TANG¹(), Bin YAO²

^1.School of Electrical and Control Engineering，Shaanxi University of Science and Technology，Xi’an Shaanxi 710021，China
^2.School of Electronic Information and Artificial Intelligence，Shaanxi University of Science and Technology，Xi’an Shaanxi 710021，China

Received:2021-09-22 Revised:2022-01-05 Accepted:2022-01-13 Online:2022-09-19 Published:2022-09-10
Contact: Wei TANG
About author:YAN Hongchao， born in 1980， M. D.， engineer. His research interests include intelligent optimization， production scheduling.
YAO Bin， born in 1981， Ph. D.， associate professor. His research interests include intelligent optimization， image processing.
Supported by:
National Natural Science Foundation of China(62073206);Technology Innovation Guidance Special Foundation of Shaanxi Province(2020CGHJ-007)

摘要/Abstract

摘要：

针对置换流水车间调度问题（PFSP），提出了一种混合鸟群算法（HBSA）以更加有效地最小化最大完工时间。首先，为了改善初始种群的质量和多样性，结合一种基于NEH（Nawaz-Enscore-Ham）的启发式算法和混沌映射提出了一种新的种群初始化方法；其次，为了使算法能够处理离散的调度问题，采用最大排序值（LRV）规则将连续的位置值转换为离散的工件排序；最后，为了强化算法对解空间的探索能力，借鉴变邻域搜索（VNS）和迭代贪婪（IG）算法的思想针对个体最佳工件排序和种群最佳工件排序分别提出了局部搜索方法。针对广泛使用的Rec标准测试集进行了仿真测试，并与目前有效的元启发式算法——刘等提出的混合差分进化算法（L-HDE）、混合共生生物搜索算法（HSOS）、离散狼群算法（DWPA）、多班级教学优化算法（MCTLBO）相比较，结果表明，HBSA取得的最佳相对误差（BRE）、平均相对误差（ARE）的平均值比上述四种算法至少下降了73.3%、76.8%，从而证明HBSA具有更强的寻优能力和更好的稳定性。尤其是针对测试算例Rec25和Rec27，仅HBSA的求解结果达到了目前已知最优解，进一步证明了其优越性。

关键词: 鸟群算法, 置换流水车间调度问题, 种群初始化, 局部搜索, 最大完工时间

Abstract:

A Hybrid Bird Swarm Algorithm （HBSA） was proposed to minimize the makespan more efficiently for Permutation Flowshop Scheduling Problem （PFSP）. Firstly， to improve the quality and diversity of initial population， a new population initialization method was put forward by combining a NEH （Nawaz-Enscore-Ham） based heuristic algorithm and chaotic mapping. Secondly， to deal with the discrete scheduling problem by the algorithm， the Largest Ranked Value （LRV） rule was adopted to convert continuous position values to discrete job permutation. Finally， to enhance the ability of the algorithm to explore the solution space， local search methods for the individual best job permutation and population best job permutation were proposed on the basis of the ideas of Variable Neighborhood Search （VNS） and Iterative Greedy （IG） algorithms respectively. The proposed algorithm was simulated and tested on the widely used benchmark test set Rec and compared with Hybrid Differential Evolution algorithm proposed by Liu et al （L-HDE） algorithm， Hybrid Symbiotic Organisms Search （HSOS） algorithm， Discrete Wolf Pack Algorithm （DWPA） and Multi-Class Teaching-Learning-Based Optimization （MCTLBO） algorithm， which are the effective meta-heuristic algorithms for PFSP. The results show that the average values of Best Relative Error （BRE） and Average Relative Error （ARE） achieved by HBSA are at least 73.3% and 76.8% lower than those of the above four algorithms， thus proving that HBSA has stronger search ability and better stability. It is worth mentioning that， for Rec25 and Rec27 test instances， only HBSA achieves the currently known optimal solutions， which further proves its superiority.

Key words: Bird Swarm Algorithm (BSA), Permutation Flowshop Scheduling Problem (PFSP), population initialization, local search, makespan

中图分类号:

TP39

闫红超, 汤伟, 姚斌. 求解置换流水车间调度问题的混合鸟群算法[J]. 计算机应用, 2022, 42(9): 2952-2959.

Hongchao YAN, Wei TANG, Bin YAO. Hybrid bird swarm algorithm for solving permutation flowshop scheduling problem[J]. Journal of Computer Applications, 2022, 42(9): 2952-2959.

图/表 11

图1 HBSA流程

Fig. 1 Flow chart of HBSA

图2 LRV规则表示方法

Fig.2 Representation of LRV rule

图3 插入操作实例

Fig.3 Example of insert operation

图4 交换操作实例

Fig.4 Example of swap operation

表1 Rec标准测试集的最优解

Tab.1 The optimal results of Rec benchmark

算例	$m$	$n$	$C *$	算例	$m$	$n$	$C *$
Rec01	5	20	1 247	Rec23	10	30	2 011
Rec03	5	20	1 109	Rec25	15	30	2 513
Rec05	5	20	1 242	Rec27	15	30	2 373
Rec07	10	20	1 566	Rec29	15	30	2 287
Rec09	10	20	1 537	Rec31	10	50	3 045
Rec11	10	20	1 431	Rec33	10	50	3 114
Rec13	15	20	1 930	Rec35	10	50	3 277
Rec15	15	20	1 950	Rec37	20	75	4 951
Rec17	15	20	1 902	Rec39	20	75	5 087
Rec19	10	30	2 093	Rec41	20	75	4 960
Rec21	10	30	2 017

表1 Rec标准测试集的最优解

Tab.1 The optimal results of Rec benchmark

算例	$m$	$n$	$C *$	算例	$m$	$n$	$C *$
Rec01	5	20	1 247	Rec23	10	30	2 011
Rec03	5	20	1 109	Rec25	15	30	2 513
Rec05	5	20	1 242	Rec27	15	30	2 373
Rec07	10	20	1 566	Rec29	15	30	2 287
Rec09	10	20	1 537	Rec31	10	50	3 045
Rec11	10	20	1 431	Rec33	10	50	3 114
Rec13	15	20	1 930	Rec35	10	50	3 277
Rec15	15	20	1 950	Rec37	20	75	4 951
Rec17	15	20	1 902	Rec39	20	75	5 087
Rec19	10	30	2 093	Rec41	20	75	4 960
Rec21	10	30	2 017

表2 HBSA与BSA、HBSA1~HBSA3计算结果的比较

Tab.2 Comparison of computational results among HBSA， BSA and HBSA1~HBSA3

算例	BSA		HBSA1		HBSA2		HBSA3		HBSA
算例	BRE	ARE	BRE	ARE	BRE	ARE	BRE	ARE	BRE	ARE
平均值	7.635	10.933	3.749	4.036	0.213	0.271	1.546	2.246	0.098	0.173
Rec01	4.411	8.528	2.005	3.769	0.000	0.000	0.321	1.235	0.000	0.000
Rec03	2.435	6.353	1.713	1.713	0.000	0.000	0.180	0.180	0.000	0.000
Rec05	3.140	4.630	0.242	0.322	0.000	0.000	0.242	0.242	0.000	0.000
Rec07	2.299	6.660	1.149	3.078	0.000	0.000	0.000	1.034	0.000	0.000
Rec09	4.099	9.073	1.431	1.614	0.000	0.000	1.301	1.405	0.000	0.000
Rec11	6.429	10.887	6.429	6.429	0.000	0.000	0.629	2.068	0.000	0.000
Rec13	4.560	9.440	1.969	2.052	0.000	0.000	1.969	1.969	0.000	0.000
Rec15	4.410	6.905	5.385	5.385	0.000	0.000	1.179	1.600	0.000	0.000
Rec17	5.941	10.862	4.101	4.101	0.000	0.000	2.208	3.344	0.000	0.000
Rec19	9.412	11.804	3.679	3.794	0.287	0.287	0.812	1.223	0.143	0.268
Rec21	7.685	10.902	4.512	4.730	0.188	0.149	1.438	1.616	0.149	0.149
Rec23	7.161	11.599	7.608	7.668	0.298	0.378	1.840	3.590	0.149	0.219
Rec25	7.879	11.834	4.497	4.759	0.119	0.263	3.024	3.438	0.000	0.103
Rec27	9.608	13.184	3.793	4.197	0.169	0.236	2.191	2.790	0.000	0.181
Rec29	12.505	15.826	4.416	4.486	0.000	0.061	1.355	3.244	0.000	0.026
Rec31	11.856	13.348	5.123	5.511	0.263	0.361	1.872	3.369	0.099	0.246
Rec33	8.028	10.780	1.574	1.805	0.000	0.000	0.514	0.732	0.000	0.000
Rec35	6.012	7.795	0.336	0.336	0.000	0.000	0.000	0.049	0.000	0.000
Rec37	14.361	16.574	6.423	6.589	1.070	1.527	3.918	4.314	0.343	0.816
Rec39	12.561	14.839	5.838	5.901	0.865	0.908	2.497	4.152	0.649	0.702
Rec41	15.544	17.773	6.512	6.512	1.210	1.512	4.980	5.569	0.524	0.913

图5 HBSA和BSA对Rec07、Rec17、Rec27及Rec37的收敛曲线

Fig.5 Convergence curves of HBSA and BSA for Rec07， Rec17， Rec27 and Rec37

表3 HBSA与四种优化算法计算结果的比较

Tab.3 Comparison of computational results among HBSA and four optimization algorithms

算例	L-HDE		HSOS		MCTLBO		DWPA		HBSA
算例	BRE	ARE	BRE	ARE	BRE	ARE	BRE	ARE	BRE	ARE
平均值	0.502	0.757	0.583	1.050	0.367	0.747	0.427	0.759	0.098	0.173
Rec01	0.000	0.000	0.000	0.000	0.000	0.120	0.000	0.000	0.000	0.000
Rec03	0.000	0.000	0.000	0.000	0.000	0.068	0.000	0.000	0.000	0.000
Rec05	0.242	0.242	0.000	0.000	0.000	0.217	0.000	0.213	0.000	0.000
Rec07	0.000	0.000	0.000	0.000	0.000	0.632	0.000	0.000	0.000	0.000
Rec09	0.000	0.026	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
Rec11	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
Rec13	0.000	0.275	0.000	0.273	0.000	0.192	0.000	0.129	0.000	0.000
Rec15	0.000	0.523	0.000	0.523	0.000	0.356	0.000	0.213	0.000	0.000
Rec17	0.000	0.363	0.000	1.388	0.000	0.037	0.000	0.043	0.000	0.000
Rec19	0.287	0.702	0.620	1.274	0.287	0.430	0.287	0.978	0.143	0.268
Rec21	0.645	1.279	1.437	1.537	1.438	1.557	0.543	1.157	0.149	0.149
Rec23	0.348	0.428	0.348	1.280	0.149	0.686	0.403	0.616	0.149	0.219
Rec25	0.557	1.082	0.835	2.067	0.199	0.809	0.379	1.027	0.000	0.103
Rec27	0.253	0.851	0.969	1.432	0.253	1.016	0.433	0.952	0.000	0.181
Rec29	0.831	1.049	0.831	2.488	0.000	0.822	0.475	1.183	0.000	0.026
Rec31	0.427	0.644	0.427	0.644	0.427	1.307	0.987	0.971	0.099	0.246
Rec33	0.000	0.244	0.000	0.565	0.128	0.777	0.019	0.156	0.000	0.000
Rec35	0.000	0.000	0.000	0.000	0.000	0.026	0.000	0.112	0.000	0.000
Rec37	2.565	3.001	2.565	3.001	1.959	2.430	1.158	2.805	0.343	0.816
Rec39	1.730	1.832	1.828	2.222	0.904	1.613	1.633	2.374	0.649	0.702
Rec41	2.661	3.351	2.388	3.350	1.956	2.601	2.660	3.003	0.524	0.913

图6 BRE的比较

Fig.6 Comparison of BRE

图7 ARE的比较

Fig.7 Comparison of ARE

图8 BREˉ和AREˉ的比较

Fig.8 Comparison of BREˉ and AREˉ

参考文献 24

1	GAREY M R， JOHNSON D S， SETHI R. The complexity of flowshop and jobshop scheduling［J］. Mathematics of Operations Research， 1976， 1（2）： 117-129. 10.1287/moor.1.2.117
2	CHUNG C S， FLYNN J， KIRCA O. A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems［J］. International Journal of Production Economics， 2002， 79（3）： 185-196. 10.1016/s0925-5273(02)00234-7
3	NAWAZ M， ENSCORE E E， Jr.， HAM I. A heuristic algorithm for the m-machine， n-job flow-shop sequencing problem［J］. Omega， 1983， 11（1）： 91-95. 10.1016/0305-0483(83)90088-9
4	JOHNSON S M. Optimal two- and three-stage production schedules with setup times included［J］. Naval Research Logistics Quarterly， 1954， 1（1）： 61-68. 10.1002/nav.3800010110
5	TASGETIREN M F， LIANG Y C， SEVKLI M， et al. A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem［J］. European Journal of Operational Research， 2007， 177（3）： 1930-1947. 10.1016/j.ejor.2005.12.024
6	CEBERIO J， IRUROZKI E， MENDIBURU A， et al. A review on estimation of distribution algorithms in permutation-based combinatorial optimization problems［J］. Progress in Artificial Intelligence， 2012， 1（1）： 103-117. 10.1007/s13748-011-0005-3
7	LIU Y， YIN M H， GU W X. An effective differential evolution algorithm for permutation flow shop scheduling problem［J］. Applied Mathematics and Computation， 2014， 248： 143-159. 10.1016/j.amc.2014.09.010
8	亓祥波，朱云龙，张丁一. 求解PFSP的双种群协同学习算法［J］. 控制与决策， 2017， 32（1）： 12-20. 10.13195/j.kzyjc.2015.1568
	QI X B， ZHU Y L， ZHANG D Y. Double population co-learning algorithm for permutation flow-shop scheduling problems［J］. Control and Decision， 2017， 32（1）： 12-20. 10.13195/j.kzyjc.2015.1568
9	秦旋，房子涵，张赵鑫. 混合共生生物搜索算法求解置换流水车间调度问题［J］. 浙江大学学报（工学版）， 2020， 54（4）： 712-721. 10.3785/j.issn.1008-973X.2020.04.010
	QIN X， FANG Z H， ZHANG Z X. Hybrid symbiotic organisms search algorithm for permutation flow shop scheduling problem［J］. Journal of Zhejiang University （Engineering Science）， 2020， 54（4）： 712-721. 10.3785/j.issn.1008-973X.2020.04.010
10	MENG X B， GAO X Z， LU L H， et al. A new bio-inspired optimisation algorithm： bird swarm algorithm［J］. Journal of Experimental and Theoretical Artificial Intelligence， 2016， 28（4）： 673-687. 10.1080/0952813x.2015.1042530
11	罗钧，刘泽伟，张平，等. 基于非线性因子的改进鸟群算法在动态能耗管理中的应用［J］. 电子与信息学报， 2020， 42（3）： 729-736. 10.11999/JEIT190264
	LUO J， LIU Z W， ZHAGN P， et al. Application of improved bird swarm algorithm based on nonlinear factor in dynamic energy management［J］. Journal of Electronics and Information Technology， 2020， 42（3）： 729-736. 10.11999/JEIT190264
12	张玉，卢子广，卢泉，等. 基于Levy飞行改进鸟群算法的光伏直流微电网优化配置研究［J］. 太阳能学报， 2021， 42（5）： 214-220.
	ZHANG Y， LU Z G， LU Q， et al. Research on optimal configuration of photovoltaic DC microgrid based on Levy flight improved bird swarm algorithm［J］. Acta Energiae Solaris Sinica， 2021， 42（5）： 214-220.
13	陈少，吉卫喜，仇永涛，等. 基于改进鸟群算法的双资源约束离散智能车间调度问题研究［J］. 现代制造工程， 2019（4）： 20-26.
	CHEN S， JI W X， QIU Y T， et al. Improved bird swarm algorithm for dual resource constrained discrete intelligent job shop scheduling problem［J］. Modern Manufacturing Engineering， 2019（4）： 20-26.
14	屈迟文，傅彦铭，罗明山，等. 求解柔性作业车间调度问题的鸟群算法［J］. 计算机工程与应用， 2018， 54（17）： 249-257.
	QU C W， FU Y M， LUO M S， et al. Solving flexible job-shop scheduling problem using bird swarm algorithm［J］. Computer Engineering and Applications， 2018， 54（17）： 249-257.
15	REEVES C R. A genetic algorithm for flowshop sequencing［J］. Computers and Operations Research， 1995， 22（1）： 5-13. 10.1016/0305-0548(93)e0014-k
16	RIM C， PIAO S H， LI G， et al. A niching chaos optimization algorithm for multimodal optimization［J］. Soft Computing， 2018， 22（2）： 621-633. 10.1007/s00500-016-2360-2
17	LIU W B， JIN Y， PRICE M. A new improved NEH heuristic for permutation flowshop scheduling problems［J］. International Journal of Production Economics， 2017， 193： 21-30. 10.1016/j.ijpe.2017.06.026
18	KUMAR S， MANDAL K K， CHAKRABORTY N. Optimal DG placement by multi-objective opposition based chaotic differential evolution for techno-economic analysis［J］. Applied Soft Computing， 2019， 78： 70-83. 10.1016/j.asoc.2019.02.013
19	RUIZ R， STÜTZLE T. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem［J］. European Journal of Operational Research， 2007， 177（3）： 2033-2049. 10.1016/j.ejor.2005.12.009
20	PAN Q K， RUIZ R. An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem［J］. Omega， 2014， 44： 41-50. 10.1016/j.omega.2013.10.002
21	FARAHMAND RAD S， RUIZ R， BOROOJERDIAN N. New high performing heuristics for minimizing makespan in permutation flowshops［J］. Omega， 2009， 37（2）： 331-345. 10.1016/j.omega.2007.02.002
22	TAILLARD E. Some efficient heuristic methods for the flow shop sequencing problem［J］. European Journal of Operational Research， 1990， 47（1）： 65-74. 10.1016/0377-2217(90)90090-x
23	谢锐强，张惠珍. 求解置换流水车间调度的离散狼群算法［J］. 控制工程， 2020， 27（2）： 288-296.
	XIE R Q， ZHNAG H Z. Discrete wolf pack algorithm for permutation flow shop scheduling problem［J］. Control Engineering of China， 2020， 27（2）： 288-296.
24	张其文，张斌. 基于教学优化算法求解置换流水车间调度问题［J］. 系统仿真学报， 2022， 34（5）： 1054-1063. 10.16182/j.issn1004731x.joss.20-0983
	ZHANG Q W， ZHANG B. Teaching-learning-based optimization algorithm for permutation flowshop scheduling［J］. Journal of System Simulation， 2022， 34（5）： 1054-1063. 10.16182/j.issn1004731x.joss.20-0983

[1]	湛航, 何朗, 黄樟灿, 李华峰, 张蔷, 谈庆. 改进的基于层次距离的基因表达式编程特征选择分类算法[J]. 计算机应用, 2021, 41(9): 2658-2667.
[2]	邓文瀚, 张铭, 王李进, 钟一文. 混合群体增量学习算法求解闭环布局问题[J]. 计算机应用, 2021, 41(1): 95-102.
[3]	陈桢, 钟一文, 林娟. 求解0-1背包问题的混合贪婪遗传算法[J]. 计算机应用, 2021, 41(1): 87-94.
[4]	张架鹏, 倪志伟, 倪丽萍, 朱旭辉, 伍章俊. 基于改进离散人工蜂群算法的同类机调度优化[J]. 计算机应用, 2020, 40(3): 689-697.
[5]	张玉州, 徐廷政, 郑军帅, 饶舜. 考虑紧急度的救灾车辆路径问题建模与优化[J]. 计算机应用, 2019, 39(8): 2444-2449.
[6]	宋婷, 陈矛, 吴超, 张龚钊. 基于多类迭代局部搜索的自动化排课算法[J]. 计算机应用, 2019, 39(6): 1760-1765.
[7]	陈林烽, 齐学梅, 陈俊文, 黄琤, 陈付龙. 批量流水调度问题的量子候鸟协同优化算法[J]. 计算机应用, 2019, 39(11): 3250-3256.
[8]	吕进锋, 赵怀慈. 基于记忆库粒子群算法的海上协作搜寻计划制定[J]. 计算机应用, 2018, 38(9): 2477-2482.
[9]	李斌, 陈爱斌, 周国雄, 周涛. 基于Cell-DEVS的森林灭火资源调度狼群优化算法[J]. 计算机应用, 2018, 38(5): 1494-1499.
[10]	王晓静, 彭虎, 邓长寿, 黄海燕, 张艳, 谭旭杰. 基于均匀局部搜索和可变步长的萤火虫算法[J]. 计算机应用, 2018, 38(3): 715-721.
[11]	顾军华, 霍士杰, 武君艳, 尹君, 张素琪. 求解最大团问题的并行多层图划分方法[J]. 计算机应用, 2018, 38(12): 3425-3432.
[12]	王佳君, 喻强, 张晶晶. 基于先验置信传播的图像修复改进算法[J]. 计算机应用, 2016, 36(4): 1115-1119.
[13]	宋月振, 裴腾达, 裴炳南. 基于中心解的改进人工蜂群算法[J]. 计算机应用, 2016, 36(4): 1022-1026.
[14]	欧阳秋萍, 李杰, 沈林成. 考虑3G/4G网络特性的多无人机环保监测任务调度[J]. 计算机应用, 2016, 36(3): 871-877.
[15]	刘翱, 邓旭东, 李维刚. 基于模拟退火的混合萤火虫Memetic算法[J]. 计算机应用, 2016, 36(11): 3055-3061.

求解置换流水车间调度问题的混合鸟群算法

Hybrid bird swarm algorithm for solving permutation flowshop scheduling problem

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 24

相关文章 15

编辑推荐

Metrics