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.