The authors discuss the problem of scheduling a set of n independent jobs on m parallel machines to minimize costs for earliness, due date assignment and weighted number of tardy jobs. They restrict the due dates to the common due date case, but discuss some special cases for arbitrary due dates, especially the authors show the connection to the classical scheduling problem of minimizing the weighted number of tardy jobs on a single machine or parallel machines, respectively. For the common due date, they distinguish between two different models, namely an externally given common due date or an adjustable common due date. The authors give nearly a full classification for the single and multiple machine models. The only exception is a special single machine case, where they can only provide a pseudopolynomial algorithm and the complexity status of this special case remains open. For all other problems, the authors either develop polynomial algorithms-of order n,nlogn and n4, respectively, or give NP-hardness proofs-reductions of the Knapsack problems, the even-odd-partition problem and of the NP-hard scheduling problems nℝ1ℝr(j)≥0ℝnC and nℝP2||Cmax.
