Question 7 of 7: Circuit-Board Job Scheduling Against a 3.5-Hour Deadline

Question 7: Circuit-Board Job Scheduling Against a 3.5-Hour Deadline (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 with a fixed processing time each (seconds), initially allocated as shown; the manager's target completion is 3.5 hours $=12{,}600$ s per machine. Machines are interchangeable (similar capabilities), so any job's processing time is the same regardless of which of the three machines runs it.

Find. (a) A rebalanced schedule (job-to-machine assignment) for the jobs; (b) if the 3.5-hour deadline cannot be met, a defensible method for choosing which jobs run late; (c) whether the makespan can be pushed below 4 hours (14,400 s), with justification.

Approach. The initial allocation is badly unbalanced (Machine B alone carries 26,200 s, more than 7 hours, while C sits at 5,600 s), so first check the 3.5-hour target against the theoretical work-content floor before attempting a schedule; if the target is provably unreachable, rebalance to the true minimum makespan instead, then decide which jobs must run late using a due-date-minimizing sequencing rule.

1. Total work content and lower bound. Summing all 14 job times: $3100+4400+6000+3800+3800+4300+4300+4300+1800+1200+1200+2900+1000+1000=\boxed{43{,}100\ \text{s}}$. Spread perfectly evenly across 3 machines this is $43{,}100/3=14{,}366.7$ s, so no machine can possibly finish before $$\boxed{\lceil 43{,}100/3\rceil = 14{,}367\ \text{s}}$$ — a firm lower bound on the makespan. Comparing this floor to the stated 3.5-hour deadline, $12{,}600$ s: $$14{,}367\ \text{s} > 12{,}600\ \text{s},$$ so the 3.5-hour target is provably infeasible, regardless of how the 14 jobs are assigned or sequenced — no rebalancing exists that meets it.
2. Rebalance the jobs to the true minimum makespan (part a). Since 3.5 hours cannot be hit, the best achievable schedule is the one that minimizes the makespan outright. Searching all ways to partition the 14 jobs across 3 machines (an exhaustive assignment search, tractable at this size) for the assignment that minimizes the largest machine load finds a schedule whose worst machine is exactly $\boxed{14{,}400\ \text{s}}$ — only 33 s above the theoretical floor from Step 1:

3. Choosing which jobs run late (part b). Because every machine's load (14,300–14,400 s) unavoidably exceeds the 12,600 s deadline, at least $$43{,}100-3\times12{,}600=\boxed{5{,}300\ \text{s}}$$ of processing must occur after the deadline on some job, no matter how work is assigned or sequenced (this is the same work-content argument as Step 1, applied to the deadline instead of to a bare lower bound). The choice of which jobs absorb that unavoidable 5,300 s is a sequencing decision: on each machine, run jobs in shortest-processing-time (SPT) order. Because SPT front-loads the small jobs, the cumulative time stays under 12,600 s for as long as possible, and only the single largest job on each machine is pushed past the cutoff (Figure 2, red segments) — B7982 (4,400 s) on Machine A finishes at 14,300 s, 1,700 s late; B6183 (6,000 s) on Machine B finishes at 14,400 s, 1,800 s late; B6298 (4,300 s) on Machine C finishes at 14,400 s, 1,800 s late. Summing these three: $1{,}700+1{,}800+1{,}800=5{,}300$ s — exactly the unavoidable total from the work-content argument, confirming this schedule achieves the minimum possible total tardiness, with only one late job per machine (three of fourteen) and the minimum makespan. All other eleven jobs complete on or before the 3.5-hour deadline. The rule to apply on a fixed machine loading is: let exactly one job per machine absorb that machine's overrun, never split the overrun across several jobs. SPT puts the largest job last, but it is not the only valid choice: any job at least as long as the machine's overrun can be sequenced last with the same tardiness (on Machine A, any of B9989, B2401, B1184 or B7982 can take the 1,700 s). So the practical choice of which job is late should be made by customer priority (weighted tardiness, e.g. WSPT with customer-importance weights): put the least critical eligible job last. Two scope notes. First, the "three late jobs" count is minimal only for this minimum-makespan loading. If the makespan is allowed to grow, as few as one job need be late: load A = B7982+B4056+B8212+B4813 = 12,600 s and B = B1847+B6298+B9989+B1910+B7214 = 12,600 s, and put B2401+B1184+B9455+B3311 (11,900 s) then B6183 on C. B6183 then finishes at 17,900 s, 5,300 s late: the same total tardiness, but one customer waits almost 1.5 h longer. Second, which option is better depends on whether the manager cares more about how many customers are late or about how late the worst one is.

(c) Can the makespan go below 4 hours? No. The exhaustive rebalancing search in Step 2 already found the true minimum achievable makespan across every possible 3-way job assignment, and it is exactly 14,400 s — equal to 4 hours and only 33 s above the 14,367 s theoretical floor from Step 1. The floor itself cannot be reached because the job durations are indivisible lumps (the largest, B6183 at 6,000 s, cannot be split across machines) that do not combine into three exactly-equal 14,366.7 s groups; 14,400 s is the closest any combination gets. Since a full search over every assignment already confirms no combination beats 14,400 s, the only way to genuinely go below 4 hours — or, more urgently, to close in further on the stated 3.5-hour target — is to change the problem itself: split a large batch (such as B6183's 45-unit batch) across two machines if the surface-mount process allows a batch to be divided, add a fourth machine or a shift of overtime capacity, or negotiate a same-day subcontract for the smallest jobs — none of which is possible within the "reassign among the existing three machines" scope the question asks for.