Question 7 of 10: Dynamic Programming — Single-Machine Job Sequencing
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — December 2013 — 98-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 200 marks across 10 questions and only 100 marks are required, so a candidate would normally answer a subset — all ten are solved below for completeness.
Reference texts: Hillier & Lieberman, Introduction to Operations Research (11th ed., McGraw-Hill) — linear/integer programming, network optimization, dynamic programming, decision analysis and queueing theory; Nahmias, Production and Operations Analysis — inventory models with planned backorders.
This job-sequencing dataset (processing times 2, 4, 6, 8 days; due dates 4, 14, 10, 16 days. The dynamic-programming recursion, optimal sequence and minimum cost below are recomputed independently here and match that solution exactly.
Given. Single machine, no preemption; jobs $A,B,C,D$ with processing times $p=2,4,6,8$ days and due dates $d=4,14,10,16$ days from now; penalty $100 per day a job's completion time exceeds its due date.
Job
$p$ (days)
$d$ (due, days)
A
2
4
B
4
14
C
6
10
D
8
16
Find. The job sequence minimizing total tardiness penalty, via a dynamic-programming recursion over subsets.
Approach. Because total tardiness cost with a common processing order depends only on which jobs have been scheduled so far (their total processing time) and not the order among them (a classical single-machine scheduling result), define a DP state as the set of jobs already sequenced and recurse over which job is scheduled last in that set.
State and recursion. For a subset $S$ of jobs, let $C(S)=\sum_{j\in S}p_j$ (total processing time if $S$ is scheduled contiguously first) and $f(S)$ = minimum total penalty to sequence exactly the jobs in $S$ (in some order, occupying the first $C(S)$ machine-days). The Held–Karp-style recursion picks which job $j\in S$ goes last within $S$:
$$f(S)=\min_{j\in S}\Big\{f(S\setminus\{j\})+100\max(0,\,C(S)-d_j)\Big\},\qquad f(\varnothing)=0.$$
Build up from singletons. $f(\{A\})=100\max(0,2-4)=0$; $f(\{B\})=100\max(0,4-14)=0$; $f(\{C\})=100\max(0,6-10)=0$; $f(\{D\})=100\max(0,8-16)=0$ — no job is late on its own.
Grow subsets up to $\{A,B,C,D\}$ (16 states total; full table), taking the minimum over which job finishes each subset last. The full-set optimum is reached with $D$ scheduled last:
$$f(\{A,B,C,D\})=\min_{j}\{f(\{A,B,C,D\}\setminus\{j\})+100\max(0,20-d_j)\}.$$
Optimal sequence. Tracing back the minimizing choice at each level recovers the order:
$$\boxed{A\to C\to B\to D}$$
Completion times: $A$ at day 2 (due 4, on time); $C$ at day $2+6=8$ (due 10, on time); $B$ at day $8+4=12$ (due 14, on time); $D$ at day $12+8=20$ (due 16, 4 days late).
Total penalty.
$$\boxed{\text{Total cost}=100\times4=\$400.}$$
This matches the brute-force check over all $4!=24$ permutations.
