Optimal due-date assignment and sequencing

This paper examines the problem of assigning due-dates to a given set of jobs and sequencing them on a single machine in order to minimize the cost of quoting long due-dates and that of missing the quoted due-dates. Properties required for the solution of the problem are identified, leading to the recognition that the problem is computationally difficult. It is shown, however, that there are special cases of the problem which can be solved easily. Viable solution strategies for the general problem, both exact and approximate, are also proposed.