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

The paper considers the problem of optimal assignment of NOP due-dates to n jobs and sequencing them on a single machine to minimize a penalty function depending on the values of assigned constant waiting allowance and maximum job tardiness. It is shown that the earliest due date (EDD) order is an optimal sequence. For finding optimal constant waiting allowance, the paper reduces the problem to a multiple objective piecewise linear programming with single variable. An efficient algorithm for optimal solution of the problem is given.