Question 4 of 8: LP Formulation — Post Office Workforce Scheduling

Question 4: LP Formulation — Post Office Workforce Scheduling (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. Daily FTE requirement $b_d$, $d=1,\dots,7$ (Sun…Sat) $=(11,17,13,15,19,14,16)$; FT employee = 8 hr/day × 5 consecutive days at $15/hr ($600/week); PT employee = 4 hr/day × 5 consecutive days at $10/hr ($200/week, 0.5 FTE-equivalent/day); part-time labour capped at 25% of the total weekly labour-hour requirement.

Find. An LP that assigns full-time and part-time staff to 5-consecutive-day shift patterns to cover every day's FTE requirement at minimum weekly cost.

Approach. Use the classic cyclic "days-off scheduling" device: index the 7 possible 5-consecutive-day shift patterns by their start day, let $x_i,y_i$ be the number of full-time/part-time staff starting such a shift on day $i$, write each day's coverage as a sum over the (at most 5) patterns that include it, and cap total part-time hours at 25% of total required hours.

1. Decision variables and coverage indicator. For $i=1,\dots,7$ (start day, cyclic mod 7): $x_i\ge0$ = number of full-time employees whose 5-day block starts on day $i$; $y_i\ge0$ = number of part-time employees whose 5-day block starts on day $i$. Define $a_{d,i}=1$ if day $d$ falls within the 5-day block starting on day $i$ (i.e. $d\in\{i,i{+}1,\dots,i{+}4\}\bmod7$), else 0.
2. Daily coverage constraint (FT contributes 1.0 FTE/day worked, PT contributes 0.5 FTE/day worked): $$\sum_{i=1}^{7}a_{d,i}\,x_i+0.5\sum_{i=1}^{7}a_{d,i}\,y_i\ \ge\ b_d,\qquad d=1,\dots,7$$
3. Part-time composition cap — total part-time labour-hours over the week cannot exceed 25% of the total weekly requirement (each PT employee works $5\times4=20$ hr/week; each unit of $b_d$ is $8$ hr): $$20\sum_{i=1}^{7}y_i\ \le\ 0.25\Big(8\sum_{d=1}^{7}b_d\Big)$$
4. Objective — minimize weekly labour cost ($600/FT employee/week, $200/PT employee/week): $$\boxed{\min Z=600\sum_{i=1}^{7}x_i+200\sum_{i=1}^{7}y_i}$$ subject to the coverage constraints of Step 2, the part-time cap of Step 3, and $x_i,y_i\ge0$ for all $i$.
5. Validating solve. Plugging in $b=(11,17,13,15,19,14,16)$, so $\sum b_d=105$ and the part-time cap is $20\sum y_i\le0.25(840)=210$: solving the 14-variable LP (e.g. by simplex/software) gives a minimum feasible weekly cost of $12,350 — confirming the model is feasible and well-posed. (The LP relaxation splits some shift starts fractionally across days, as is typical for continuous staff-scheduling relaxations; the question asks only for the formulation.)