In this note, we consider a single machine scheduling problem with generalized total tardiness objective function. An NP-hardness proof and a pseudo-polynomial time solution algorithm are proposed for a special case of this problem.
Moreover, we present a new graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted number of tardy jobs on a single machine.
The latter algorithm improves the complexity of an existing pseudo-polynomial algorithm by Lawler.
E.R. Gafarov, A.A. Lazarev and F. Werner. (2012), A note on a single machine scheduling problem with generalized total tardiness objective function. Information Processing Letters, 112 (3), 72 — 76. (among the 25 most downloaded papers of this journal in Science Direct within the last 90 days in January 2012) (journal impact factor 2018: 0.793). Q2