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. A quick proof that nothing better exists: every job time is a multiple of 100 s, so every machine load is too, and the smallest multiple of 100 s at or above the 14,367 s floor is 14,400 s. The optimal schedule:

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. On this minimum-makespan schedule it also gives the fewest late jobs: one per machine, three of fourteen overall. All other eleven jobs finish by the 3.5-hour deadline. Within each machine, the rule is to let the largest job on that machine be the one delivered late. Delaying a smaller job ahead of it would only add lateness without reducing the count. Across the whole schedule, though, fewer late jobs is not automatically better. You can make just ONE job late: load two machines to at most 12,600 s each and put every overrun behind one large job, such as B6183, on the third machine. That third machine then runs to $43{,}100-2\times12{,}600=17{,}900$ s (almost 5 h), so the single late job is about 5,300 s late or more and the makespan grows. The choice depends on what "customers may be lost" means for each order. If each late customer is equally at risk, whatever the delay, the one-late-job plan loses the fewest customers. If the risk grows with how late an order is, the balanced three-late-job plan above is better. In practice, weight each job by its customer's importance (value, contract penalty, relationship), always finish the high-weight jobs on time, and choose the low-weight jobs to absorb the unavoidable 5,300 s of overrun.

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