Parallel-machine scheduling problems with earliness and tardiness penalties

This paper considers the problem of assigning a common due-date and sequencing a set of simultaneously available jobs on several identical parallel-machines. The objective is to minimize some penalty function of earliness, tardiness and due-date values. The paper shows that the problem is NP-hard with either a total or a maximal penalty function. For the problem with a total penalty function, it shows that the special case in which all jobs have an equal processing time is polynomially-solvable.