Motivation
An interval-scheduling problem gives each activity a fixed start and finish. A different problem arises when every job must be performed and we may choose its start time. One machine can process only one job at a time. Putting a job first helps that job, but delays all the jobs behind it. Which order is best depends on what those delays cost.
Two common objectives lead to different greedy rules. To control the worst lateness relative to promised due dates, put earlier due dates first. To minimize a weighted sum of completion times, compare processing time with weight. The useful lesson is how to discover and prove these rules: compare two neighboring jobs while keeping the rest of the schedule fixed.
Definitions and assumptions
Definition 2.6.1
(Jobs, schedules and lateness)
There are jobs. Job has processing time , due date , and, when needed, weight . Every job is available at time zero. A feasible schedule assigns a start time to each job so that the intervals do not overlap. Processing is nonpreemptive: a started job runs to completion without interruption. Write
Definition 2.6.2
(Objectives: maximum lateness and weighted completion time)
is completion time, is lateness, and is tardiness. Lateness can be negative: finishing early gives negative lateness. Tardiness counts only the amount by which a due date is missed. Our objectives are
The unweighted sum of completion times is the special case . An empty input can simply return an empty schedule and weighted cost zero; the maximum-lateness statements below concern nonempty inputs so that a maximum exists.
Why we can first remove idle time
Take any feasible schedule and retain its job order. Run the first job at time zero and each later job immediately after its predecessor. Each job then starts and finishes no later than before. All jobs remain available, since they were available at zero. Every lateness weakly decreases; every term weakly decreases because its weight is nonnegative.
Thus it suffices to consider schedules with no idle time. Such a schedule is completely described by a permutation of the jobs, with
There are finitely many permutations, so each objective has a minimum. This reduction proves existence as well as removing unnecessary timing decisions. It would fail if a later job had not yet been released when the machine became free.
Theorems
Theorem 2.6.3
(Earliest due date minimizes maximum lateness)
Under the stated one-machine, all-available, nonpreemptive assumptions, any no-idle schedule with jobs in nondecreasing due-date order minimizes over all feasible schedules. Equal due dates can be ordered arbitrarily. The same schedule minimizes maximum tardiness .
Theorem 2.6.4
(The processing-time-to-weight rule)
Under the same assumptions, a no-idle schedule minimizes if it orders all positive-weight jobs by nondecreasing , followed by the zero-weight jobs in any order. Equal ratios can be ordered arbitrarily. In particular, shortest processing time first minimizes the unweighted sum of completion times.
These are sufficient descriptions of optimal schedules, not claims that every optimal schedule has those orders. An inversion may leave the objective unchanged, and zero weights can create further ties.
Proof: exchanging due-date inversions
Proof
(Exchanging a due-date inversion)
Suppose neighboring jobs appear as , with . Let be the start of this two-job block. Before the exchange their completion times are and . After exchanging them, job completes at , and job completes at .
Every job outside the pair has the same completion time: the pair still occupies the same total processing time. For the changed jobs,
and
Both new latenesses are at most one of the old latenesses, so their new maximum cannot exceed the old maximum. Including the unchanged jobs proves that exchanging this inversion cannot increase .
Starting with an optimal no-idle schedule, repeatedly exchange adjacent due-date inversions. A finite sequence of such exchanges sorts the due dates: each strict inverted pair exchange reduces the inversion count. The resulting earliest-due-date schedule is therefore also optimal. Swapping equal due dates preserves the pair's maximum lateness, since the later completion determines it under either order. Hence any tie order is valid.
For a nonempty finite job set,
The right side is nondecreasing in , so an earliest-due-date schedule also minimizes maximum tardiness. The converse need not hold: if many schedules finish everything before its due date, all have maximum tardiness zero, although their negative maximum latenesses can differ.
Proof X-ray
Which old job bounds both new jobs?
In a due-date inversion, job has the earlier due date but completes second. Moving it first improves its completion time. Moving second gives it the pair's old final completion time, but with a later due date than . Thus the old lateness of bounds both new latenesses. A proof that merely says “earlier deadlines are urgent” misses this quantitative comparison.
Proof: the weighted pair difference
Proof
(The weighted pair difference)
Again compare neighboring jobs starting at time . The rest of the objective is unchanged. Their contributions in the two orders differ by
When both weights are positive, putting before is no worse exactly when . The starting time cancels, so this preference holds wherever the pair occurs. Exchanges of adjacent ratio inversions sort the positive-weight jobs without increasing cost.
If and , the difference is . Moving ahead strictly improves cost: the zero-weight job's own completion is free, but its processing delays a job whose completion matters. Exchanging all such inversions moves zero-weight jobs to the end. Two zero-weight jobs contribute zero in either order. Together these exchanges transform any optimal no-idle schedule into the asserted order. A pair with equal positive ratios has difference zero, justifying arbitrary ties.
For unit weights, the pair difference becomes , proving shortest-processing-time order. One can also write the unweighted objective as
An early processing time contributes to many completion times. Putting shorter jobs first assigns larger multipliers to smaller processing times; the exchange proof makes that intuition precise.
Concept lensCombinatorial
A pairwise description of the weighted cost
Writing as the processing time of plus those of all jobs scheduled before it gives , where means that is scheduled before . The first sum does not depend on the order. Each unordered pair contributes if is first and if is first, so the cost is a sum with one term per pair. Swapping two adjacent jobs changes exactly one pair, which is why the exchange difference is and why the ratio test is a pairwise comparison.
Worked examples
Worked example 2.6.5
(A due-date schedule and its competing objective)
Let have equal to , and . Earliest due date gives . Their completion times are and their latenesses are , so . The shortest-processing-time order has completion times and latenesses , giving a worse maximum lateness of two.
To minimize weighted completion instead, the ratios for are . Their completion times are , giving . The due-date order has weighted cost . An order can be optimal for one objective and substantially worse for another.
Worked example 2.6.6
(Equal ratios and a zero-weight job)
Jobs have equal to , and . The positive ratios are both . Order has weighted cost ; order has cost . Putting first in order raises cost to . Zero weight does not make a job harmless when it delays other jobs.
Worked example 2.6.7
(Maximum lateness is not total tardiness)
Take with and with . Earliest due date gives , with latenesses nine and nine. Its maximum lateness is nine and its total tardiness is eighteen. Order gives latenesses and ten, so its maximum lateness is worse, but its total tardiness is only ten. The maximum-lateness theorem does not minimize the sum of tardiness values.
Worked example 2.6.8
(Why release times change the model)
Suppose is available at zero, takes four time units and is due at time one hundred. Job is released at time one, takes one unit and is due at time two. Running the available job immediately gives order with finishing at five and maximum lateness three. Deliberately idling until time one, running to time two and then to time six gives maximum lateness zero. The no-idle reduction, and therefore the proof above, does not apply to this release-time model.
Implementation and cost
For either rule, sort the jobs and compute completion times in one prefix-sum pass. This takes comparisons and arithmetic operations, including evaluation of the objective. Retaining the job order, completion times and objective values takes words; a sorting implementation's extra workspace must be accounted for separately.
For positive weights, the preference is equivalent to . This avoids rounding an approximately represented quotient. An actual sorting comparator should use the strict test , breaking equality with a fixed unique job identifier; a raw non-strict comparison is not a valid strict sorting comparator. Handle zero weights separately rather than dividing by zero. Exact comparisons and arithmetic are unit-cost only when the chosen number model supports them. With binary integer inputs of at most bits, cross products need up to bits and accumulated completion times need bits. The word-operation statement is not a constant-bit-cost assertion for arbitrary large inputs.
Common mistakes
Counterexample mode
A greedy rule belongs to an objective
Claim: since earliest due date is optimal for maximum lateness, the same order also minimizes the weighted sum of completion times. Take the three jobs of the first worked example, with equal to , and . The due-date order has completion times and cost , but the order has completion times and cost . Conversely, shortest processing time first, , gives maximum lateness , while the due-date order gives . The repair is to name the objective first: each objective has its own exchange inequality, and a rule is justified only for the objective whose pair difference it sorts.
Common mistake
(Demanding an improvement for every job)
An adjacent exchange does not have to improve every job. In the due-date proof one job finishes later after the swap, but its new lateness is still bounded by the pair's old worst lateness. For the weighted sum, the algebra allows one contribution to increase while another decreases by at least as much. Confusing an aggregate improvement with a job-by-job improvement would reject the very exchanges that prove the theorems.
Common mistake
(Reusing a rule outside its model)
The assumptions also do real work. Release times can make left-shifting infeasible; precedence constraints can make a proposed exchange illegal; multiple machines change the available schedules. None of these models is covered by merely reusing the same sorting rule.
Neither earliest due date nor shortest processing time wins in general, and the problem is NP-hard.
A natural next question
Is there an exchange rule for total tardiness?
Neither earliest due date nor shortest processing time wins in general, and the problem is NP-hard.
For total tardiness , jobs favor shortest-first: total tardiness against for due-date order. Jobs favor due-date order: against . Minimizing is NP-hard, although a pseudopolynomial dynamic program exists, so no pairwise exchange rule can be expected to settle it.
Summary
A no-idle reduction turns the all-available one-machine problem into a permutation problem. A due-date inversion can be exchanged without increasing the pair's worst lateness. A weighted pair has difference , yielding ratio order. Repeated adjacent exchanges supply a global optimality proof because they reach a sorted order while preserving feasibility and never worsening the chosen objective.
Exercises
Quick check
(Jobs have equal to . Find an earliest-due-date order, every completion time and .)
Sort by due date and add processing times.
Solution · Answer
The due-date order is . Completion times are , giving latenesses and . The theorem proves this value is minimum; a short job need not be first.
Quick check
(Jobs have equal to . Find a minimum weighted-completion order and its objective value.)
Compute for the positive-weight jobs and place the zero-weight job last.
Solution · Answer
Positive ratios are for and two for , so choose . Completion times are and the weighted sum is .
Quick check
(Prove the displayed identity for the unweighted sum of completion times by counting how often each processing time occurs.)
Count in how many completion times each processing time appears.
Solution · Answer
Processing time occurs in completion times at positions , exactly times. Interchanging the two finite sums gives the identity.
Quick check
(Explain why a maximum-tardiness minimizer need not minimize maximum lateness. Give two jobs with generous due dates, and explain why giving both jobs the same due date cannot produce such a counterexample among no-idle schedules.)
Try due dates large enough that every job finishes early.
Solution · Answer
Give the one-unit job due date ten and the three-unit job due date twenty. Short-first has latenesses and maximum ; long-first has latenesses and maximum . Both have maximum tardiness zero. If both due dates equal , the last job always has the greatest lateness, namely , in either no-idle order. Equal due dates therefore cannot separate these two objectives in this way.
Quick check
(In a weighted schedule, adjacent positive-weight jobs have . How much does swapping their order decrease the objective, regardless of the block's start time?)
Use the pair difference .
Solution · Answer
The old-minus-new difference is . The surrounding jobs and start time cancel, so the objective decreases by fourteen.
Quick check
(Add a precedence constraint requiring job before job , with and . Explain exactly why the ratio-order proof cannot establish an optimal feasible schedule in this model.)
Check which order the ratio rule prefers, then check feasibility.
Solution · Answer
The ratio rule wants before , since . That order violates the precedence constraint. The proof's exchange is no longer a feasible operation; there is only the feasible order in this two-job instance. A formula comparing two objective values does not establish that both candidate orders are legal.