Multiple-machine scheduling with earliness, tardiness and completion time penalties

We consider the problem of scheduling n jobs on m parallel and identical machines. The goal is to find an optimal permutation of the jobs and an optimal due date which jointly minimize an objective function consisting of earliness, tardiness and completion time penalties. We show that the problem is NP-hard and present a polynominally solvable case. Furthermore, a heuristic is developed and computationally demonstrated to be efficient in obtaining near-optimal solutions.