Trade-off solutions in a single-machine scheduling problem for minimizing total earliness and maximum tardiness

This paper considers a single-machine scheduling problem involving minimization of the total earliness and the maximum tardiness. Four dominant properties for the precedence relationship between jobs in a search for an optimal solution are proposed. The lower bounds of the total earliness and the maximum tardiness of a subproblem are derived. The dominance properties and the lower bounds are implemented in the branchand-bound algorithm to facilitate the search for an optimal schedule. A heuristic algorithm is then developed to overcome the inefficiency of the branch-and-bound algorithm. Computational performance of the two algorithms is also investigated.