Question 7 of 7: Rebalancing 14 Jobs Across Three Surface-Mount Machines

Question 7: Rebalancing 14 Jobs Across Three Surface-Mount Machines (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; target completion within 4 hours ($14{,}400$ s). No individual job due dates are stated, so "minimize the lateness of the worst job" is read as minimizing the makespan (the completion time of the last-finishing machine).

Find. (a) A rebalanced schedule that completes all jobs within the 4-hour (14,400 s) target; (b) a better scheduling approach beyond simple machine rebalancing.

Approach. The initial allocation is badly imbalanced (Machine B alone totals 26,200 s $=7.3$ h, nearly double the deadline, while C sits at only 5,600 s), so the deadline cannot be met without reassigning jobs across machines; find the lower bound on the best possible makespan, then search for a job-to-machine assignment achieving it (or as close as feasible), and check the result against the 4-hour target.

1. Lower bound. Total work content across all 14 jobs is $\sum_jp_j=43{,}100$ s; with 3 identical parallel machines, no assignment can beat $$C_{max}\ge\left\lceil\frac{43{,}100}{3}\right\rceil=\boxed{14{,}367\ \text{s}}.$$
2. Rebalanced assignment. An exhaustive search over 3-way partitions of the 14 jobs (minimizing the largest machine load) finds: $$\text{A: B1910, B9989, B2401, B1184, B7982}\ (1{,}200+1{,}800+3{,}100+3{,}800+4{,}400=14{,}300\text{ s})$$ $$\text{B: B3311, B8212, B4056, B6183}\ (1{,}200+2{,}900+4{,}300+6{,}000=14{,}400\text{ s})$$ $$\text{C: B4813, B7214, B9455, B1847, B6298}\ (1{,}000+1{,}000+3{,}800+4{,}300+4{,}300=14{,}400\text{ s})$$ giving $\boxed{L_{max}=C_{max}=14{,}400\ \text{s}}$, only 33 s above the theoretical floor. That gap cannot be closed: every job time is a multiple of 100 s, so every machine load is too, and the smallest multiple of 100 at or above 14,367 s is 14,400 s. This schedule is therefore optimal.
3. Check against the 4-hour target. $4\ \text{h}=14{,}400$ s exactly, so this schedule meets the manager's expectation with $\boxed{0\ \text{s}}$ of margin — the last job on Machines B and C finishes at the very instant of the 4-hour deadline. Every job's lateness relative to a $d=14{,}400$ s target is $\le0$; the "worst job" (on B or C) is exactly on time, not late.

(b) A better way to schedule the machines. The rebalanced schedule above meets the deadline exactly, but with zero margin — any hiccup (a jammed feeder, a late material delivery, an operator break) on Machine B or C pushes the worst job late, since there is no slack anywhere in the schedule. Four changes would make the operation more robust without requiring the machines to run any faster: (1) Sequence within each machine by shortest-processing-time (SPT) first. $L_{max}$ (the makespan) is unaffected by the order jobs run in on a machine, but SPT-first minimizes the average flow time and average WIP across all 14 jobs — several small jobs finish early instead of waiting behind one long one, which matters if any job has a customer waiting on it individually rather than just the whole batch. (2) Lot-stream the largest batches. B6183 (batch 45, 6,000 s) and B7982 (batch 126, 4,400 s) are the two longest single jobs; splitting a large batch into sub-lots that can start moving to the next process step before the whole batch finishes reduces the effective flow time of downstream operations even though the machine's own total processing time is unchanged. (3) Build in a real time buffer instead of scheduling to the exact deadline. Since the current best schedule (14,400 s) lands precisely on the 4-hour target with no slack, propose either negotiating a small buffer into the deadline or keeping a portion of one machine's capacity in reserve (e.g., holding B6183 back as the first job addressed if any machine falls behind) so a single disruption doesn't automatically cause a miss. (4) Address the root imbalance, not just this batch. The initial allocation (A 11,300 / B 26,200 / C 5,600 s) was badly skewed toward Machine B before any rebalancing — if this pattern repeats batch after batch (e.g., because jobs are habitually routed to whichever machine is nominally "assigned" to a product family rather than by current load), the real fix is a dynamic, load-aware dispatching rule for future batches, not a one-time manual rebalancing exercise each time a new job list arrives.