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 SPT achieves the minimum possible total tardiness; and because every machine in this makespan-minimizing schedule is loaded above 12,600 s, one late job per machine (three of fourteen overall) is the fewest this schedule allows. All other eleven jobs complete on or before the 3.5-hour deadline. This is the rule to apply: always let the single largest job on each machine be the one delivered late, never a smaller job ahead of it in the SPT order, since delaying a smaller job instead would only increase total lateness without reducing the count of late jobs. If the manager cares more about how many customers are let down than about the makespan, a different assignment is possible: load two machines to at most 12,600 s and put all the overrun on the third machine behind one large job (e.g. B6183, whose 6,000 s exceeds the 5,300 s unavoidable overrun). Only one job is then late, but that machine runs to at least $43{,}100-2\times12{,}600=17{,}900$ s and the single late job is at least 5,300 s late. The choice between the two schedules is a customer-priority decision: weight each candidate late job by its customer's importance or lost-sale penalty (weighted tardiness) and pick the schedule with the lower weighted cost.

(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.