Question 7 of 7: Circuit-Board Job Scheduling Across Three Machines

Question 7: Circuit-Board Job Scheduling Across Three 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 with a fixed processing time each (seconds), initially allocated as shown; the manager's target completion is 4 hours $=14{,}400$ 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) with makespan as close as possible to 14,400 s; (b) the average tardiness of that schedule against the 4-hour due date; (c) whether the makespan can be pushed below 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 treat this as an identical-parallel-machine load-balancing problem: total the 14 job times, compare to the 3-way theoretical minimum, then reassign jobs (respecting none of the original per-machine grouping, since the machines are stated to have similar capabilities) to bring every machine's load as close to the 14,400 s target as the job sizes allow.

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, about 33 s under the 4-hour target itself.
2. Rebalance the jobs. 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}}$ — landing precisely on the 4-hour target, only 33 s above the theoretical floor from Step 1:

3. Average tardiness (part b). Tardiness is a job measure: with the common due date $d=14{,}400$ s, each job $j$ has $T_j=\max(0,C_j-d)$. No job can complete later than its machine's last job, and the machine finish times are $C_A=14{,}400$, $C_B=14{,}300$, $C_C=14{,}400$ s, so every one of the 14 jobs has $C_j\le14{,}400$ s whatever the sequence on each machine: $$T_j=0\ \ (j=1,\dots,14)\ \Rightarrow\ \boxed{\bar T = \frac{1}{14}\sum_j T_j=0\ \text{s}}.$$ Every job finishes at or before the 4-hour target, so the schedule has zero average tardiness — a direct benefit of rebalancing away from the original allocation, where Machine B alone (26,200 s $\approx7.3$ h) would have been almost 3.3 h tardy.

(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 the 4-hour target 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 is to change the problem itself — e.g. 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.