Rostering Four Night Duties with Interlocking Constraints
A four-bedded district laboratory runs a single night shift, 20:00 to 08:00, for emergency haematology and biochemistry. Four technicians - Farah, Gopal, Hina and Imran - must each cover exactly one of the four nights from Monday to Thursday. Nobody works two of these nights, and every night is covered by exactly one technician. The roster officer must satisfy these rules:
- Farah's night must fall before Gopal's night, but Farah cannot take Monday.
- Hina cannot take Tuesday, because she attends a certification class that evening.
- Imran must take the night immediately after Hina's night.
- Imran is already rostered for the Friday night shift, and hospital policy does not allow the same technician to work two consecutive nights.
The roster officer produces a draft with Hina on Monday, Imran on Tuesday, Farah on Wednesday and Gopal on Thursday. The senior technician wants the draft justified in writing before signing it, and asks two supplementary questions about what would happen if circumstances changed.
1. Determine the roster from the rules and justify each step of the deduction.
Read the worked answer
Step 1 - place Hina and Imran. Rule 3 makes them a consecutive pair: (Mon, Tue), (Tue, Wed) or (Wed, Thu). Rule 2 removes any pair beginning on Tuesday, leaving (Mon, Tue) or (Wed, Thu).
Step 2 - test (Wed, Thu). Imran would work Thursday and then again on Friday, which rule 4 forbids. So this pair is impossible.
Step 3 - therefore Hina is Monday and Imran is Tuesday. Wednesday and Thursday remain for Farah and Gopal.
Step 4 - place Farah and Gopal. Rule 1 requires Farah before Gopal, so Farah is Wednesday and Gopal is Thursday. The stipulation that Farah cannot take Monday is automatically satisfied and is, in this solution, redundant.
Final roster: Monday - Hina; Tuesday - Imran; Wednesday - Farah; Thursday - Gopal.
The draft is therefore correct, but it is correct by deduction, not by luck: every rule was needed except rule 1's Monday clause, and a written justification should note that so that the clause is not mistaken for the load-bearing one.
2. If Hina's certification class is cancelled, does the roster change? Give the reasoning, not just the answer.
Read the worked answer
No - the roster does not change, and the point of the question is to check whether the constraint was actually doing any work.
With rule 2 withdrawn, the consecutive pair Hina–Imran may now begin on Monday, Tuesday or Wednesday.
• (Mon, Tue): Farah and Gopal take Wednesday and Thursday, Farah first - valid. • (Tue, Wed): Farah and Gopal are left with Monday and Thursday; Farah must come before Gopal and cannot take Monday, so Farah would need Thursday and Gopal Monday, which violates rule 1. Invalid. • (Wed, Thu): Imran would work Thursday and Friday consecutively, which rule 4 forbids. Invalid.
Only one arrangement survives, and it is identical to the original: Hina Monday, Imran Tuesday, Farah Wednesday, Gopal Thursday. Rule 2 was a genuine constraint on the search but not on the solution; removing it changes the reasoning path without changing the outcome. Writing that down matters, because a roster that is right for the wrong reason tends to break the next time a rule is added.
3. If Gopal reports sick and cannot take any night this week, what follows, and which single rule would have to be relaxed to build a workable roster?
Read the worked answer
No workable roster exists while rule 1 stands. Rule 1 requires Farah's night to fall before Gopal's, so Gopal's presence is a precondition for placing Farah at all; remove Gopal and Farah has nowhere to go, because the only slots not constrained by Hina and Imran must be ordered with Gopal at the later end.
The cleanest relaxation is therefore rule 1 (Farah before Gopal), since Gopal is no longer available and the ordering requirement has lost its subject. That leaves Hina–Imran as a consecutive pair and Farah free to take either remaining night: (Mon, Tue) with Farah Wednesday or Thursday, or (Wed, Thu) excluded by rule 4, so Hina Monday, Imran Tuesday, Farah on Wednesday or Thursday.
A second, less satisfactory option is to bring in a fifth technician, which introduces a new constraint set and should be treated as a fresh rostering problem rather than a patch. The rule that must not be sacrificed is rule 4 (no consecutive nights), because fatigue on a lone night shift is a patient-safety issue, not an administrative preference - and rule 2, the class, is a training obligation rather than a safety limit, so it would be the fairer rule to negotiate if a compromise is forced.