Scheduling a Volunteer Roster with Conflicting Constraints
A community kitchen must staff 14 shifts across 7 days (two shifts per day: morning and evening). There are 9 volunteers. Each volunteer submits an availability list and a maximum number of shifts they will work. Volunteer A can work only mornings, at most 3 shifts. Volunteer B can work any shift but only on weekends, at most 2. Volunteer C is available every shift and will work up to 4. The remaining six volunteers each have partial availability and caps between 1 and 3. Every shift needs exactly one person. The coordinator first tried a greedy approach: sort volunteers by fewest available shifts and assign them to their earliest available slot. This left Saturday evening empty even though three volunteers listed availability for it. A second attempt sorted by most available shifts first and produced a valid roster, but it gave Volunteer C five shifts, exceeding her cap.
1. Explain why the greedy strategy failed in the first attempt and why the second attempt violated a hard constraint. Identify which constraint each approach ignored.
Read the worked answer
The first greedy rule ordered volunteers by scarcity (fewest available shifts) and filled each volunteer's earliest slot. Scarcity ordering is a reasonable heuristic because constrained volunteers have fewer options, but the rule never checks whether a shift will later become unfillable. When Saturday evening's only remaining candidates had already been consumed by earlier assignments, the slot was stranded. The failure is structural: greedy makes an irrevocable choice per volunteer without lookahead, so it can exhaust a resource (a volunteer's availability) that a later shift depends on.
The second rule ordered by abundance and assigned earliest slots. Abundance ordering fills flexible volunteers first, which tends to leave constrained volunteers for the shifts only they can cover - good for feasibility. But the algorithm never re-checked each volunteer's cap after assignment. Volunteer C's cap of 4 is a hard constraint, and assigning her a fifth shift means the roster is infeasible regardless of coverage. The first approach ignored future feasibility (a lookahead/global constraint); the second ignored a per-volunteer capacity constraint. A correct approach must treat caps as hard constraints enforced at every assignment and must check that remaining shifts still have at least one eligible, uncapped volunteer before committing.
2. Describe how you would model this problem formally and what algorithmic approach would guarantee a correct roster if one exists.
Read the worked answer
Model it as a constraint satisfaction / bipartite matching problem. Let S be the set of 14 shifts and V the 9 volunteers. Define a bipartite graph with an edge (v, s) whenever volunteer v is available for shift s. Each shift must be matched to exactly one volunteer (a coverage constraint). Each volunteer v has a capacity cap(v), so v may be matched to at most cap(v) shifts. This is a bipartite b-matching (capacitated matching) problem.
A guaranteed approach: split each volunteer v into cap(v) copies, each connected to the shifts v can work, then find a maximum matching in the resulting bipartite graph (e.g. Hopcroft–Karp). If the maximum matching saturates all 14 shifts, a valid roster exists; otherwise no roster exists and the unmatched shifts identify the bottleneck. Alternatively, formulate as an integer program: minimise 0 subject to sum over v of x(v,s) = 1 for each shift, sum over s of x(v,s) ≤ cap(v) for each volunteer, x binary. A solver returns a feasible assignment or proves infeasibility.
Either method handles the hard constraints correctly. The greedy heuristics cannot guarantee correctness because they commit without backtracking; matching/ILP either find a valid assignment or certify that none exists, which is exactly the judgement the exam rewards.
3. Suppose the coordinator wants to also minimise the number of volunteers used. Explain why this changes the problem and how you would adapt the model.
Read the worked answer
Minimising volunteers used adds an objective on top of feasibility. The pure matching model only asks whether all shifts can be covered; it does not prefer solutions that concentrate work. To minimise the number of distinct volunteers, introduce a binary variable y(v) that is 1 if volunteer v is used, with x(v,s) ≤ y(v) for every shift s (linking constraint) and the objective minimise the sum of y(v). The coverage and capacity constraints remain. This is now an integer program with a genuine optimisation objective.
A matching-based adaptation is harder: capacitated matching finds a feasible assignment, not a minimum-cardinality support. One workaround is to test feasibility with k volunteers for increasing k (or binary search) by restricting the volunteer set, but that is exponential in the worst case. The ILP formulation is cleaner and a solver handles it directly. Note the trade-off: minimising volunteers may push some volunteers to their caps and reduce slack, making the roster more fragile to last-minute absences. The exam expects you to recognise that adding an objective changes the problem class from feasibility to optimisation and that the model must be extended with linking variables and an objective function.