The two-machine total completion time flow shop problem

The two-machine total completion time flow shop problem

0.00 Avg rating0 Votes
Article ID: iaor1999152
Country: Netherlands
Volume: 90
Issue: 2
Start Page Number: 227
End Page Number: 237
Publication Date: Apr 1996
Journal: European Journal of Operational Research
Authors: , ,
Keywords: programming: branch and bound
Abstract:

In this paper we study the NP-hard scheduling problem of minimizing total completion time in a two-machine flow shop. Five known lower bounds are discussed and two new ones are presented. A new dominance criterion is also proposed. Several versions of a branch and bound method are derived by applying, both individually and combined, these lower bounds. A heuristic procedure is also presented that uses a constructive O(n2) time method, which computes a good starting solution, together with a neighborhood search based on pairwise interchanges. Computational 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 value and less than 2.7% from the lower bound.

Reviews

Required fields are marked *. Your email address will not be published.