Sequencing Work by Cost of Delay Under Precedence Constraints

A backlog is a scheduling problem whether or not it is modelled as one: a set of items, each with a rate at which delay costs something, each needing a span of work on a resource that can do one thing at a time. The question “what next” has an exact answer under one specific set of assumptions, and the interest lies in how far that answer survives when the assumptions are relaxed.

Cost of delay expressed as a rate

The starting point is a per-item cost rate. If an item is worth a certain amount per unit time once delivered, and delivery happens at completion time, then total value over a fixed horizon is maximised by minimising the sum of each item’s rate multiplied by its completion time: sum over items of w_j C_j, where w_j is the cost of delay per day and C_j is the day the item completes.

The formulation assumes that value accrues linearly, that items are independent, that all of them will eventually be done, and that the horizon is long enough to contain all completions. Each assumption can fail, but the objective is still the right reference point: it captures the two facts that a delay costs more for some items than others, and that finishing something early moves all subsequent items earlier as well.

The interchange argument that yields a ratio rule

Consider two items scheduled consecutively, starting at time S. If a runs first, completion times are S + p_a and S + p_a + p_b. If b runs first, they are S + p_b and S + p_b + p_a. Everything before S and everything after the pair is unaffected by the choice, so comparing the two orders reduces to comparing w_a p_a + w_b(p_a + p_b) with w_b p_b + w_a(p_b + p_a).

Subtracting the second from the first leaves p_a w_b − p_b w_a. The first order is better exactly when this is negative, which rearranges to w_a / p_a > w_b / p_b. Any pair in an optimal sequence must therefore be in non-increasing order of the ratio of cost of delay to duration, and by repeated exchange the whole sequence must be sorted that way. Smith published the rule in 1956 for single-stage production.

from itertools import permutations

def smith_order(items):                       # items: (name, weight_per_day, duration)
    return [n for n, w, p in sorted(items, key=lambda t: t[1] / t[2], reverse=True)]

def cost(order, items):
    spec = {n: (w, p) for n, w, p in items}
    t, total = 0, 0
    for n in order:
        w, p = spec[n]
        t += p
        total += w * t                        # weighted completion time
    return total

items = [('a', 3, 2), ('b', 5, 4), ('c', 9, 3), ('d', 2, 1), ('e', 7, 6)]
best = min(permutations(n for n, _, _ in items), key=lambda o: cost(o, items))
assert cost(smith_order(items), items) == cost(best, items)

The proof is short enough that the rule can be trusted as a theorem rather than a heuristic, and that matters: it means a disagreement about the order is a disagreement about the inputs, not about the method.

Why the ratio is fragile in practice

The ratio rule is exact given w and p. Both are estimates, and the ratio amplifies their errors asymmetrically.

Duration appears in the denominator, so a small p produces a large ratio, and the absolute error in estimating p is not proportionally smaller. An item thought to take one day when it takes three drops from a ratio of w/1 to w/3, a factor of three. An item thought to take twenty days when it takes twenty-two moves by about nine percent. The ordering therefore has a systematic bias towards small estimated items, not because small items are more valuable but because their denominators are uncertain in relative terms.

The weight is harder still. Cost of delay is a rate whose value depends on a counterfactual: what happens if this is a week late. For revenue-bearing features the counterfactual can sometimes be modelled from traffic and conversion; for internal work it is usually a judgment, and judgments about rates are not comparable across people unless they are anchored to a common unit. Two items whose weights came from different people’s intuitions are being compared as if the numbers were commensurable.

A third fragility comes from interaction between items. The objective assumes additive value, so it cannot express enabling work, where one item makes several others cheaper or possible. Such an item carries little value on its own and a large value through its successors. The remedy is to price the successors into the enabler, which is a modelling decision with no unique answer, and to treat the result as preferred rather than optimal.

What precedence does to optimality

Real backlogs have dependencies. An item cannot start until another finishes, either because of technical coupling or because the second is a follow-on release of the first.

With arbitrary precedence constraints, minimising total weighted completion time on one machine is NP-hard; Lawler established the result in 1978. The difficulty is structural rather than a limitation of known algorithms: the ratio order may be infeasible because a high-ratio item sits behind a low-ratio one, and any feasible order must pay for the blocked item’s duration before collecting the valuable one.

A natural heuristic applies the ratio rule to the available set: at each step, among items whose predecessors are complete, choose the highest ratio. It fails in a specific and instructive way. Consider a short, low-value item that must precede a long, high-value one. The pair is worth scheduling early if the combined ratio is high, but the available-set rule sees only the first item’s poor ratio and defers the pair. The standard correction is to compute the ratio over the remaining chain: sum the weights of the item and its successors still to be done, sum their durations, and use that aggregate ratio for the leading item. The corrected rule recognises that starting a chain early collects the whole chain’s value sooner.

Block decomposition gives a stronger result for some structures. Sidney’s work on decomposition partitions the item set into blocks that can be sequenced as units, which is exact when the precedence graph has the right shape and gives bounds otherwise. For the general case, exact solution requires branch and bound or integer programming, which is why practical sequencing is done by rule and reviewed rather than optimised.

Deadlines replace weights when the objective changes

Many backlogs have due dates rather than weights, and the objective changes with them. Minimising the maximum lateness on one machine is solved by earliest due date order, an exchange argument of the same shape as Smith’s: if two adjacent items are out of due-date order, swapping them cannot increase the maximum lateness. Minimising the number of late items is solved by Moore’s algorithm, which sorts by due date, then repeatedly removes the longest item from the prefix whenever a lateness occurs, moving it to the end.

The results are exact only for their own objectives, and the objectives conflict. A sequence ordered by earliest due date can have terrible weighted completion time, and one ordered by ratio can miss every deadline. Combining them requires a single objective, for example weighted completion time subject to a maximum lateness bound, which is a harder problem and is usually solved approximately.

One machine is an assumption worth naming

Everything above assumes a single resource that works on one item at a time. A team is not that, and the parallel-machine version of the weighted problem is NP-hard even for two machines, so the ratio rule loses its exactness as soon as more than one person can work.

That does not make the rule useless. It makes the rule a statement about the bottleneck. Where one constraint determines the completion of everything, such as a single reviewer, a shared environment, or one person who can perform a required approval, the sequence through that constraint is the sequence that matters, and the ratio rule applies to it exactly. Where work is genuinely parallel, the rule applies weakly or not at all. Establishing which situation holds is the first step, and the critical path computation is the tool for it: an item on the zero-float chain through the constraint should be scheduled by its effect on that chain, not by its standalone ratio. Where the sequencing is done by pull rather than by assignment, the work-in-progress limit determines the order indirectly, because the item that finishes first frees the slot that admits the next one.