引用本文:周永强,王翠雨,李颖俐,李新宇.改进果蝇算法求解混合流水车间调度问题[J].控制理论与应用,2023,40(4):597~606.[点击复制]
zhouyongqiang,wangcuiyu,liyingli,lixinyu.Improved fruit fly optimization algorithm for solving the hybrid flow shop scheduling problem[J].Control Theory and Technology,2023,40(4):597~606.[点击复制]
改进果蝇算法求解混合流水车间调度问题
Improved fruit fly optimization algorithm for solving the hybrid flow shop scheduling problem
摘要点击 1585  全文点击 523  投稿时间：2021-10-11  修订日期：2023-02-19
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  10.7641/CTA.2022.10962
  2023,40(4):597-606
中文关键词  混合流水车间调度  关键路径  快速评估  果蝇算法
英文关键词  hybrid flow shop scheduling  critical path  fast evaluation  fruit fly algorithm
基金项目  国家重点研发计划项目(2019YFB1704600)
作者单位E-mail
周永强 华中科技大学 数字制造装备与技术国家重点实验室 2532868784@qq.com 
王翠雨* 华中科技大学 数字制造装备与技术国家重点实验室 76325434@qq.com 
李颖俐 华中科技大学 数字制造装备与技术国家重点实验室 lyl_elena@163.com 
李新宇 华中科技大学 数字制造装备与技术国家重点实验室 lixinyu@mail.hust.edu.cn 
中文摘要
      针对混合流水车间调度问题(HFSP), 本文提出了一种新的基于果蝇算法和变邻域搜索的混合优化方法. 首先, 将关键块内的工序与同阶段其他机器上的工序进行交换, 提出了一种基于关键路径的HFSP新邻域结构. 其次,针对HFSP的阶段式解码特性, 提出了一种邻域解的快速评估方法, 并验证了快速评估方法的高效性. 然后, 基于提出的新邻域结构, 并将N7和K-insertion邻域结构引入HFSP, 设计了基于上述3种邻域结构的变邻域搜索方法, 以此为基础提出了一种针对HFSP的混合优化方法. 最后, 通过对Carlier和Liao等经典测试集进行测试, 验证了所提新邻域结构的可行性和有效性, 并将该方法与其他文献的方法进行了对比, 验证了所提方法的优越性.
英文摘要
      Aiming at the hybrid flow-shop scheduling problem (HFSP), this paper proposes a new hybrid optimization method based on the fruit fly algorithm and variable neighbourhood search (VNS). Firstly, a new neighbourhood structure of HFSP based on the critical path is proposed by the operation of exchanging within the critical block. Secondly, a rapid evaluation method of neighbourhood solutions is proposed for the stage-based decoding method of HFSP, and the efficiency of this evaluation method is verified. Then, based on the proposed new neighbourhood structure and introducing the N7 and K-insertion neighbourhood structures into HFSP, a variable neighbourhood search method based on the above three neighbourhood structures is designed as a basis for proposing a hybrid optimisation method for HFSP. Finally, the feasibility and effectiveness of the proposed new neighbourhood structure is verified by testing it on classical benchmark such as Carlier and Liao, and the method is compared with other methods in the literature to verify the superiority of the proposed method.