A fast algorithm to minimize makespan for the two-machine flow-shop problem with release times

Abstract

<p>We consider the two -machine flow-shop problem with release times where the objec­ tive is to minimize the makespan. We derive a new dominance order and incorporate it into an efficient branch and bound algorithm which uses an adaptive branching scheme. The algorithm performed very well. It solved within a few seconds 953 of the test prob­ lems with up to 500 jobs in a large scale computational experiment. For the unsolved problems, the average gap between the best solution found and the optimum was less than 0.53. Experiments also indicate that the speed of the algorithm is largely due to the use of the dominance order which cut solution times roughly in half.</p>