| Citation: | ZHOU N，ZHANG S L，ZHANG C. Discrete sparrow search algorithm incorporating rough data-deduction for solving hybrid flow-shop scheduling problems[J]. Journal of Beijing University of Aeronautics and Astronautics，2024，50（2）：398-408 （in Chinese） doi: 10.13700/j.bh.1001-5965.2022.0424
|
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.
| [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).
|
Figures(8) / Tables(4)
Copyright © Journal of Beijing University of Aeronautics and Astronautics
Address: Editorial Department of Journal of Beijing University of Aeronautics and Astronautics, 37 Xueyuan Road, Haidian District, Beijing Post Code: 100191 Email: jbuaa@buaa.edu.cn
Supported by:
Beijing Renhe Information Technology Co., Ltd.
DownLoad:
