A SIMPLE LOWER BOUND FOR TOTAL COMPLETION TIME MINIMIZATION IN A TWO-MACHINE FLOWSHOP

The purpose of this study is to present a simple lower bound to facilitate the development of branch-and-bound algorithms for the minimization of total completion time in a two-machine flowshop. The studied problem is known to be strongly NP-hard. In the literature, several lower bounds have been proposed. The bounding technique addressed in this paper is based upon a concept about rearrangement of the parameters of the input instance. The technique is intrinsically simple for computer implementations. We conduct computational experiments for problems with 10–65 jobs. Numerical results from our computational study indicate that the new scheme is very effective in reducing the execution time needed for composing optimal solutions.