Optimal assignment of due-dates for preemptive single-machine scheduling

This paper considers due-date assignment and preemptive scheduling of n jobs in a single-machine shop under precedence constraints. Along with a release date, the job i has processing time piand a due-date diis assigned depending on pi. If di=k1pi+k2, the due-date assignment method is known as PPW: processing-time-plus-wait. If di=k1pk2i, it is known as TWK-power (total-work-content-power) due-date determination. The problem is to minimize an objective function depending on the assigned due-date parameters k1and k2, together with maximum tardiness penalty. It is shown that an O(n2) algorithm yields an optimal schedule. A simple analytical solution method is presented to find the optimal due-dates for a special case of the objective function and PPW due-date assignment method.