Question 1 of 10: LP Formulation — Post Office Full-Time / Part-Time Staff Scheduling
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — December 2013 — 98-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 200 marks across 10 questions and only 100 marks are required, so a candidate would normally answer a subset — all ten are solved below for completeness.
Reference texts: Hillier & Lieberman, Introduction to Operations Research (11th ed., McGraw-Hill) — linear/integer programming, network optimization, dynamic programming, decision analysis and queueing theory; Nahmias, Production and Operations Analysis — inventory models with planned backorders.
Given. Daily FTE requirement over one week (S–S); full-time (FT) staff work 8 hrs./day at $15/hr = $120/day, 5 consecutive days then 2 consecutive days off; part-time (PT) staff work 4 hrs./day at $10/hr = $40/day, i.e. 0.5 FTE-day each; PT labour capped at 25% of the total weekly labour requirement.
Day
Sun
Mon
Tue
Wed
Thu
Fri
Sat
Week total
FTE required
11
17
13
15
19
14
16
105
Find. A Linear Programming model — decision variables, objective and constraints — that minimizes the weekly labour cost of covering the schedule. Do not solve.
Approach. Model full-time staffing as a cyclic days-off schedule (7 possible 5-consecutive-day shift starts, each covering 5 of the 7 days), add a daily part-time headcount, then impose day-by-day coverage and a union part-time cap.
Decision variables. Index the days $i=1,\dots,7$ (Sun…Sat). Let $x_j\ge0$ integer = number of full-time employees whose 5-consecutive-day work week begins on day $j$ (working days $j,j+1,\dots,j+4$, mod 7, then resting the other 2 consecutive days), for $j=1,\dots,7$. Let $y_i\ge0$ integer = number of part-time employees working on day $i$ (4 hrs. that day only), $i=1,\dots,7$.
Coverage sets. A shift starting on day $j$ covers day $i$ exactly when $j\in\{i,i-1,i-2,i-3,i-4\}\pmod 7$ — i.e. 5 of the 7 possible start-days cover any given day.
Day $i$ covered
FTE$_i$
Full-time shifts covering it
Sun (1)
11
$x_1,x_4,x_5,x_6,x_7$
Mon (2)
17
$x_1,x_2,x_5,x_6,x_7$
Tue (3)
13
$x_1,x_2,x_3,x_6,x_7$
Wed (4)
15
$x_1,x_2,x_3,x_4,x_7$
Thu (5)
19
$x_1,x_2,x_3,x_4,x_5$
Fri (6)
14
$x_2,x_3,x_4,x_5,x_6$
Sat (7)
16
$x_3,x_4,x_5,x_6,x_7$
Coverage constraints. Each day's on-duty FTE (full-time shifts covering it, plus 0.5 FTE per part-timer that day) must meet requirement:
$$\sum_{j\,\text{covers}\,i} x_j \;+\; 0.5\,y_i \;\ge\; \text{FTE}_i,\qquad i=1,\dots,7.$$
Union part-time cap. Part-time FTE-days may not exceed 25% of the week's total requirement ($0.25\times105=26.25$):
$$0.5\sum_{i=1}^{7} y_i \;\le\; 26.25 \quad\Longleftrightarrow\quad \sum_{i=1}^{7} y_i \le 52.5.$$
Objective. Minimize weekly labour cost ($600 per full-time employee—5 days at $120—plus $40 per part-time employee-day):
$$\boxed{\min Z = 600\sum_{j=1}^{7}x_j \;+\; 40\sum_{i=1}^{7}y_i}$$
subject to the 7 coverage constraints, the union cap, and $x_j,y_i\ge0$ integer.
Element
Formulation
Variables
$x_j\ge0$ integer (FT shifts starting day $j$), $y_i\ge0$ integer (PT headcount day $i$), $j,i=1,\dots,7$
The paper's instruction reads "minimize the fuel cost," a typo for labour cost — the paragraph is entirely about full-/part-time wages, so the objective above minimizes labour cost. The union cap is modelled as an aggregate weekly limit (total part-time FTE-days $\le$25% of the week's total FTE requirement); a per-day reading ($0.5y_i\le0.25\,\text{FTE}_i$ for each $i$) is an equally defensible alternative and would simply replace the single cap row with 7 rows.
