A branch-and-bound algorithm for minimizing the total completion time in two-machine flowshop problem subject to release dates

In this paper, we consider the problem of minimizing the sum of completion times in a two-machine permutation flowshop subject to release dates. We present several variants of a branch-and-bound algorithm for the problem under consideration. Computational experiments on a large set of randomly generated instances show that problems up to 30 (70, and 100) job problems when release dates are uniformly distributed in the [1, 100] and [1, 200] ([1, 100 n], [1, 200n]) range can be solved in a reasonable CPU time.