Question 7 of 7: Circuit-Board Job Scheduling and Minimum Workforce

Question 7: Circuit-Board Job Scheduling and Minimum Workforce (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), pre-assigned to one of three non-interchangeable machines A, B, C; target completion within 4 hours ($14{,}400$ s). No individual job due dates are stated, so “minimize the average lateness” is read as minimizing the makespan (last-machine completion time) if the 4-hour target cannot be hit, or simply hitting it exactly if it can.

Find. (a) A rebalanced job-to-machine schedule meeting the 4-hour target if possible; (b) the minimum operator headcount for a 3-machine, 3-shift/day, 7-day/week operation under the stated days-off rules.

Approach. The initial allocation is badly imbalanced (Machine B carries $26{,}200$ s, over $7.2$ hours, versus C's $5{,}600$ s), so find the theoretical makespan lower bound, search for a job-to-machine partition achieving it, then size the workforce with the days-off (Tibrewala–Philippe–Browne) formula for a constant daily requirement.

1. Lower bound. Total work content is $\sum_jp_j=11{,}400+26{,}200+5{,}600=43{,}200$ s across 3 identical-capability, non-interchangeable-only-by-job-type machines; no assignment can beat $$C_{max}\ge\left\lceil\frac{43{,}200}{3}\right\rceil=\boxed{14{,}400\ \text{s}},$$ which lands exactly on the manager's 4-hour deadline.
2. Rebalanced assignment (part a). An exhaustive branch-and-bound search over 3-way partitions of the 14 job times finds a partition that exactly hits the lower bound on all three machines: $$\text{A: B6103, B4006, B8212, B1910}\ (6{,}000+4{,}300+2{,}900+1{,}200=14{,}400\text{ s})$$ $$\text{B: B7902, B1104, B2401, B9909, B3311}\ (4{,}400+3{,}800+3{,}200+1{,}800+1{,}200=14{,}400\text{ s})$$ $$\text{C: B1807, B6208, B9405, B4813, B7214}\ (4{,}300+4{,}300+3{,}800+1{,}000+1{,}000=14{,}400\text{ s})$$ giving $\boxed{C_{max}=14{,}400\ \text{s}}$ on all three machines simultaneously — the 4-hour target is achievable exactly, with zero margin and zero lateness on every job.
3. Minimum workforce (part b). Three machines $\times$ three 8-hour shifts/day gives a constant daily requirement $R=3\times3=9$ operators every day of the week. By the Tibrewala–Philippe–Browne days-off formula (each operator supplies at most 5 workdays per 7-day week, matching the "no more than one shift/day, two days off in seven" rule): $$N\ge\left\lceil\frac{7R}{5}\right\rceil=\left\lceil\frac{7\times9}{5}\right\rceil=\left\lceil12.6\right\rceil=\boxed{13\ \text{operators}}.$$ This is achievable by rotating 13 operators across the 7 circular rest-day start positions (as six pairs of 2 plus one single operator), leaving at most 4 resting on any one day and always $13-4=9$ on shift; rotating each operator's rest-day position over successive weeks also satisfies the stated two-weekends-off-per-five-weeks rule without raising the headcount.