The reversibility property in a job-insertion tiebreaker for the permutational flow shop scheduling problem

The best performing approximate methods proposed for the permutational flow shop scheduling problem with makespan minimization are the well known NEH constructive heuristic and the iterated greedy algorithm. Both methods are based on the successive insertion (or reinsertion) of jobs into a partial schedule, evaluating the makespan of the resulting schedule for all insertion positions, and selecting the insertion position that presents the shortest makespan. Frequently, there are many tied insertion positions that produce such shortest makespan. Thus, a tiebreaker must be used to discern a selection among the tied insertion positions. Many tiebreakers have been proposed in the literature for this case. These tiebreakers improve the results produced by approximate methods when embedded into them. In this paper we propose two new tiebreakers that use a weighted and an unweighted approximation of the idle time increment produced by inserting the job into each tied insertion position. They were designed considering the reversibility property of the PFSSP. Our computational experiments show that the proposed tiebreakers outperform tiebreakers from the literature when evaluated within the NEH heuristic and within the iterated greedy algorithm. The iterated greedy algorithms with the proposed tiebreakers embedded are the best approximate methods so far for the permutational flow shop scheduling problem. © 2021 Elsevier B.V.We are indebted to Profs. Victor Fernandez-Viagas and Weibo Liu for generously sharing their code and for guiding us on the reimplementation of their tiebreakers. We are very grateful to the referees, for their valuable comments on earlier versions of this paper. This research has been partially supported by the Fondo Nacional de Desarrollo Cient?fico, Tecnol?gico y de Innovaci?n Tecnol?gica (FONDECYT) and the World Bank through projects Kusisqa (014/2019 - FONDECYT - BM - INC.INV) and Het-FSSP (445/2019 - FONDECYT - PIB); and by the supercomputing center ?Inkari? of the Universidad Nacional de San Agust?n de Arequipa