Handling ties in heuristics for the permutation flow shop scheduling problem

Abstract

The NEH heuristic, as the most efficient procedure for the flow shop scheduling problem is based on constructing a sequence of jobs by iteratively inserting the non-scheduled jobs into a current subsequence. The initial phase of NEH, in which an initial order (priority order) of jobs is defined, and the insertion procedure, usually cause a high number of ties. Unlike the sort of ties in the insertion phase, the ties in the initial phase are not uniquely defined by the definition of NEH. This results in an inaccuracy in most of the large number of published experimental results on this topic. The experimental research, presented in this paper confirms the importance of the inclusion of the information about the sort of ties in the initial phase in any experimental result related to NEH. The conclusion, obtained by this study, is that the range of the objective values for different sorts of ties is often greater than the improvements, published in literature. This allowed us to construct a very simple algorithm that outperforms published NEH improvements, maintaining NEH's exceptional efficiency. The proposed algorithm also uses the information about the ties in the insertion phase to improve the objective value. The permutation flow shop problem primarily concerns the makespan objective, but the main conclusions can be applied to other flow shop problems as well.