95-20 Single Machine Scheduling with Earliness and Tardiness Penalties: When is an Optimal Solution Not Optimal?

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

ABSTRACT
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 is avoided.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-20.ps

DIMACS Home Page