融合粗糙数据推理的离散麻雀搜索算法求解HFSP问题

周宁; 张嵩霖; 张晨

doi:10.13700/j.bh.1001-5965.2022.0424

融合粗糙数据推理的离散麻雀搜索算法求解HFSP问题

doi: 10.13700/j.bh.1001-5965.2022.0424

兰州交通大学电子与信息工程学院，兰州 730070

基金项目: 国家自然科学基金(61650207,61963023)；兰州交通大学天佑创新团队(TY202003)

详细信息

通讯作者:
E-mail：zhouning@lzjtu.edu.cn

中图分类号: TP301.6；TB181
计量
- 文章访问数: 181
- HTML全文浏览量: 85
- PDF下载量: 16
- 被引次数: 0
出版历程
- 收稿日期: 2022-05-27
- 录用日期: 2022-08-01
- 网络出版日期: 2022-09-06
- 整期出版日期: 2024-02-27

Discrete sparrow search algorithm incorporating rough data-deduction for solving hybrid flow-shop scheduling problems

School of Electronic and Information Engineering，Lanzhou Jiaotong University，Lanzhou 730070，China

Funds: National Natural Science Foundation of China (61650207,61963023); Tianyou Innovation Team of Lanzhou Jiaotong University (TY202003)

More Information

Corresponding author: E-mail：zhouning@lzjtu.edu.cn

摘要

摘要:
针对麻雀搜索算法(SSA)易陷入局部最优、无法求解离散优化问题等不足，提出了一种改进离散麻雀搜索算法(IDSSA)。抽象原始麻雀搜索算法的位置更新公式，针对个体的不同身份设计新的离散化启发式位置更新策略，并针对混合流水车间调度问题(HFSP)设计了编码与解码方式；引入粗糙数据推理理论，通过数学证明解释了引入理论的可行性与合理性，为算法提供理论支撑，提高可解释性；利用上近似的性质扩大搜索空间，提高种群多样性，避免算法早熟，结合划分及粗糙数据推理提出3种策略，促进种群间信息共享，调节种群的开发能力与探索能力，降低算法陷入局部最优的概率；使用改进离散麻雀搜索算法求解混合流水车间调度问题，对3个小规模实例与10个Liao经典测试集进行仿真实验，验证了改进离散麻雀搜索算法求解混合流水车间调度问题的可行性，通过与遗传算法、差分进化算法等经典算法的对比实验，证明了所提算法的优越性与改进策略的有效性。
- 麻雀搜索算法 /
- 离散化算法 /
- 粗糙集理论 /
- 全局优化 /
- 近似算法 /
- 数据关联 /
- 混合流水车间调度
Abstract:
To address the shortcomings of the sparrow search algorithm (SSA), such as easy fall into local optimum and inability to solve discrete optimization problems, an improved discrete sparrow search algorithm (IDSSA) is proposed. Firstly, the position update formula of the original sparrow search algorithm is abstracted, with a new discrete heuristic position update strategy designed according to the different identities of individuals, and with the encoding and decoding methods designed for the hybrid flow-shop scheduling problem (HFSP). Secondly, the rough data-deduction theory is introduced, and the feasibility and rationality of the above theory are explained by mathematical proofs, providing theoretical support for the algorithm and improving the interpretability. Then, the nature of upper approximation is adopted to expand the search space, improve the population diversity, and avoid prematurity of the algorithm. Division and rough data-deduction are combined to propose three strategies to promote information sharing among populations, regulate the exploitation ability and exploration ability of populations, and reduce the probability of the algorithm falling into local optimum. Finally, the improved discrete sparrow search algorithm is used to solve the hybrid flow shop scheduling problem. Simulation experiments are carried out on three small-scale practical examples and ten Liao’s classic test sets to verify the feasibility of the improved algorithm. Results show the superiority of the proposed algorithm and the effectiveness of the improved strategy through comparison with classical algorithms such as genetic algorithm and differential evolutionary algorithm.
- sparrow search algorithm /
- discretization algorithm /
- rough set theory /
- global optimization /
- approximation algorithm /
- data association /
- hybrid flow-shop scheduling

HTML全文

图 1 中等范围移动

Figure 1. Medium range movement

下载: 全尺寸图片幻灯片

图 2 小范围移动

Figure 2. Small range movement

下载: 全尺寸图片幻灯片

图 3 在最差个体与自身之间移动

Figure 3. Moving between the worst individual and oneself

下载: 全尺寸图片幻灯片

图 4 靠近最优个体

Figure 4. Approaching the optimal individual

下载: 全尺寸图片幻灯片

图 5 逆序变异

Figure 5. Reverse sequence mutation

下载: 全尺寸图片幻灯片

图 6 推理关系

Figure 6. Reasoning relationship

下载: 全尺寸图片幻灯片

图 7 HFSP问题示意图

Figure 7. Schematic diagram of HFSP

下载: 全尺寸图片幻灯片

图 8 j30c5e1算例的最优调度甘特图

Figure 8. Optimal scheduling Gantt chart of j30c5e1

下载: 全尺寸图片幻灯片

表 1 小规模实例1结果

Table 1. Results of small-scale example 1

组合	前期执行概率			中期执行概率			后期执行概率			最小完工时间平均值/s
组合	策略1	策略2	策略3	策略1	策略2	策略3	策略1	策略2	策略3	最小完工时间平均值/s
1	0.3	0.4	0.3	0.2	0.7	0.1	0.1	0.2	0.7	13.5
2	0.3	0.4	0.3	0.2	0.7	0.1	0.2	0.2	0.6	13.7
3	0.3	0.4	0.3	0.3	0.6	0.1	0.1	0.2	0.7	13.6
4	0.3	0.4	0.3	0.3	0.6	0.1	0.2	0.2	0.6	13.7
5	0.4	0.3	0.3	0.2	0.7	0.1	0.1	0.2	0.7	13.7
6	0.4	0.3	0.3	0.2	0.7	0.1	0.2	0.2	0.6	13.7
7	0.4	0.3	0.3	0.3	0.6	0.1	0.1	0.2	0.7	13.5
8	0.4	0.3	0.3	0.3	0.6	0.1	0.2	0.2	0.6	13.7

下载: 导出CSV

表 2 正交实验结果

Table 2. Orthogonal experimental results

算例	组合	最小完工时间平均值/s
小规模实例2	3	297
小规模实例3	1	24
j30c5e1	1	477.2
j30c5e2	6	619.8
j30c5e3	3	613.3
j30c5e4	2	577.6
j30c5e5	1	606.8
j30c5e6	6	613.7
j30c5e7	5	633.4
j30c5e8	3	691.7
j30c5e9	1	655.1
j30c5e10	1	599.3

下载: 导出CSV

表 3 小规模实例结果比较

Table 3. Comparison of results of small-scale examples

算法	加工时间最小值/s			加工时间平均值/s
算法	实例1	实例2	实例3	实例1	实例2	实例3
GA	14.0		26	14.9		27.3
DEA		299	25		309.6	25.3
FOA	13.5	297		13.5	297.4
DSSA	14	297	24	14.2	297.6	24.2
IDSSA	13.5	297	24	13.5	297	24

下载: 导出CSV

表 4 大规模测试集结果比较

Table 4. Comparison of large-scale test set results s

算法	加工时间最小值
算法	j30c5e1	j30c5e2	j30c5e3	j30c5e4	j30c5e5	j30c5e6	j30c5e7	j30c5e8	j30c5e9	j30c5e10
GA	482.0	619.0	628.0	588.0	619.0	627	638	700.0	669	611
DEA	481.0	620.0	620.0	586.0	621.0	625	637	699.0	671	610
BBOA	484.0	621.0	623.0	585.0	618.0	628	639	698.0	670	612
IBBOA	474.0	616.0	610.0	577.0	609.0	615	629	685.0	654	596
DSSA	474.0	619.0	612.0	577.0	607.0	616	630	691.0	656	598
IDSSA	472.0	616.0	609.0	575.0	604.0	608	629	685.0	652	594

算法	加工时间平均值
算法	j30c5e1	j30c5e2	j30c5e3	j30c5e4	j30c5e5	j30c5e6	j30c5e7	j30c5e8	j30c5e9	j30c5e10
GA	495.0	627.0	635.2	599.2	627.6	636.2	644.8	712.3	677.0	622.5
DEA	490.5	624.2	631.8	597.5	627.6	635.5	643.0	709.7	680.3	619.6
BBOA	491.8	625.2	636.4	594.4	625.9	640.1	643.7	710.2	681.4	621.9
IBBOA	479.2	617.6	614.1	582.0	616.9	620.4	635.5	693.1	662.5	605.4
DSSA	479.8	622.8	616.9	583.7	615.1	618.8	637.2	697.4	660.2	606.5
IDSSA	477.2	619.8	613.3	577.6	606.8	613.7	633.4	691.7	655.1	599.3

下载: 导出CSV

参考文献(20)

