Question 8 of 8: Rebalancing 14 Jobs Across Three Surface-Mount Machines

Question 8: Rebalancing 14 Jobs Across Three Surface-Mount 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, 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 4 hours ($14{,}400$ s). No individual job due dates are stated, so “minimize the lateness of the worst job” is read as minimizing the makespan (the completion time of the last-finishing machine).

Find. (a) A rebalanced schedule that completes all jobs within the 4-hour (14,400 s) target; (b) the minimum full-time-equivalent 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, nearly 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 the stated shift pattern and days-off constraints.

1. Lower bound. Total work content across all 14 jobs is $\sum_jp_j=43{,}100$ s; with 3 identical parallel machines, no assignment can beat $$C_{max}\ge\left\lceil\frac{43{,}100}{3}\right\rceil=\boxed{14{,}367\ \text{s}}.$$
2. Rebalanced assignment. An exhaustive search over 3-way partitions of the 14 jobs (minimizing the largest machine load) finds: $$\text{A: B1910, B9989, B2401, B1184, B7982}\ (1{,}200+1{,}800+3{,}100+3{,}800+4{,}400=14{,}300\text{ s})$$ $$\text{B: B3311, B8212, B4056, B6183}\ (1{,}200+2{,}900+4{,}300+6{,}000=14{,}400\text{ s})$$ $$\text{C: B4813, B7214, B9455, B1847, B6298}\ (1{,}000+1{,}000+3{,}800+4{,}300+4{,}300=14{,}400\text{ s})$$ giving $\boxed{L_{max}=C_{max}=14{,}400\ \text{s}}$, only 33 s above the theoretical floor. Every job time is a multiple of 100 s, so every machine load is too. The smallest multiple of 100 at or above 14,367 s is 14,400 s, so this makespan is provably optimal. This 4-hour cycle meets the manager's target with $\boxed{0\ \text{s}}$ of margin. The sequence within each machine does not change the makespan. Running each machine's jobs shortest-first (as listed) also minimizes that machine's mean flow time.
3. Minimum workforce (part b). Three machines, each needing one full-time operator per running shift, times three 8-hour shifts/day, seven days/week $=3\times3=9$ operators on duty every day, $R=9$. Operators are interchangeable across machines and shifts, and each works at most one shift per day, so the task is to find the fewest people who can supply 9 working days on every calendar day.
   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 the 5 weeks, so each can work at most 3 of the 5 Saturdays: $3N\ge45\Rightarrow N\ge15$. The same holds for Sundays.
   Weekly-hours bound. The plant needs $7\times9=63$ shifts per week. The 5-days-in-a-row limit allows at most about 6 shifts per operator per week, which gives only $N\ge11$, so the weekend rule governs.
   A 15-person rota that works. Form 5 crews of 3 operators. 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 every weekday. Within a working crew, one operator takes each of the three shifts. A full 35-day cyclic check confirms that no operator works more than 5 days in a row. For example, crew 3 works Fri–Sat–Sun–Mon–Tue and then rests Wed+Thu. $$\boxed{\text{Minimum workforce}=15\ \text{operators}}.$$ The rule of thumb of 5 people per round-the-clock position ($9\times5=45$) overstates the need three-fold. It gives every machine-shift position its own dedicated crew, when operators can in fact cover any machine on any shift.