基于麻雀搜索算法的柔性作业车间不一致分批调度问题研究

doi:10.16731/j.cnki.1671-3133.2025.04.002

现代制造工程 ›› 2025, Vol. 535 ›› Issue (4): 11-24.doi: 10.16731/j.cnki.1671-3133.2025.04.002

• 先进制造系统管理运作 • 上一篇下一篇

基于麻雀搜索算法的柔性作业车间不一致分批调度问题研究

陈子研, 黎增灿, 管在林

华中科技大学机械科学与工程学院,武汉 430074

收稿日期:2024-06-11 出版日期:2025-04-18 发布日期:2025-05-08
通讯作者: 管在林,博士,教授,主要研究方向为高级计划排程与生产运作优化、制造系统建模仿真与物流分析及数字化工厂。E-mail:ziyan_chen@hust.edu.cn;zlguan@hust.edu.cn
作者简介:陈子研,硕士研究生,主要研究方向为车间计划、调度。黎增灿,硕士研究生,主要研究方向为车间调度、智能优化算法。

Research on flexible job shop batch scheduling problem with variable sublots based on improved sparrow search algorithm

CHEN Ziyan, LI Zengcan, GUAN Zailin

School of Mechanical Science & Engineering,Huazhong University of Science & Technology,Wuhan 430074,China

Received:2024-06-11 Online:2025-04-18 Published:2025-05-08

摘要/Abstract

摘要： 针对以最小化最大完工时间为目标的柔性作业车间不一致分批调度问题(Flexible Job shop Batch Scheduling Problem with Variable Sublots,FJBSP-VS),提出了一种结合禁忌搜索的改进麻雀搜索算法(Tabu Search-Sparrow Search Algorithm,TS-SSA),对工件分批、机器选择与子批排序进行集成优化。首先,设计了一种用于表示工件分批、机器选择信息与子批排序信息的双层编码方式与一种结合无延迟调度的解码方式,该解码方式可有效提高机器利用率;在保留发现者-加入者结构的基础上对麻雀搜索算法进行离散化改进,通过引入交叉算子使其可以用于离散问题的求解;其次,改进加入者所选择的靠近对象,增强算法全局搜索能力;再次,将禁忌搜索与改进麻雀搜索算法相结合,增强算法的局部搜索能力;最后,使用27个已有公开算例进行试验,验证了TS-SSA的有效性和优越性。

关键词: 柔性作业车间, 分批调度, 麻雀搜索算法, 禁忌搜索

Abstract: To address the Flexible Job shop Batch Scheduling Problem with Variable Sublots (FJBSP-VS) aiming at minimizing the maximum completion time,an improved Sparrow Search Algorithm combined with Tabu Search (Tabu Search-Sparrow Search Algorithm,TS-SSA) was proposed for the integrated optimization of job batching,machine selection,and sublot sequencing.Firstly,a two-layer encoding method was designed to represent job batching,machine selection information,and sublot sequencing information,along with a decoding method that integrates no-delay scheduling to effectively improve the machine utilization. The Sparrow Search Algorithm (SSA) was discretized while retaining the producers-scroungers structure by introducing a crossover operator to solve discrete problems.Additionally,the choice of the target close to the scrounger was improved to enhance the global search ability of the algorithm.Furthermore,the combination of Tabu Search (TS) with the improved SSA enhances the local search ability of the algorithm.Finally,experiments were conducted using 27 existing public examples to verify the effectiveness and superiority of the TS-SSA algorithm.

Key words: flexible job shop problem, batch scheduling, Sparrow Search Algorithm (SSA), Tabu Search (TS)

中图分类号:

陈子研, 黎增灿, 管在林. 基于麻雀搜索算法的柔性作业车间不一致分批调度问题研究[J]. 现代制造工程, 2025, 535(4): 11-24.

CHEN Ziyan, LI Zengcan, GUAN Zailin. Research on flexible job shop batch scheduling problem with variable sublots based on improved sparrow search algorithm[J]. Modern Manufacturing Engineering, 2025, 535(4): 11-24.

参考文献