[1]	XUE J K, SHEN B. A novel swarm intelligence optimization approach: Sparrow search algorithm[J]. Systems Science & Control Engineering, 2020, 8(1): 22-34.
[2]	吴新忠, 韩正化, 魏连江, 等. 矿井风流智能按需调控算法与关键技术[J]. 中国矿业大学学报, 2021, 50(4): 725-734. WU X Z, HAN Z H, WEI L J, et al. Intelligent on-demand adjustment algorithm and key technology of mine air flow[J]. Journal of China University of Mining & Technology, 2021, 50(4): 725-734(in Chinese).
[3]	付华, 刘昊. 多策略融合的改进麻雀搜索算法及其应用[J]. 控制与决策, 2022, 37(1): 87-96. FU H, LIU H. Improved sparrow search algorithm with multi-strategy integration and its application[J]. Control and Decision, 2022, 37(1): 87-96(in Chinese).
[4]	韩统, 汤安迪, 周欢, 等. 基于LASSA算法的多无人机协同航迹规划方法[J]. 系统工程与电子技术, 2022, 44(1): 233-241. HAN T, TANG A D, ZHOU H, et al. Multiple UAV cooperative path planning based on LASSA method[J]. Systems Engineering and Electronics, 2022, 44(1): 233-241(in Chinese).
[5]	熊智, 李欣童, 熊骏, 等. 基于改进麻雀搜索算法的无人机集群置信传播协同定位方法[J]. 中国惯性技术学报, 2021, 29(2): 171-177. XIONG Z, LI X T, XIONG J, et al. Cooperative positioning method for UAV swarm belief propagation based on improved sparrow search algorithm[J]. Journal of Chinese Inertial Technology, 2021, 29(2): 171-177(in Chinese).
[6]	熊国文, 张敏, 许文鑫. 基于众包模式的两级开闭混合车辆路径优化[J]. 浙江大学学报(工学版), 2021, 55(12): 2397-2408. XIONG G W, ZHANG M, XU W X. Vehicle routing optimization of two-echelon opening and closing hybrid based on crowd sourcing mode[J]. Journal of Zhejiang University (Engineering Science), 2021, 55(12): 2397-2408(in Chinese).
[7]	WU X L, CAO Z. Greedy simulated annealing algorithm for solving hybrid flow shop scheduling problem with re-entrant batch processing machine[C]//Proceedings of the Chinese Automation Congress. Piscataway: IEEE Press, 2020: 4907-4911.
[8]	LIANG X, WANG P, HUANG M. Flowshop scheduling problem with limited buffer based on hybrid shuffled frog leaping algorithm[C]//Proceedings of the IEEE 7th International Conference on Computer Science and Network Technology. Piscataway: IEEE Press, 2019: 87-93.
[9]	ZHANG Q, TIAN Z, WANG S, et al. Iterated greedy algorithm for solving a hybrid flow shop scheduling problem with reentrant jobs[C]//Proceedings of the Chinese Control and Decision Conference. Piscataway: IEEE Press, 2020: 5636-5641.
[10]	SUN X, SHEN W, SUN B. A modified genetic algorithm for distributed hybrid flowshop scheduling problem[C]//Proceedings of the IEEE 24th International Conference on Computer Supported Cooperative Work in Design. Piscataway: IEEE Press, 2021: 981-986.
[11]	DONG X. An self-adaptive flower pollination algorithm for hybrid flowshop scheduling problem[C]//Proceedings of the IEEE 3rd Information Technology, Networking, Electronic and Automation Control Conference. Piscataway: IEEE Press, 2019: 2176-2179.
[12]	WANG P, SANG H Y, TAO Q Y, et al. Improved migratory birds optimisation algorithm to solve low-carbon hybrid lot-streaming flowshop scheduling problem[C]//Proceedings of the World Conference on Computing and Communication Technologies. Piscataway: IEEE Press, 2020: 33-36.
[13]	SCHUMACHER C, BUCHHOLZ P, FIEDLER K, et al. Local search and Tabu search algorithms for machine scheduling of a hybrid flow shop under uncertainty[C]//Proceedings of the Winter Simulation Conference. Piscataway: IEEE Press, 2020: 1456-1467.
[14]	GAREY M R, JOHNSON D S, SETHI R. The complexity of flowshop and jobshop scheduling[J]. Mathematics of Operations Research, 1976, 1(2): 330-348.
[15]	JOYCE T, HERRMANN J M. A review of no free lunch theorems, and their implications for metaheuristic optimization[M]//YANG X S. Nature-inspired algorithms and applied optimization. Berlin: Springer, 2018: 27-51.
[16]	闫硕. 基于上近似的粗糙数据推理研究及应用[D]. 北京: 北京交通大学, 2017: 32-45. YAN S. Rough data-deduction based on the upper approximation and its applications[D]. Beijing: Beijing Jiaotong University, 2017: 32-45(in Chinese).
[17]	VON LÜCKEN C, BRIZUELA C A, BARÁN B. Clustering-based multipopulation approaches in MOEA/D for many-objective problems[J]. Computational Optimization and Applications, 2022, 81(3): 789-828. doi: 10.1007/s10589-022-00348-0
[18]	杜利珍, 王震, 柯善富, 等. 混合流水车间调度问题的果蝇优化算法求解[J]. 中国机械工程, 2019, 30(12): 1480-1485. DU L Z, WANG Z, KE S F, et al. Fruit fly optimization algorithm for solving hybrid flow-shop scheduling problems[J]. China Mechanical Engineering, 2019, 30(12): 1480-1485(in Chinese).
[19]	LIAO C J, TJANDRADJAJA E, CHUNG T P. An approach using particle swarm optimization and bottleneck heuristic to solve hybrid flow shop scheduling problem[J]. Applied Soft Computing, 2012, 12(6): 1755-1764. doi: 10.1016/j.asoc.2012.01.011
[20]	张源, 陶翼飞, 王加冕. 改进差分进化算法求解混合流水车间调度问题[J]. 中国机械工程, 2021, 32(6): 714-720. ZHANG Y, TAO Y F, WANG J M. An improved DE algorithm for solving hybrid flow-shop scheduling problems[J]. China Mechanical Engineering, 2021, 32(6): 714-720(in Chinese).