On heuristic solutions for the stochastic flowshop scheduling problem

We address the problem of scheduling jobs in a flowshop when their processing times adopt a given distribution (stochastic flowshop scheduling problem), for which optimal solutions exist only for very specific cases. Consequently, some heuristics have been proposed, all of them with similar performance. In our paper, we first focus on the critical issue of estimating the expected makespan of a sequence and found that, for instances with a medium/large variability (expressed as the coefficient of variation of the processing times of the jobs), the number of samples or simulation runs used in the literature may not be sufficient to derive robust conclusions. We thus propose a procedure with a variable number of iterations that ensures that the error in the estimation of the expected makespan is bounded within a small percentage with a very high probability. Using this procedure, we test the main heuristics proposed in the literature and find significant differences in their performance, in contrast with existing studies. We also find that the deterministic counterpart of the most efficient heuristic for the stochastic problem performs extremely well for most settings, which indicates that (at least within the limitations of our study), a practical way to solve the stochastic problem may be to simplify it to its deterministic version.