On the Meaningfulness of Optimal Solutions to Scheduling Problems: Can an Optimal Solution be Nonoptimal?

N. V. R. Mahadev, Aleksandar Pekeč and Fred S. Roberts
Additional contact information
N. V. R. Mahadev: Northeastern University, Boston, Massachusetts
Aleksandar Pekeč: University of Aarhus, Aarhus, Denmark
Fred S. Roberts: Rutgers University, New Brunswick, New Jersey

Operations Research, 1998, vol. 46, issue 3-supplement-3, S120-S134

Abstract: We consider the problem of finding an optimal schedule for jobs on a single machine when there are penalties for both tardy and early arrivals. We point out that if attention is paid to how these penalties 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. In particular, we note that if the penalties measure utilities or disutilities, or loss of goodwill or customer satisfaction, then these kinds of anomalies can occur, for instance if we change both unit and zero point in scales measuring these penalties. We investigate situations where problems of these sorts arise for four specific penalty functions under a variety of different assumptions. The results of the paper have implications far beyond the specific scheduling problems we consider, and suggest that considerations of scale of measurement should enter into analysis of conclusions of optimality both in scheduling problems and throughout combinatorial optimization.

Keywords: Philosophy of modeling; effects of scales; Transportation; scheduling; tardiness and earliness; Production; scheduling; single machines (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.3.S120 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:46:y:1998:i:3-supplement-3:p:s120-s134

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().