基于变邻域搜索的可重入流水车间调度

A Variable Neighborhood Search for the Re-entrant Permutation Flowshop Scheduling Problem

与传统的流水车间调度问题中工件在每个机器上只能加工一次不同,考虑了机械制造中工件需要在一个机器上进行多次重复加工的实际情况,研究了工件可重入的流水车间调度问题。针对该问题,基于对邻域搜索性能的分析和学习,提出了一个自适应变邻域搜索算法,并在算法中嵌入了一个精英解集合,以增强算法的跳出局部最优的能力。基于随机测试问题的实验结果表明,所提出的自适应策略能够明显增强变邻域搜索算法的搜索效率,使得算法能够快速获得高质量的近优解,并且其性能要优于CPLEX优化软件。

Different from the traditional permutation flowshop scheduling in which each job can be processed on each machine for at most once, in practical production of the mechanical industry a job generally needs to be processed on a machine for several times. So this paper considers this practical condition and investigates the re-entrant permutation flowshop scheduling problem. For this problem, an adaptive variable neighborhood search （AVNS） algorithm is proposed based on the analysis and learning of search performance of each neighborhood. In addition, an elite solution set is embedded in the algorithm so as to enhance its ability of getting out of local optimum. Computational results based on randomly generated instances show that the proposed adaptive strategy can significantly enhance the search efficiency so that the AVNS can achieve a high quality near-optimal solution very quickly. On average, the proposed AVNS is also superior to the software CPLEX.