Exact procedures for single machine total cost scheduling

Abstract

We study the One-Machine problem with release dates with the aim of minimizing several objective functions among those the total (weighted) tardiness and the total (weighted) completion time. These problems are NP hard in the strong sense. We present general dominance properties, propagation rules along with an intelligent backtracking technique, which are valid for all these criteria. These techniques have been integrated into Branch and Bound methods and have been experimentally studied. These results show the efficiency of these techniques which improve the best results found for these criteria.