Sparrow search algorithm to solve flexible job shop scheduling problem
-
摘要: 为解决传统的元启发式算法在处理柔性作业车间调度问题（flexible job shop scheduling problem, FJSP）时的收敛速度较慢，易陷入局部最优等问题，提出了麻雀搜索算法（sparrow search algorithm, SSA)解决FJSP问题的优化方法。首先，分析和研究了柔性作业车间调度问题并针对问题的特点进行数学建模和仿真模拟，以实现最大完工时间的最小化和总能耗的最优化；然后，提出了解决问题的优化研究方法和柔性作业车间调度分析问题的编码方式，建立了求解FJSP的SSA流程；最后，根据标准算例数据和实际车间生产数据对算法进行仿真模拟，证明了应用SSA在求解FJSP问题的可行性、优越性和高效性，助力车间的智能化管控。
-
关键词:
- 麻雀搜索算法 /
- 柔性作业车间调度问题 /
- 元启发式算法
Abstract: In order to solve the problem that the traditional meta-heuristic algorithm has slow convergence speed and is easy to fall into local optimum when dealing with the flexible job shop scheduling problem (FJSP), The sparrow search algorithm (SSA) is proposed to solve the FJSP problem. Firstly, the flexible job shop scheduling problem is analyzed and studied, and mathematical modeling and simulation are carried out according to the characteristics of the problem, in order to minimize the maximum completion time and optimize the total energy consumption. Then, the optimization research method to solve the problem and the coding method of flexible job shop scheduling analysis problem are proposed, and the SSA process to solve FJSP is established. Finally, according to the standard example data and the actual workshop production data to simulate the algorithm, proved that the application of SSA in solving FJSP problems in the feasibility, superiority and efficiency, to help the intelligent control of the workshop. -
表 1 3
$ \times $ 5的完全柔性作业车间加工时间表工件 工序 可选机器 M1 M2 M3 M4 M5
N1O11 5 4 2 6 2 O12 2 3 7 3 4 O13 8 3 2 5 5
N2O21 2 5 3 4 4 O22 4 5 3 7 8 O23 2 3 2 5 1
N3O31 3 5 3 6 5 O32 3 7 2 4 7 O33 2 7 2 6 4 
下载: 导出CSV
表 3 实际案例实验结果
目标 tsPSO CMABC SSA ${C}_{ {\rm{max} } }$ 11 12 11 12 11 11 12 $ {W}_{t} $ 50 43 45 44 45 46 41 加权值 22.7 21.3 21.2 21.6 21.2 21.5 20.7
下载: 导出CSV
表 4 实际案例实验结果
算例名称
（问题规模）目标 AL＋CGA CSTA HTABC SSA Kacem1 ${C}_{{\rm{max}}}$ 6 8 $ \mathrm{N}/\mathrm{A} $ $ \mathrm{N}/\mathrm{A} $ 6 7 7 $ {W}_{t} $ 16 15 15 15 16 加权值 9 10 8.7 9.4 9.7 Kacem2 ${C}_{{\rm{max}}}$ $ \mathrm{N}/\mathrm{A} $ 11 12 11 11 12 11 12 $ {W}_{t} $ 32 32 33 34 33 32 34 加权值 17.3 18.0 17.6 17.9 18.3 17.3 18.6
下载: 导出CSV
-
[1] He L, Chiong R, Li W, et al. Multi-objective optimization of energy-efficient job-shop scheduling with dynamic reference point-based fuzzy relative entropy[J]. IEEE Transactions on Industrial Informatics, 2022, 18(1): 600-610. [2] Gu X L, Huang M, Liang X. A discrete particle swarm optimization algorithm with adaptive inertia weight for solving multi-objective flexible job-shop scheduling problem[J]. IEEE Access, 2020(99): 1. [3] Bissoli D C, Zufferey N, Amaral A R S. Lexicographic optimization‐based clustering search metaheuristic for the multiobjective flexible job shop scheduling problem[J]. International Transactions in Operational Research, 2019, 28(5): 2733-2758. [4] Lei D, L M, Wang L, et al. A two-phase meta-heuristic for multi-objective flexible job shop scheduling problem with total energy consumption threshold[J]. IEEE Transactions on Cybernetics, 2019, 45(3): 1097-1109. [5] 徐建萍, 路光明, 余鹏, 等. 考虑批量的多目标柔性作业车间鲁棒调度[J]. 现代制造工程, 2019(10): 28-34. [6] Ishibuchi H, Murata T. A multi-objective genetic local search algorithm and its application to shop scheduling[J]. IEEE Transactions on Systems, Man and Cybernetics-Part C:Application and Reviews, 1998, 28: 392-403. doi: 10.1109/5326.704576 [7] Deng Q W, Gong G L, Gong X R, et al. A bee evolutionary guiding nondominated sorting genetic algorithm ii for multi-objective flexible job-shop scheduling[J]. Research Article, 2017(3): 5232518. [8] 陈魁, 毕利. 考虑运输时间的多目标柔性作业车间调度研究[J]. 小型微型计算机系统, 2021, 42(5): 946-952. doi: 10.3969/j.issn.1000-1220.2021.05.008 [9] 薛建凯. 一种新型的群智能优化技术的研究与应用[D]. 上海: 东华大学, 2020. [10] 毛清华, 张强. 融合柯西变异和反向学习的改进麻雀算法[J]. 计算机科学与探索, 2021, 15(6): 1155-1164. doi: 10.3778/j.issn.1673-9418.2010032 [11] 汤安迪, 韩统, 徐登武, 等. 基于混沌麻雀搜索算法的无人机航迹规划方法[J]. 计算机应用, 2021, 41(7): 2128-2136. [12] 杨玮, 杨白月, 王晓雅, 等. 低碳环境下冷链物流企业库存-配送优化[J]. 包装工程, 2021, 42(11): 45-52. [13] 韩统, 汤安迪, 周欢, 等. 基于LASSA算法的多无人机协同航迹规划方法[J]. 系统工程与电子技术, 2022, 44(1): 233-241. doi: 10.12305/j.issn.1001-506X.2022.01.29 [14] 王永彬. 制造企业降本增效工作机制的构建研究[J]. 中国管理信息化, 2020, 23(18): 145-146. doi: 10.3969/j.issn.1673-0194.2020.18.067 [15] 杨草原, 邓永滨, 孙孟珂. 基于NSGA-Ⅲ算法的多目标柔性作业车间调度问题研究[J]. 信息技术与信息化, 2021(12): 121-123. doi: 10.3969/j.issn.1672-9528.2021.12.034 [16] 程冰, 徐华, 王玲娣, 等. 改进人工蜂群求解多目标柔性作业车间调度问题[J]. 信息与控制, 2019, 48(1): 115-122,128. [17] Kacem I, Hammadi S, Borne P. Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems[J]. IEEE Transactions on Systems Man, and Cybernetics, 2002, 32(1): 1-13. doi: 10.1109/TSMCC.2002.1009117 [18] Kacem I, Hammadi S, Borne P. Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic[J]. Mathematics & Computers in Simulation, 2014, 60(3-5): 245-276. [19] 吴贝贝, 张宏立, 王聪, 等. 基于正态云模型的状态转移算法求解多目标柔性作业车间调度问题[J]. 控制与决策, 2021, 36(5): 1181-1190. [20] 孟冠军, 杨大春, 陶细佩. 基于混合人工蜂群算法的多目标柔性作业车间调度问题研究[J]. 计算机应用研究, 2019, 36(4): 972-974,979. -
下载:
点击查看大图
图(5) / 表(4)
计量
- 文章访问数: 154
- HTML全文浏览量: 18
- PDF下载量: 28
- 被引次数: 0
