Five Consignments, One Inspector: Sequencing Under Conflicting Constraints
A CWC godown has five consignments due for pre-dispatch inspection - P, Q, R, S and T - and only one inspector, who can certify exactly one consignment per working day, Monday to Friday. Each consignment must be certified before its truck is loaded the next morning, and no day may be left unused.
The inspector's standing instructions are:
- P must be certified before R, but not on the day immediately before R, because the two lots share a sampling plan and the laboratory needs a gap between them.
- T must be certified after S, with exactly one working day falling between S and T.
- Q cannot be taken on Monday or Friday; Q's stock lies in the block whose weighbridge is certified only mid-week.
- R cannot be certified on Friday, since the certification report has to reach the regional office before the weekend.
On Tuesday morning the laboratory telephones to say that the samples for P have been mixed up and P can be certified only on Thursday. The dispatch section wants to know whether the week's plan can still be met, or whether trucks must be rescheduled.
1. Determine the inspection order that satisfies all four standing instructions, and show how each alternative is eliminated.
Read the worked answer
Step 1 - fix the S–T pair. Rule 2 allows only three placements in a 5-day week: S=1, T=3; S=2, T=4; S=3, T=5.
Step 2 - test each against the Q rule (Q in slots 2, 3 or 4).
- S=1, T=3. Free slots are 2, 4, 5; Q can be 2 or 4. If Q=2, P and R must take 4 and 5, and the only P-before-R order is P=4, R=5 - adjacent, forbidden by Rule 1. If Q=4, P and R take 2 and 5, giving P=2, R=5, which puts R on Friday and breaks Rule 4. Dead end.
- S=2, T=4. Free slots 1, 3, 5; Q can only be 3. Then P and R take 1 and 5, i.e. P=1, R=5 - R on Friday again. Dead end.
- S=3, T=5. Free slots 1, 2, 4. If Q=4, then P and R take 1 and 2, i.e. P=1, R=2, adjacent and forbidden. If Q=2, then P and R take 1 and 4: P=1, R=4, legal on all counts.
Answer: Mon P, Tue Q, Wed S, Thu R, Fri T.
The structural reason: R may not sit in slot 5 and must be separated from P, so the S–T pair has to be pushed to the back half of the week and Friday has to be given to T, the only lot with no positional restriction.
2. The regional office relaxes Rule 4, allowing R to be certified on Friday. How many valid schedules now exist, and what are they?
Read the worked answer
Relaxing Rule 4 does not change the three possible S–T placements; it only removes one filter. Re-test each case:
- S=1, T=3. Slots 2, 4, 5 free. Q=2 forces P=4, R=5 - adjacent, still illegal. Q=4 forces P=2, R=5 - legal. One schedule: S, P, T, Q, R.
- S=2, T=4. Slot 3 is the only place for Q; P=1, R=5 is legal. One schedule: P, S, Q, T, R.
- S=3, T=5. Slots 1, 2, 4 free. Q=4 forces P=1, R=2 - adjacent, illegal. Q=2 forces P=1, R=4 - legal. One schedule: P, Q, S, R, T.
Total: three valid schedules.
Note what this shows about such puzzles: the binding constraint was never Rule 4 alone. Rule 1 (non-adjacency) and Rule 3 (mid-week only) between them do most of the eliminating - that is why removing a single restriction triples the number of solutions rather than leaving the answer unchanged. In practice, a scheduler should state which rule is load-bearing before promising a fixed dispatch plan, because a one-line relaxation at regional level can leave three equally compliant plans and no basis for choosing between them.
3. The laboratory now says P can be certified only on Thursday. Is any schedule still feasible under the original four rules? What should the godown do?
Read the worked answer
No schedule exists. R must follow P, and Thursday leaves only Friday for R - which Rule 4 forbids. Certifying P on Friday is worse: nothing remains after it for R. So the constraint set is infeasible, not merely tight.
The reasoning to report upwards is this: P and R consume two consecutive-or-later slots, and R is barred from the last slot. P must therefore be certified no later than Wednesday for any plan to close. Thursday is already one day too late, so the answer does not depend on how the other lots are arranged.
Practical options, in order of preference:
- Split the consignment. Certify the Thursday-lab samples of P as a part lot and re-inspect the balance next week, so at least one truck moves.
- Swap the laboratory. If the mix-up was internal, send P's samples to the district laboratory and keep Tuesday's slot; the rule is about a gap before R, not about which laboratory signs.
- Re-sequence R. Certify R first and P afterwards, which needs a written waiver of Rule 1 from the regional office - the sampling-plan reason may not survive if the two lots are being dispatched separately.
What must not be done is to load P's truck on an uncertified consignment and 'regularise later'. That converts a scheduling problem into a documentation and liability problem.