THE 2-MACHINE TOTAL COMPLETION-TIME FLOW-SHOP PROBLEM

In this paper we study the NP-hard scheduling problem of minimizing to tal completion time in a two-machine now shop. Five known lower bounds are discussed and two new ones are presented. A new dominance criteri on is also proposed. Several versions of a branch and bound method are derived by applying, both individually and combined, these lower boun ds. A heuristic procedure is also presented that uses a constructive O (n(2)) time method, which computes a good starting solution, together with a neighborhood search based on pairwise interchanges. Computation al results show that the exact method can handle problems of up to 30 jobs in size within a reasonable amount of time and that the heuristic procedure has an average error of less than 0.5% from the optimal val ue and less than 2.7% from the lower bound.