An empirical analysis of the optimality rate of flow shop heuristics

If a certain optimization problem is NP-hard or even harder, one could expect that the chances of solving it optimally should rather decrease with an increase of the problem size. We reveal, however, that the opposite occurs for a strongly NP-hard problem, which requires sequencing n jobs through an m machine flow shop so as to minimize the makespan. In particular, we empirically examine optimality rates (the probability of being optimal) of the famous NEH heuristic of Nawaz et al. [Nawaz, M., Enscore, Jr., E., Ham, I., 1983. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, The International Journal of Management Science 11, 91-95] and two improved versions of NEH. By using millions of simulation trials and a new effective lower bound on the shortest makespan, we observe relatively high optimality rates of the three heuristics for small values of m. Rather surprisingly, for larger values of n, the heuristics become more frequently optimal as n increases. Neither theoretical nor empirical studies of optimality rates of flow shop heuristics have been conducted so far, and - to the best of our knowledge - no similar studies are known in the field of operations research.