Effects of change of scale on optimality in a scheduling model with priorities and earliness/tardiness penalties

We consider the effect of changes of scale of measurement on the conclusion that a particular solution to a scheduling problem is optimal. The analysis in this paper was motivated by the problem of finding the optimal transportation schedule when there are penalties for both late and early arrivals, and when different items that need to be transported receive different priorities. We note that in this problem, 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 the parameter is measured in one way, but not if the parameter is measured in a different way that seems equally acceptable. This conclusion about the sensitivity of the conclusion that a given solution to a combinatorial optimization problem is optimal is different from the usual type of conclusion in sensitivity analysis, since it holds even though there is no change in the objective function, the constraints, or other input parameters, but only in scales of measurement. We emphasize the need to consider such changes of scale in analysis of scheduling and other combinatorial optimization problems. We also discuss the mathematical problems that arise in two special cases, where all desired arrival times are the same and the simplest case where they are not, namely the case where there are two distinct arrival times but one of them occurs exactly once. While specialized, these two examples illustrate the types of mathematical problems that arise from considerations of the interplay between scale-types and optimization.

Duke Scholars

Author Aleksandar Pekec Fuqua School of Business