Two-machine flowshop scheduling to minimize total tardiness

Abstract

In this paper, the problem of sequencing jobs on a two-machine flowshop to minimize total tardiness is considered, and a branch-and-bound algorithm is developed. Five dominance properties for the precedence relations between jobs in an optimal solution are proposed and a sharp lower bound on the total tardiness of a subproblem is derived. The dominance properties and the lower bound are implemented in the branch-and-bound algorithm to facilitate the search for an optimal schedule. Computational experiments are conducted and the results show that this algorithm is more efficient than the existing ones.