Principles of Sequencing and Scheduling, 2nd Edition

Appendix BThe Critical Ratio Rule

B.1 A Basic Trade‐off Problem

A common planning problem involves trading off surplus and shortage outcomes in an uncertain environment. Conceptually, we make a decision and then await the value of an uncertain outcome. However, due to uncontrollable factors, the outcome may turn out to be larger or smaller than what we decide. If the outcome is larger than the value we decide, we incur costs due to underestimation; if the outcome is smaller, we incur costs due to overestimation. Faced with these possibilities, we look for a decision that navigates optimally between the two kinds of risks.

In a scheduling environment, the uncertain outcome is often the completion time of a particular job (or a set of jobs). The job’s due date, assuming that we can choose it, plays the role of our decision. If the job completes before the due date, then we incur earliness costs, and if the job completes after the due date, we incur tardiness costs. Unless our decisions are perfect, we can anticipate incurring one cost or the other, and our objective is to minimize the expected cost.

The use of expected cost as an objective function derives from the theory of decision making under risk and uncertainty. If we interpret the scheduling scenario literally, as a repeating operational problem, then an appropriate objective is the long‐run cost, which is optimized by minimizing the expected cost corresponding to each decision.

To analyze the decision problem, we let ...