A best-of-breed iterated greedy for the permutation flowshop scheduling problem with makespan objective

摘要

In this paper, we analyse several issues concerning the most efficient approximate algorithms for the permutation flowshop scheduling problem with makespan objective. On the one hand, it is not clear which algorithm obtains the best solutions for the problem, since (1) conflicting results have been reported regarding the implementation of a key part in one of these algorithms (the FF tie-breaking mechanism by Fernandez-Viagas and Framinan, 2014), and (2) some recent contributions have appeared independently, so they have not been compared so-far. On the other hand, since all these efficient methods consist of specialised variants of an iterated greedy algorithm, it is worth exploring if their specific features can be efficiently combined so a new, best-of-breed algorithm can be designed. These questions are addressed in this paper by first conducting an extensive comparison among the best-so-far algorithms (including a detailed description of the FF tie-breaking algorithm and the posting of its source codes to ensure full reproducibility), and then by designing a best-of-breed combination of these algorithms. The computational experience carried out shows that the new algorithm designed significantly outperform existing ones, thus being the best-so-far approximate method for the problem. (C) 2019 Elsevier Ltd. All rights reserved.