Question 8 of 8: Rebalancing 14 Jobs Across Three Surface-Mount Machines, and Minimum Workforce

Question 8: Rebalancing 14 Jobs Across Three Surface-Mount Machines, 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) shown once regardless of which machine runs it (the three machines have “similar capabilities,” so a job’s time does not depend on its assigned machine); three identical parallel machines A, B, C; target completion within 3.5 hours ($12{,}600$ s). No individual due dates are given, so every job is taken to share the 3.5-h due date $d=12{,}600$ s. The lateness of job $j$ is $L_j=C_j-d$, so the worst lateness is $L_{max}=C_{max}-d$, and minimizing it is the same as minimizing the makespan $C_{max}$.

Find. (a) A rebalanced schedule that minimizes the worst lateness against the 3.5-hour (12,600 s) target, and whether that target can be met; (b) the minimum operator headcount needed to staff this facility under the stated shift and days-off rules.

Approach. The initial allocation is badly imbalanced (Machine B alone totals 26,200 s $=7.3$ h, about double the deadline, while C sits at only 5,600 s), so find the theoretical lower bound on makespan, search for a job-to-machine assignment achieving it, then size the workforce from two lower bounds (days off per week, and weekends off per five weeks) and a rota that meets the larger one.

1. Lower bound. Total work content across all 14 jobs is $\sum_jp_j=43{,}200$ s; with 3 identical parallel machines, no assignment can beat $$C_{max}\ge\left\lceil\frac{43{,}200}{3}\right\rceil=\boxed{14{,}400\ \text{s}}.$$ This bound is already above the 3.5-h target ($14{,}400>12{,}600$ s), so no schedule can finish all jobs in 3.5 hours. The best possible is to reach the bound, 4 hours, if a perfectly balanced 3-way partition of these 14 job times exists.
2. Rebalanced assignment (part a). An exhaustive branch-and-bound search over 3-way partitions of the 14 jobs (minimizing the largest machine load) finds a partition that exactly hits the lower bound: $$\text{A: B6183, B4056, B8212, B1910}\ (6{,}000+4{,}300+2{,}900+1{,}200=14{,}400\text{ s})$$ $$\text{B: B7982, B1184, B2401, B9989, B3311}\ (4{,}400+3{,}800+3{,}200+1{,}800+1{,}200=14{,}400\text{ s})$$ $$\text{C: B1847, B6298, B9455, B4813, B7214}\ (4{,}300+4{,}300+3{,}800+1{,}000+1{,}000=14{,}400\text{ s})$$ giving $C_{max}=14{,}400$ s (4 h 0 min) on all three machines, equal to the lower bound and therefore optimal. The worst lateness against the 3.5-h target is $$\boxed{L_{max}=14{,}400-12{,}600=1{,}800\ \text{s}\ (30\ \text{min})},$$ the least possible. The job order within a machine does not change $L_{max}$; sequencing shortest-first (SPT) on each machine minimizes how many jobs finish after 3.5 h. This 4-hour schedule is the “proposed four-hour schedule” used in part (b). Method: compute the averaging bound, then search job assignments (largest job first, placed on each machine in turn, pruning any branch whose largest load already reaches the best found) until a partition meets the bound.
3. Minimum workforce (part b). Three machines, each needing one operator per shift, times three 8-hour shifts/day, seven days/week, gives a constant requirement of $R=3\times3=9$ operators every day (one shift each). Two lower bounds apply:
   Days-off bound. Each operator needs two days off in every seven, so works at most 5 of 7 days: $5N\ge7R=63\Rightarrow N\ge\lceil12.6\rceil=13$.
   Weekend bound. Every Saturday needs 9 operators, so a 5-week cycle needs $5\times9=45$ Saturday shifts. Each operator must have at least 2 full weekends off in 5 weeks, so works at most 3 of the 5 Saturdays: $3N\ge45\Rightarrow N\ge15$ (Sundays give the same bound). $$N\ge\max(13,\ 15)=\boxed{15\ \text{operators}}.$$ A 15-person rota that meets it. Form 5 crews of 3. In week $k$ ($k=1\ldots5$), crews $k$ and $k+1$ (cyclically) take the weekend off, so 3 crews (9 operators) work every weekend and each crew gets exactly 2 weekends off in 5. Each crew also rests the same two weekdays every week: crews 1 and 2 Mon+Tue, crew 3 Wed+Thu, crew 4 Thu+Fri, crew 5 Wed+Fri. That leaves exactly 3 crews (9 operators) on duty each weekday. Within a working crew, one operator takes each shift. Because every crew rests a fixed pair of weekdays, any 7 consecutive days contain at least two of its days off, so the rule holds for rolling weeks as well as calendar weeks.