A guaranteed accuracy shifting bottleneck algorithm for the two-machine flowshop total tardiness problem

A guaranteed accuracy shifting bottleneck algorithm is developed for the two-machine flowshop total tardiness problem by exploiting its relationship to its single machine counterpart. The algorithm provides a solution which does not exceed the optimal by more than a predetermined value and we show that this bound is tight; further, the obtained solution can be declared optimal a priori in many instances. Computational experiments indicate that the proposed heuristic performs better than the currently best available heuristic for the problem.