改进果蝇算法求解混合流水车间调度问题  

Improved fruit fly optimization algorithm for solving the hybrid flow shop scheduling problem

作　　者：周永强 王翠雨[1] 李颖俐 李新宇[1] ZHOU Yong-qiang;WANG Cui-yuy;LI Ying-li;LI Xin-yu(State Key Lab of Digital Manufacturing Equipment&Technology,Huazhong University of Science&Technology,Wuhan Hubei 430074,China)

机构地区：[1]华中科技大学、数字制造装备与技术国家重点实验室,湖北武汉430074

出　　处：《控制理论与应用》2023年第4期597-606,共10页Control Theory & Applications

基　　金：国家重点研发计划项目(2019YFB1704600)资助。

摘　　要：针对混合流水车间调度问题(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.

关 键 词：混合流水车间调度 关键路径 快速评估 果蝇算法 

分 类 号：TH186[机械工程—机械制造及自动化] TP18[自动化与计算机技术—控制理论与控制工程]