On no-wait and no-idle flow shops with makespan criterion

The paper deals with the NP-hard problems of minimizing the makespan in m-machine no-wait and no-idle permutation flow shops. We identify networks whose longest path lengths represent the makespans. These networks reveal the duality between the two problems, and show graphical explanations of the fact that under no-wait and no-idle conditions the makespan can be a decreasing function of some job processing times. Moreover, they also lead to a natural reduction of the no-wait flow shop problem to the traveling salesman problem, some lower bounds on the shortest makespan, and new efficiently solvable special cases.