Fast algorithms to minimize the makespan or maximum lateness in the two-machine flow shop with release times

We consider the two-machine flow-shop problem with release times where the objective is to minimize either the makespan or the maximum lateness. We present a unified treatment of various sequence-interchange operators and derive powerful new dominance orders, which are incorporated into branch-and-bound algorithms. The dominance orders produced substantial savings in the average solution time, making the algorithms very fast. They solved, within a few seconds, more than 97 per cent of the test problems with up to 500 jobs for both objectives. For the unsolved problems, the average gap from the optimum was less than 0.5 per cent.