Optimal assignment of slack due-dates and sequencing in a single-machine shop

This paper considers the problem of optimal assignment of slack due-dates to n jobs and sequencing them on a single-machine to minimize a penalty function depending on the values of the assigned slack allowance and maximum job tardiness. It is shown that the earliest due-date order yields an optimal sequence and the optimal slack allowance is a simple function of the cost per unit slack allowance.