2-STAGE NO-WAIT SCHEDULING MODELS WITH SETUP AND REMOVAL TIMES SEPARATED

This paper studies two models of two-stage processing with no-wait in process. The first model is the two-machine flow shop, and the other i s the assembly model. For both models we consider the problem of minim izing the makespan, provided that the setup and removal times are sepa rated from the processing times. Each of these scheduling problems is reduced to the Traveling Salesman Problem (TSP). We show that, in gene ral, the assembly problem is NP-hard in the strong sense. On the other hand, the two-machine flow shop problem reduces to the Gilmore-Gomory TSP, and is solvable in polynomial time. The same holds for the assem bly problem under some reasonable assumptions. Using these and existin g results, we provide a complete complexity classification of the rele vant two-stage no-wait scheduling models. (C) 1997 Elsevier Science Lt d.