考虑工件运输时间的分布式柔性作业车间调度
The Distributed Flexible Job Shop Scheduling Considering the Transportation Time of Workpieces
余佳林 1姚锡凡 1单文俊 1王桂茂2
作者信息
- 1. 华南理工大学机械与汽车工程学院,广州 510640
- 2. 广东世创金属科技股份有限公司,佛山 528300
- 折叠
摘要
为求解考虑工件在机器间运输时间的分布式柔性作业车间调度问题(DFJSPTW),提出了一种基于延迟接受爬山算法(LAHC)的改进算法,并建立起以最大完工时间为优化目标的数学模型.针对DFJSPTW的几个耦合性子问题,工序排序和机器选择、工厂分配采用了基于工序、机器、工厂的三层染色体编码方式去解决,而小车分配则提出了一种考虑负载均衡化的调度规则;为提高生成解的质量,初始化染色体时工厂和机器序列分别考虑了负载平衡;局部搜索过程中,算法设计了 4 种邻域搜索算子并提出了一种符合DFJSPTW的变邻域搜索策略,在变换邻域搜索算子时还引入了化学反应算法中的单分子反应搜索机制,用于加强算法的综合搜索能力.通过数值实验验证了变邻域搜索策略和引入单分子反应搜索机制的有效性,同时通过改进算法与GA_OP、GA_JS算法的对比实验,进一步验证了所提算法求解DFJSPTW问题的优越性.
Abstract
To solve the distributed flexible job shop scheduling problem considering the transportation time of workpieces between machines(DFJSPTW),this study proposed an improved algorithm based on late ac-ceptance hill climbing algorithm(LAHC)and established a mathematical model with the maximum com-pletion time as the optimization objective.Firstly,to address the coupled sub-problems of DFJSPTW,inclu-ding factory allocation,machine selection,and operation sequencing,a three-tier chromosome encoding method based on operations,machines,and factories is employed.Additionally,a scheduling rule consider-ing load balancing is proposed for AGV allocation.To improve the quality of generated solutions,load bal-ancing is taken into account separately for factory and machine sequences during the initialization of chro-mosomes.During the local searching,the algorithm is designed with four types of neighborhood search op-erators and proposed a variable neighborhood search strategy that were compatible with DFJSPTW.Addi-tionally,when switching between neighborhood search operators,a single-molecule reaction search mecha-nism inspired by the chemical reaction algorithm is introduced to enhance the algorithm's comprehensive search capability.The effectiveness of the variable neighborhood search strategy and the introduction of the single-molecule reaction search mechanism were validated through numerical experiments.Furthermore,comparative experiments with the improved algorithm against GA_OP and GA_JS algorithms were conduc-ted to further confirm the superiority of the proposed algorithm in solving DFJSPTW.
关键词
柔性作业车间调度问题/分布式调度/工件运输时间/单目标优化Key words
flexible job shop scheduling/distributed scheduling/the transportation time of workpieces/sin-gle-objective optimization引用本文复制引用
基金项目
广东省基础与应用基础基金(2024A1515011048)
广东省基础与应用基础基金(2022A1515010095)
企业产学研合作项目(20201257)
出版年
2024
NETL
NSTL
万方数据