A simple lower bound for total completion time minimization in a two-machine flowshop

Abstract

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.