Due-date assignment and early/tardy scheduling on identical parallel machines

This article examines the problem of simultaneously assigning a common due date to a set of independent jobs and scheduling them on identical parallel machines in such a way that the costs associated with the due date and with the earliness or tardiness of the jobs are minimized. The authors establish that, for certain values of the due-date cost, an optimal schedule for this problem is also optimal for an early/tardy scheduling problem studied by Emmons. They discuss the solution properties for the two problems, and show that both problems are NP-hard even for two machines. The authors further show that these problems become strongly NP-hard if the number of machines is allowed to be arbitrary. They provide a dynamic programming solution for the problems, the complexity of which indicates that the problems can be solved in pseudopolynomial time as long as the number of machines remains fixed. Finally, the authors present the results of a limited computational study.