Question 7 of 7: Mathematical-Programming Model to Minimize the Worst Job's Lateness

Question 7: Mathematical-Programming Model to Minimize the Worst Job's Lateness (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Fourteen jobs, each with a fixed processing time (seconds) shown once regardless of which machine runs it (the three machines have "similar capabilities," so a job's time does not depend on its assigned machine); three identical parallel machines A, B, C. No individual job due dates or a common deadline are stated on this sitting.

Find. A mathematical programming (mixed-integer) model whose decision variables and constraints schedule the 14 jobs across the 3 machines to minimize the lateness of the single worst-off job.

Approach. Lateness is formally $L_j=C_j-d_j$, the completion time of job $j$ minus its due date; since no per-job or common due date is stated on this sitting, the model below treats the unstated due date as $d_j=0$ for every job — the standard convention when a scheduling problem gives no due dates — which collapses "minimize the lateness of the worst job" exactly to "minimize the makespan," $L_{max}=\max_j(C_j-0)=C_{max}$. The formulation is built generally (with an explicit $d_j$ term) so it is ready to use unchanged the moment real due dates are supplied, then solved as a bonus numeric check using the given processing-time data.

1. Decision variables. For each job $j=1,\dots,14$ and machine $k\in\{A,B,C\}$: $x_{jk}\in\{0,1\}=1$ if job $j$ is assigned to machine $k$. $C_k\ge0$ = completion time (total load) of machine $k$. $L_{max}\ge0$ = the lateness of the worst job (the objective).
2. Assignment constraints. Every job runs on exactly one machine: $$\sum_{k\in\{A,B,C\}}x_{jk}=1\qquad\forall j=1,\dots,14.$$
3. Machine load / completion time. Each machine's completion time is the sum of the processing times $p_j$ of every job assigned to it (all jobs on a machine run back-to-back with no idle time in an optimal single-stage schedule): $$C_k=\sum_{j=1}^{14}p_j\,x_{jk}\qquad\forall k\in\{A,B,C\}.$$
4. Worst-job lateness. With every job sharing due date $d_j=d=0$ (unstated on this sitting), the lateness of the job that finishes last on machine $k$ equals $C_k-d$; the worst job overall is on whichever machine has the largest completion time: $$L_{max}\ge C_k-d\qquad\forall k\in\{A,B,C\}.$$
5. Objective. Minimize the worst job's lateness: $$\boxed{\min L_{max}}\quad\text{s.t. the constraints above, } x_{jk}\in\{0,1\},\ C_k,L_{max}\ge0.$$ This is the standard $P||C_{max}$ (identical parallel-machine makespan-minimization) mixed-integer formulation; if real due dates $d_j$ were supplied, only Step 4's right-hand side would change to $d_j$ (evaluated per job, not per machine), and a job-level lateness variable $L_j=C_j-d_j$ would replace the machine-level $C_k-d$ term.

Bonus numeric validation. Solving the model above with the given processing-time data (not required by the question, but a useful check that the formulation is well-posed and achievable) gives the following. The total work content is $\sum_j p_j=43{,}100$ s, giving a lower bound $C_{max}\ge\lceil43{,}100/3\rceil=14{,}367$ s that no assignment can beat; an exhaustive search over 3-way partitions of the 14 jobs achieves $\boxed{L_{max}=C_{max}=14{,}400\ \text{s}}$ (Machine A 14,300 s; Machine B 14,400 s; Machine C 14,400 s), only 33 s above the theoretical floor — confirming the model in Steps 1–5 is both feasible and tight against the data.