A note on optimal assignment of slack due-dates in single-machine scheduling (Q1310016)

The author solves a single machine problem with job ready times, special due dates and job preemption allowed. Additionally, job precedence constraints are given. The objective is to minimize a linear combination of the maximum tardiness and due date assignment costs. As due dates the slack due dates are used which allow constant slack for all jobs, i.e. \(d_ j= r_ j+ k\) for all jobs \(j\), \(d_ j\) and \(r_ j\) denote the job due date and ready time, respectively, and the parameter \(k\) is the constant slack for all jobs. The solution consists of two phases, computing the optimal job sequence first, then optimizing the due date parameter \(k\). For arbitrary precedence constraints, the algorithm works in \(O(n^ 2)\), whereas for tree-like precedence constraints the complexity decreases to \(O(n\log n)\). For special cases (if the job due dates and modified job release times are similarly ordered) the proposed algorithm can even be used if job preemption is not allowed.