Two-machine flowshop scheduling to minimize total tardiness

Authors:

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.

This publication has 13 references indexed in Scilit: