Heuristic solution methods for the stochastic flow shop problem

We investigate the stochastic flow shop problem with m machines and general distributions for processing times. No analytic method exists for solving this problem, so we looked instead at heuristic methods. We devised three constructive procedures with modest computational requirements, each based on approaches that have been successful at solving the deterministic counterpart. We compared the performance of these procedures experimentally on a set of test problems and found that all of them achieve near-optimal performance.

► Three heuristic procedures were tested for the stochastic flow shop problem. ► Each heuristic is based on an established procedure for the deterministic problem. ► Each heuristic is computationally efficient. ► None of the three heuristics dominated the others in all experimental settings. ► All three procedures delivered solutions that are roughly within 1% of the optimum.