The paper addresses deterministic, nonpreemptive scheduling of jobs th
at are immediately available for processing on a single machine. The j
obs-are partitioned into several multijob customer orders. The problem
is to determine a due-date for each customer order and to schedule al
l the jobs such that a total penalty function is minimized. The total
penalty function is the sum of penalties for job earliness, penalties
for job tardiness, and penalties associated with the lead times of cus
tomer orders. The main result is that there is an optimal solution in
which the jobs within each customer order are processed contiguously.
This is an appealing feature in terms of implementation. Efficient alg
orithms are presented for solving special cases of this problem.