Rebalancing 14 Jobs Across Three Surface-Mount Machines, and Minimum Workforce: 23-Ind-A4 Production Management, December 2018, Q8

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.

Check — 14-job data set and deadline

The 14-job data set (batch sizes, and the workforce shift/days-off rules) is as printed; job B2401's processing time is $3{,}200$ s, consistent with the printed initial-machine total of A $=11{,}400$ s. Total work content is 43,200 s, which happens to be exactly divisible by 3, so the theoretical lower bound on makespan is exactly $14{,}400$ s — precisely the manager's 4-hour target. The rebalanced assignment is solved below; the part-(b) workforce calculation does not depend on job times: the plain workday bound (13) ignores the weekends-off rule, which raises the minimum to 15.

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

Job	Batch size	Time (s)	Initial machine
B2401	72	3,200	A
B7982	126	4,400	A
B6183	45	6,000	B
B1184	110	3,800	A
B9455	240	3,800	C
B4056	32	4,300	B
B1847	32	4,300	B
B6298	32	4,300	B
B9989	192	1,800	C
B1910	64	1,200	B
B3311	64	1,200	B
B8212	32	2,900	B
B4813	64	1,000	B
B7214	64	1,000	B
Initial totals			A 11,400 / B 26,200 / C 5,600

Find. (a) A rebalanced schedule that completes all jobs within the 4-hour (14,400 s) target if at all possible; (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 with days-off scheduling bounds (5-day week and weekends-off rule) for a constant daily requirement.

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 lower bound lands exactly on the manager's 4-hour target — so “if possible” hinges on whether a perfectly balanced 3-way partition of these 14 specific job times actually exists, not merely on a close approximation.
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 $\boxed{L_{max}=C_{max}=14{,}400\ \text{s}}$ on all three machines simultaneously — the manager's 4-hour target is achievable exactly, with zero margin and zero lateness on every job.
Minimum workforce (part b). Three machines, each needing one full-time operator per shift, times three 8-hour shifts/day, seven days/week, gives a constant daily requirement of $R=3\times3=9$ operators every day of the week. This is a days-off scheduling problem with a weekends-off rule (Baker; Burns & Carter): “at least $A=2$ weekends off in every $B=5$ weeks, two days off in every seven days”. Two lower bounds apply, and the larger one governs.
Workday bound. An operator works at most 5 of every 7 days, so $5N\ge7R$ and $N\ge\lceil63/5\rceil=13$.
Weekend bound. Over any 5 consecutive weeks there are 5 Saturdays, each needing 9 operators: $5\times9=45$ operator-Saturdays. An operator with 2 full weekends off can work at most $B-A=3$ of those Saturdays, so $$N\ge\left\lceil\frac{B\,R}{B-A}\right\rceil=\left\lceil\frac{5\times9}{3}\right\rceil=15.$$ With 13 operators only $13\times3=39<45$ Saturday shifts could be staffed, so the weekends-off rule, not the 5-day week, sets the minimum.
15 is achievable. Split the 15 operators into five crews of 3. (i) Weekends: in week $k$ crews $k$ and $k+1$ (cyclically, mod 5) take Saturday and Sunday off, so $15-6=9$ work every weekend day, and each crew has exactly 2 weekends off in every 5 weeks. (ii) Weekdays: each crew keeps the same two weekday rest days every week — crews 1–2 Mon+Tue, crew 3 Wed+Thu, crew 4 Thu+Fri, crew 5 Wed+Fri — so exactly 6 operators rest each weekday and 9 work. The longest possible run of work days is 5 (e.g. Wed–Sun for a Mon+Tue crew), so every rolling 7-day window holds at least 2 days off, and a weekend off only adds rest. Hence $$\boxed{N_{min}=15\ \text{operators}}.$$

Figure 2 — Rebalanced load-balanced assignment meeting the 4-hour target exactly: Machine A, B, C each 14,400 s.

Machine	Job set	Load (s)
A	B6183, B4056, B8212, B1910	14,400
B	B7982, B1184, B2401, B9989, B3311	14,400
C	B1847, B6298, B9455, B4813, B7214	14,400
Makespan (part a)	14,400 s = 4 h 0 min on all three machines (meets deadline exactly, 0 s margin)
Minimum workforce (part b)	15 operators (weekend bound $\lceil5\times9/3\rceil$ governs; 5 crews of 3)

Concept & Theory

Topic. Parallel-machine load-balancing to minimize makespan, and days-off workforce scheduling for a constant daily staffing requirement.

Key relations. Makespan lower bound $C_{max}\ge\lceil\sum p_j/m\rceil$ for $m$ identical parallel machines; minimum days-off workforce for constant daily requirement $R$ with a 5-day workweek and $A$ weekends off in every $B$ weeks, $N\ge\max\left(\lceil7R/5\rceil,\ \lceil BR/(B-A)\rceil\right)$.

Why this works. The makespan bound is a simple averaging argument (no partition can beat the average load per machine); a perfectly divisible total work content (here, exactly $3\times14{,}400$) is what makes the bound achievable with zero slack rather than merely approachable. The days-off bound is the same averaging idea applied to labour-days instead of machine-seconds — 7 requirement-days per week can be supplied by at most 5 workdays per operator, and $B$ weekends of demand can be supplied by at most $B-A$ working weekends per operator. Whichever bound is larger governs, and an explicit crew rota shows it is achievable, not just a theoretical floor.

Common pitfall. Sizing workforce as “5 dedicated crew members per position” ($3\text{ machines}\times3\text{ shifts}\times5=45$) by treating each of the 9 daily positions as needing its own independent rotating team; this massively overstates the requirement because operators are interchangeable across positions from day to day — the correct question is the total labour-days needed per week ($7R=63$) divided by what one operator can supply ($5$ days), not five dedicated bodies per position. The opposite trap is stopping at $\lceil7R/5\rceil=13$, which ignores the weekends-off rule; that rule needs 15. Separately, assuming a lower bound that happens to equal a stated target is automatically infeasible to reach exactly — here it is exactly reachable, but only a real partition search (not just the averaging argument) confirms that.

Source. Pinedo, Scheduling: Theory, Algorithms, and Systems, Ch. 3 (parallel-machine scheduling); Nahmias & Olsen, Production and Operations Analysis, Ch. 3 (days-off/workforce scheduling).

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)