The minmax due-date assignment problem with acceptable lead-times

We study a single machine scheduling and due-date assignment problem with acceptable lead-times. The setting combines elements of the classical common due-date model and the DIF model, where job-dependent due-dates need to be determined. The objective function, which is of a minmax type, consists of four cost components: (1) job-earliness cost, (2) job-tardiness cost, (3) due-date cost, (4) due-date tardiness cost. We present a simple procedure for identifying the different job-types, and consequently, a polynomial-time solution is introduced. The case of due-windows for acceptable lead-times is also discussed.