Chapter XIX Job Sequencing

Deadlines on a single machine

One machine, n jobs, n deadlines. Pick a sequence; pay the penalty for what's late.

Karp's job sequencing problem: n jobs each carry a processing time, a deadline, and a penalty for missing the deadline. Choose an order on a single machine that minimizes the total weighted penalty:

σ \in S_{n} min j = 1 \sum n w_{j} \cdot 1 [C_{j} (σ) > d_{j}] . (1)

Here C_j(σ) is the completion time of job j under schedule σ, and the bracketed indicator is 1 if the job finishes late, 0 otherwise. So (1) charges the penalty w_j for each missed deadline and asks for the order that pays least.

Form (1) is NP-hard via reduction from partition. Special cases — unit times, identical penalties, agreeable weights — admit polynomial greedy solutions (Moore–Hodgson, EDF). The general case is one of the most-studied scheduling problems and the gateway to modern scheduling theory.

Figures, in plain terms

(1)

min over σ ∈ S_n is the same permutation-search idea from chapter 8. σ is one specific ordering of the n jobs; S_n is the set of all such orderings; we pick the cheapest.

Σ from j=1 to n sums one term per job. Same big-Σ as in knapsack, summing across an index range.

The term w_j · 1[C_j(σ) > d_j] is a weighted indicator. The bracket 1[condition] is the indicator function — it equals 1 if the condition is true, 0 if false.

The condition C_j(σ) > d_j asks whether job j's completion time (under schedule σ) exceeds its deadline d_j. So the indicator is 1 if the job missed its deadline, 0 if not.

Multiplying by w_j charges the per-miss penalty for job j. Summing across all j gives total penalty. Take the schedule that minimizes that total — that's the answer.