DIMACS TR: 95-20
Single Machine Scheduling with Earliness and Tardiness Penalties:
When is an Optimal Solution Not Optimal?
Authors: N.V.R. Mahadev, A. Pekec, F.S. Roberts
We consider the problem of finding the optimal schedule for jobs on a
single machine when there are penalties for both late and early arrivals.
We point out that if attention is paid to how certain parameters are
measured, then a change of scale of measurement might lead to the
anomalous situation where a schedule is optimal if these parameters are
measured in one way, but not if they are measured in a different way that
seems equally acceptable. We discuss conditions under which this anomaly
Paper available at:
DIMACS Home Page