An empirical analysis of heuristics for solving the two-machine flow shop problem with job release times

The theoretical analysis of heuristics for solving intractable optimization problems has many well-known drawbacks. Constructed instances demonstrating an exceptionally poor worst-case performance of heuristics are typically too peculiar to occur in practice. Theoretical results on the average-case performance of most heuristics could not be established due to the difficulty with the use of probabilistic analysis. Moreover, the heuristics for which some type of asymptotic optimality has been proven are likely to perform questionably in practice. The purpose of this paper is to confront known theoretical results with our empirical results concerning heuristics for solving the strongly NP-hard problem of minimizing the makespan in a two-machine flow shop with job release times. The heuristics' performance is examined with respect to their average and maximum relative errors, as well as their optimality rate, that is, the probability of being optimal. In particular, this allows us to observe that the asymptotic optimality rate of so called “almost surely asymptotically optimal” heuristic can be zero. We also present a new heuristic with short worst-case running time and statistically prove that it outperforms all heuristics known so far. However, our empirical experiments reveal that the heuristic is on average slower that its competitors with much longer worst-case running times.

► We confront known theoretical results with our empirical results concerning heuristics for solving the strongly NP-hard problem of minimizing the makespan in a two-machine flow shop with job release times.
► We examine heuristics' performance with respect to their average and maximum relative errors, as well as their optimality rate, that is, the probability of being optimal.
► We observe that the asymptotic optimality rate of so-called "almost surely asymptotically optimal" heuristic can be zero.
► We present a new heuristic which outperforms all heuristics known so far.