Question 8 of 8: Rebalancing 14 Jobs Across Three Surface-Mount Machines, and Minimum Workforce
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Technical Examinations — May 2018 — 17-Ind-A4 Production Management. Three-hour, closed-book exam; Casio or Sharp approved calculators only. Format: eight questions, each worth 20 marks (sub-part weights 10/10 as tabulated on the front-page marking scheme); candidates do two questions from Section A and three from Section B, and only the first five questions appearing in the answer book are marked. All eight are solved below for completeness. The paper asks for point-form answers wherever possible; the solutions below use full working for clarity.
Reference texts: Nahmias & Olsen, Production and Operations Analysis (7th ed., Waveland/McGraw-Hill) — forecasting, inventory (EOQ/EPQ) and aggregate planning; Sipper & Bulfin, Production: Planning, Control, and Integration — production scheduling, JIT/kanban and shop-floor implementation gaps; Hillier & Lieberman, Introduction to Operations Research (11th ed.) — LP formulation and project scheduling (CPM/PERT); Pinedo, Scheduling: Theory, Algorithms, and Systems (5th ed.) — parallel-machine scheduling and days-off workforce scheduling; Hopp & Spearman, Factory Physics (3rd ed.) — variability, buffering, and production scheduling; Liker, The Toyota Way, and Shingo, A Revolution in Manufacturing: The SMED System — 5S, Five Whys, SMED and lean root-cause analysis.
Question 8: Rebalancing 14 Jobs Across Three Surface-Mount Machines, and Minimum Workforce (20 marks)
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 two lower bounds (weekly days off and weekends off) and show a rota that meets the larger one.
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 (part a). An exhaustive branch-and-bound 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}}$, exactly meeting the manager's 4-hour target with zero margin. Every job time is a multiple of 100 s, so no machine can finish between 14,367 s and 14,400 s; 14,400 s is therefore the optimal makespan, and no schedule makes the worst job finish earlier. By hand, the longest-processing-time (LPT) rule (sort jobs longest first, give each to the least-loaded machine) gives 14,600 s; the branch-and-bound search then improves this to 14,400 s. Within each machine, run the jobs shortest first to cut average job completion time without changing the makespan.
Minimum workforce (part b). Three machines, each with one operator per shift, over three 8-hour shifts a day, seven days a week, need a constant $R=3\times3=9$ operators on duty every day. Two rules each set a floor on the headcount $N$.
$$\text{Days off: }5N\ge7R=63\ \Rightarrow\ N\ge\lceil12.6\rceil=13$$
$$\text{Weekends off: }(5-2)\,N\ge5R=45\ \Rightarrow\ N\ge15$$
The second bound holds because over 5 weeks each operator can work at most $5-2=3$ Saturdays, while $5\times9=45$ Saturday shifts must be filled. The weekend rule governs, so $\boxed{N_{min}=15\ \text{operators}}$; 13 operators could cover only $13\times3=39$ of the 45 Saturday shifts.
15 is achievable. Split the operators into 5 crews of 3 on a 5-week cycle (crew numbers wrap, so crew 6 is crew 1). In week $k$, crews $k$ and $k+1$ take the weekend off and work Monday–Friday. The other three crews work the weekend and rest two weekdays: crew $k+2$ rests Mon+Tue, crew $k+3$ Wed+Thu and crew $k+4$ Thu+Fri. Every crew gets exactly 2 weekends off in 5 weeks and 2 days off every week. Cover is 12 on Mon, Tue, Wed and Fri and 9 on Thu, Sat and Sun, so at least 9 are always on duty. A binary-programming check confirms that 14 operators is infeasible and 15 is feasible, even if “two days off in every seven” is read as every rolling 7-day window.
Figure 2 — Rebalanced load-balanced assignment meeting the 4-hour target: Machine A 14,300 s; Machine B 14,400 s; Machine C 14,400 s.
