Rebalancing 14 Jobs Across Three Surface-Mount Machines, and Minimum Workforce: 23-Ind-A4 Production Management, December 2017, 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 processing times, including the “initial” imbalanced allocation totalling A 11,300 / B 26,200 / C 5,600 s) and the explicit 4-hour completion target are as given in the question. Part (a)'s rebalanced schedule below meets a 14,400 s makespan. Part (b)'s workforce calculation uses days-off scheduling bounds: the naive “5 crews per position” estimate (45) is far too high, and the plain workday bound (13) is too low because it ignores the weekends-off rule (see step 3 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).

Job	Batch size	Time (s)	Initial machine
B2401	72	3,100	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,300 / B 26,200 / C 5,600

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 two days-off lower bounds (workdays per week, and weekends off per 5 weeks) and show the larger one is achievable.

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}}.$$
Rebalanced assignment. An exhaustive branch-and-bound search over 3-way partitions of the 14 jobs (minimizing the largest machine load) finds: $$\text{A: B2401, B6183, B4056, B4813}\ (3{,}100+6{,}000+4{,}300+1{,}000=14{,}400\text{ s})$$ $$\text{B: B7982, B1184, B1847, B9989}\ (4{,}400+3{,}800+4{,}300+1{,}800=14{,}300\text{ s})$$ $$\text{C: B9455, B6298, B1910, B3311, B8212, B7214}\ (3{,}800+4{,}300+1{,}200+1{,}200+2{,}900+1{,}000=14{,}400\text{ s})$$ giving $\boxed{L_{max}=C_{max}=14{,}400\ \text{s}}$, only 33 s above the theoretical floor. Because every job time is a multiple of 100 s, every machine load is too, so no schedule can finish before the next multiple of 100 s above 14,367 s — 14,400 s is therefore provably optimal. This 4-hour cycle meets the manager's target with $\boxed{0\ \text{s}}$ of margin.
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, at most 5 days in a row”. Two lower bounds apply, and the larger one governs.
Workday bound. A full-time 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, Fri–Tue for a Wed+Thu crew), and a weekend off only shortens runs, so every rule holds. Hence $$\boxed{N_{min}=15\ \text{operators}}.$$

Machine	Job set	Load (s)
A	B2401, B6183, B4056, B4813	14,400
B	B7982, B1184, B1847, B9989	14,300
C	B9455, B6298, B1910, B3311, B8212, B7214	14,400
Makespan (part a)	14,400 s = 4 h 0 min (meets deadline, 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$, 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)$ (Baker; Burns & Carter).

Why this works. The makespan bound is a simple averaging argument (no partition can beat the average load per machine); the days-off bound is the same 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.

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)