[1] AN Y,CHEN X,LI Y,et al.An improved non-dominated sorting biogeography-based optimization algorithm for the (hybrid) multi-objective flexible job-shop scheduling problem[J].Applied Soft Computing,2021,99:106869.
[2] 周如意.多品种小批量的生产计划管理研究[J].冶金管理,2023(8):74-76.
[3] 桑红燕.流水车间批量流调度问题求解方法研究[D].武汉:华中科技大学,2015.
[4] 谢法吾,李玲玲,李丽,等.基于多目标混合进化算法的作业车间混排可变分批节能调度方法[J].中国机械工程,2023,34(13):1576-1588,1598.
[5] ROMERO M A F,GARCIA E A R,PONSICH A,et al.A heuristic algorithm based on tabu search for the solution of flexible job shop scheduling problems with lot streaming[C]//Proceedings of the Genetic and Evolutionary Computation Conference.Kyoto:Association for Computing Machinery,2018:285-292.
[6] MENG T,PAN Q K,SANG H Y.A hybrid artificial bee colony algorithm for a flexible job shop scheduling problem with overlapping in operations[J].International Journal of Production Research,2018,56(16):5278-5292.
[7] NOVAS J M.Production scheduling and lot streaming at flexible job-shops environments using constraint programming[J].Computers & Industrial Engineering,2019,136:252-264.
[8] 黎增灿,丁林山,管在林.基于改进灰狼优化算法的柔性作业车间分批调度问题研究[J].现代制造工程,2024(4):13-25.
[9] BOZEK A,WERNER F. Flexible job shop scheduling with lot streaming and sublot size optimisation[J].International Journal of Production Research,2018,56(19):6391-6411.
[10] GE Y,WANG A,ZHAO Z. Flexible job-shop scheduling with Setups and Variable Sublots[C]//International Conference on Mechanical and Intelligent Manufacturing Technologies (ICMIMT).Cape Town:IEEE,2020:187-192.
[11] LI L.Research on discrete intelligent workshop lot-streaming scheduling with variable sublots under engineer to order[J].Computers & Industrial Engineering,2022,165:107928.
[12] SANGROUDI H A,RANJBAR-BOURANI M.Solving a flexible job shop lot sizing problem with shared operations using a self-adaptive COA[J].International Journal of Production Research,2021,59(2):483-515.
[13] TUTUMLU B,SARAC T.A MIP model and a hybrid genetic algorithm for flexible job-shop scheduling problem with job-splitting[J].Computers & Operations Research,2023,155:106222.
[14] YANG Y,SONG Y,GUO W,et al.Guided shuffled frog-leaping algorithm for flexible job shop scheduling problem with variable sublots and overlapping in operations[J].Computers & Industrial Engineering,2023,180:109209.
[15] XUE J,SHEN B.A novel swarm intelligence optimization approach:sparrow search algorithm[J].Systems Science & Control Engineering,2020,8(1):22-34.
[16] 李峥峰,丁其聪,张东方,等.改进离散麻雀搜索算法求解柔性作业车间调度问题[J].现代制造工程,2023(9):18-27.
[17] 朱国晖,景文焕,李世昌.基于改进麻雀搜索算法的服务功能链优化映射算法[J].计算机应用研究,2022,39(7):2120-2123,2131.
[18] 周宁,张嵩霖,张晨.融合粗糙数据推理的离散麻雀搜索算法求解HFSP问题[J].北京航空航天大学学报,2024,50(2):398-408.
[19] 秦红斌,常永顺,唐红涛,等.混合麻雀算法求解带准备时间的分布式柔性作业车间调度问题[J].现代制造工程,2023(11):1-11,32.
[20] GLOVER F.Future paths for integer programming and links to artificial intelligence[J].Computers & Operations Research,1986,13(5):533-549.

基于麻雀搜索算法的柔性作业车间不一致分批调度问题研究

Research on flexible job shop batch scheduling problem with variable sublots based on improved sparrow search algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	廖雪超, 向桂宏, 阮兵, 田芮利, 钟实. 带AGV数量约束的柔性作业车间调度问题研究^*[J]. 现代制造工程, 2025, 537(6): 11-21.
[2]	刘亮, 贺禹铭, 祁思远. 基于数字孪生仿真的柔性作业车间调度优化研究^*[J]. 现代制造工程, 2025, 534(3): 41-51.
[3]	杨丹, 舒先涛, 余震, 鲁光涛, 纪松霖, 王家兵. 深度强化学习求解动态柔性作业车间调度问题^*[J]. 现代制造工程, 2025, 533(2): 10-16.
[4]	王赟, 马荣, 唐思源. 基于改进鲸鱼优化算法的AGV柔性作业车间多目标优化调度^*[J]. 现代制造工程, 2024, 526(7): 17-25.
[5]	唐艺军, 杜纪浩, 李雪. 考虑运输时间的混合流水车间绿色生产调度[J]. 现代制造工程, 2024, 524(5): 23-30.
[6]	黎增灿, 丁林山, 管在林. 基于改进灰狼优化算法的柔性作业车间分批调度问题研究[J]. 现代制造工程, 2024, 523(4): 13-25.
[7]	孙鸿羽, 吉卫喜, 李威, 刘凯. 基于海鸥优化算法的分布式柔性车间调度研究[J]. 现代制造工程, 2024, 523(4): 33-42.
[8]	张学聪, 晁永生, 李纯艳, 周江林. 基于机器学习的工业机器人多目标轨迹规划^*[J]. 现代制造工程, 2024, 521(2): 31-37.
[9]	闫富乾, 石致远, 王立闻. 基于改进灰狼算法的柔性作业车间动态节能分批调度问题^*[J]. 现代制造工程, 2024, 520(1): 24-32.
[10]	李峥峰;丁其聪;张东方;张国辉. 改进离散麻雀搜索算法求解柔性作业车间调度问题[J]. 现代制造工程, 2023, 516(9): 18-27.
[11]	陆心屹;韩晓龙. 基于强化学习的改进NSGA-Ⅱ求解柔性作业车间节能调度问题[J]. 现代制造工程, 2023, 515(8): 22-35.
[12]	吴迎晨，肖彪，赵正彩，彭仕鑫，苏宏华，朱夏林. 柔性作业车间调度多策略果蝇优化算法研究[J]. 现代制造工程, 2023, 512(5): 22-30.
[13]	裴红蕾. 柔性作业车间机床与搬运机器人联合调度方法[J]. 现代制造工程, 2023, 510(3): 15-21.
[14]	董维振;陈燕. 基于改进麻雀搜索算法的带钢面标识别方法[J]. 现代制造工程, 2023, 509(2): 84-91.
[15]	秦红斌;常永顺;唐红涛;张峰;王玲军. 混合麻雀算法求解带准备时间的分布式柔性作业车间调度问题[J]. 现代制造工程, 2023, 518(11): 1-11.