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 identica l parallel machines in such a way that the costs associated with the d ue date and with the earliness or tardiness of the jobs are minimized. We establish that, for certain values of the due-date cost, an optima l schedule for this problem is also optimal for an early/tardy schedul ing problem studied by Emmons. We discuss the solution properties for the two problems, and show that both problems are NP-hard even for two machines. We further show that these problems become strongly NP-hard if the number of machines is allowed to be arbitrary. We provide a dy namic programming solution for the problems, the complexity of which i ndicates that the problems can be solved in pseudopolynomial time as l ong as the number of machines remains fixed. Finally, we present the r esults of a limited computational study. (C) 1994 John Wiley & Sons, I nc.