Two-Machine Stochastic Flow Shops With Blocking and the Traveling Salesman Problem

The paper deals with the problem of minimizing the expected makespan in a two-machine flow shop with blocking and random job processing times. It is well known that it reduces to an instance of the traveling salesman problem (TSP). Assuming that the job processing times can be stochastically ordered on both machines, we show that the problem under study is equivalent to TSP on a permuted Monge matrix. This allows us to prove that it is NP-hard for the independently and exponentially distributed job processing times, and identify a new class of efficiently solvable special cases.