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

针对混合流水车间调度问题(HFSP),本文提出了一种新的基于果蝇算法和变邻域搜索的混合优化方法.首先,将关键块内的工序与同阶段其他机器上的工序进行交换,提出了一种基于关键路径的HFSP新邻域结构.其次,针对HFSP的阶段式解码特性,提出了一种邻域解的快速评估方法,并验证了快速评估方法的高效性.然后,基于提出的新邻域结构,并将N7和K-insertion邻域结构引入HFSP,设计了基于上述3种邻域结构的变邻域搜索方法,以此为基础提出了一种针对HFSP的混合优化方法.最后,通过对Carlier和Liao等经典测试集进行测试,验证了所提新邻域结构的可行性和有效性,并将该方法与其他文献的方法进行了对比,验证了所提方法的优越性.

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

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.