Question 5 of 9: Dynamic Programming — Single-Machine Job Sequencing to Minimize Tardiness Cost
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — May 2013 — 98-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 180 marks across 9 questions and only 100 marks are required, so a candidate would normally answer a subset — all nine 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; Niebel & Freivalds, Niebel's Methods, Standards, and Work Design (13th ed.) — job-shop sequencing context.
Given. Single machine, jobs process one at a time with no preemption.
Job
Processing time $p_j$ (days)
Due date $d_j$ (days from now)
A
2
4
B
4
14
C
6
10
D
8
16
Penalty: $100 per day a job's completion exceeds its due date. Total processing time $\sum p_j=20$ days.
Find. The job sequence minimizing total tardiness cost, by dynamic programming.
Approach. Because jobs run back-to-back on one machine, the completion time of any subset $S$ scheduled together is fixed at $C(S)=\sum_{j\in S}p_j$ regardless of order — only which job finishes last in $S$ affects that job's own tardiness. This gives a subset-DP (state = set of jobs already sequenced) with $2^4=16$ states instead of $4!=24$ full permutations.
State and recursion. Let $f(S)$ = minimum total tardiness cost to sequence the jobs in $S$ among themselves (in some order), and $C(S)=\sum_{j\in S}p_j$. The last job $j$ scheduled in $S$ completes exactly at $C(S)$, so
$$f(S)=\min_{j\in S}\Big[f(S\setminus\{j\}) + 100\max\big(0,\,C(S)-d_j\big)\Big],\qquad f(\varnothing)=0.$$
Build up by subset size. All singletons finish on or before their due date ($f=0$ for each of A, B, C, D — e.g. job D alone: $C=8\le16$). All 2- and 3-job subsets also turn out tardiness-free except $\{B,C,D\}$: $C=18$, and scheduling $D$ last there costs $100(18-16)=200$ (scheduling $B$ or $C$ last is worse or infeasible-checked and not better), so $f(\{B,C,D\})=200$.
Full set $\{A,B,C,D\}$, $C=20$. Try each job last:
$j=A$: $f(\{B,C,D\})+100\max(0,20-4)=200+1600=1800$.
$j=B$: $f(\{A,C,D\})+100\max(0,20-14)=0+600=600$.
$j=C$: $f(\{A,B,D\})+100\max(0,20-10)=0+1000=1000$.
$j=D$: $f(\{A,B,C\})+100\max(0,20-16)=0+400=\mathbf{400}$.
Minimum is $j=D$ last, cost $400$.
Backtrack the optimal order. With D last, solve $f(\{A,B,C\})=0$ (need its last job too): trying each, $j=B$ last gives $f(\{A,C\})+100\max(0,12-14)=0+0=0$ (an optimal tie; B or C or A can go last here since all finish on time) — take $j=B$ last, then $f(\{A,C\})$: $j=C$ last gives $f(\{A\})+100\max(0,8-10)=0$, so $C$ before $B$; then $f(\{A\})$ trivially places $A$ first.
$$\boxed{\text{Optimal sequence: } A \to C \to B \to D,\qquad \text{minimum total tardiness cost}=\$400.}$$
Check directly. A finishes at $2\ (\le4$, on time$)$; C finishes at $2+6=8\ (\le10$, on time$)$; B finishes at $8+4=12\ (\le14$, on time$)$; D finishes at $12+8=20$, which is $20-16=4$ days late $\Rightarrow 4\times100=\$400$. Matches step 3.
