Abstract: In flexible job shops,the need for transportation using multiple functionally heterogeneous Automated Guided Vehicles (AGVs) arises due to differences in product sizes and shapes.However,existing research mainly focuses on homogeneous AGVs and does not sufficiently consider the impact of heterogeneous AGVs on transportation scheduling.Addressing the Flexible Job-shop Scheduling Problem with Heterogeneous Transportation and Sequence Dependent Setup Time (FJSPHT-SDST),an Improved Genetic Algorithm based on Variable Neighborhood Search (IGA-VNS) was proposed to minimize the maximum return time.The research introduced a task-based three-level encoding method and an active decoding strategy,utilizing genetic operations for global search.For processing and transportation task blocks on critical paths,three local search neighborhood structures were designed.Additionally,to handle solutions with multiple critical paths,a solution comparison criterion was proposed to enhance local search effectiveness.Finally,the proposed method's effectiveness was validated through comparisons with other effective algorithms on practical instances,and the impact of heterogeneous AGVs and AGV quantity on scheduling outcomes was analyzed.

Key words: flexible job shop, heterogeneous automated guided vehicles, integrated scheduling, sequence dependent setup time, critical path

摘要： 柔性作业车间中因产品尺寸和形状的差异导致需要多种功能异构的AGV进行运输。然而,现有研究主要关注同构AGV,未充分考虑异构AGV对运输调度的影响。针对考虑异构AGV和机器顺序相关准备时间的柔性作业车间生产与物流集成调度问题,提出了一种基于变邻域搜索的改进遗传算法（IGA-VNS）以最小化最大返回时间(maximum return time)。研究引入基于任务的三层编码方法和主动解码策略,利用遗传操作进行全局搜索,并针对关键路径上加工和运输任务块设计了3种局部搜索邻域结构。同时,针对调度解包含多条关键路径的情况,提出解的比较准则以增强局部搜索效果。最后,通过与其他有效算法在实例上的对比验证了所提方法的有效性,并分析了异构AGV和AGV数量对调度结果的影响。

关键词: 柔性作业车间, 异构AGV, 集成调度, 顺序相关准备时间, 关键路径