The Weighted Total Tardiness Problem with Fixed Shipping Times and Overtime Utilization

This paper addresses the problem of simultaneously determining overtime utilization and job sequencing over a finite planning horizon in a single machine job shop environment. Shipping times are assumed to occur at fixed and specified points in time, and their number is much smaller than the number of jobs. The goal is to find an overtime utilization level and job sequence that yields a “good” tradeoff between overtime cost and tardiness penalties. We begin by showing that the problem in its simplest form is NP-hard. We then present an approximate algorithm based on a capacitated transshipment formulation. This approximation provides a feasible solution along with its error bound. The algorithm is refined by incorporating the dominance relations of jobs. Extensive computational experience indicates that the algorithm is implementable in terms of both speed and accuracy.