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 concl usion that a particular solution to a scheduling problem is optimal. T he 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 transpor ted receive different priorities. We note that in this problem, if att ention is paid to how certain parameters are measured, then a change o f scale of measurement might lead to the anomalous situation where a s chedule is optimal if the parameter is measured in one way, but not if the parameter is measured in a different way that seems equally accep table. This conclusion about the sensitivity of the conclusion that a given solution to a combinatorial optimization problem is optimal is d ifferent from the usual type of conclusion in sensitivity analysis, si nce it holds even though there is no change in the objective function, the constraints, or other input parameters, but only in scales of mea surement. We emphasize the need to consider such changes of scale in a nalysis of scheduling and other combinatorial optimization problems. W e also discuss the mathematical problems that arise in two special cas es, where all desired arrival times are the same and the simplest case where they are not, namely the case where there are two distinct arri val times but one of them occurs exactly once. While specialized, thes e two examples illustrate the types of mathematical problems that aris e from considerations of the interplay between scale-types and optimiz ation.