An asynchronous genetic local search algorithm for the permutation flowshop scheduling problem with total flowtime minimization

摘要

In this study, the permutation flowshop scheduling problem with the total flowtime criterion is considered. An asynchronous genetic local search algorithm (AGA) is proposed to deal with this problem. The AGA consists of three phases. In the first phase, an individual in the initial population is yielded by an effective constructive heuristic and the others are randomly generated, while in the second phase all pairs of individuals perform the asynchronous evolution (AE) where an enhanced variable neighborhood search (E-VNS) as well as a simple crossover operator is used. A restart mechanism is applied in the last phase. Our experimental results show that the algorithm proposed outperforms several state-of-the-art methods and two recently proposed meta-heuristics in both solution quality and computation time. Moreover, for 120 benchmark instances, AGA obtains 118 best solutions reported in the literature and 83 of which are newly improved.