Five Trains, Four Platforms, One Closed
A four-platform junction must be planned for five trains on a Sunday morning. Platform 3 is booked for engineering work from 10:00 to 11:00 and cannot be used at all during that hour. A platform counts as occupied from the moment a train arrives until 10 minutes after it departs, because the cleaning gang needs that time. The trains are: A 09:40–10:10, B 10:00–10:35, C 10:20–10:50, D 10:45–11:15, E 11:05–11:40. The station manager's rule is that two trains may share a platform only if their occupied windows do not overlap; touching windows (one ending exactly when the next begins) are allowed. Platforms 1, 2 and 4 are free all morning.
1. Using only platforms 1, 2 and 4, produce an allocation for all five trains, or show that none exists.
Read the worked answer
Step 1 - convert to occupied windows (add 10 min to each departure):
| Train | Occupied |
|---|---|
| A | 09:40–10:20 |
| B | 10:00–10:45 |
| C | 10:20–11:00 |
| D | 10:45–11:25 |
| E | 11:05–11:50 |
Step 2 - find the overlaps (trains that cannot share): A–B, B–C, C–D. A–C touch at 10:20 (allowed), B–D touch at 10:45 (allowed). A, B with D or E: no overlap. C–E: C ends 11:00, E starts 11:05 - allowed.
Step 3 - allot:
- Platform 1: A (09:40–10:20) → C (10:20–11:00) → E (11:05–11:50)
- Platform 2: B (10:00–10:45) → D (10:45–11:25)
- Platform 4: unused (spare)
Every shared platform has non-overlapping windows, so the allocation is valid. Only two platforms were actually needed.
2. The engineering work on platform 3 is later extended from 11:00 to 11:30. Which train, if any, must be rescheduled?
Read the worked answer
None.
The only train that could ever have used platform 3 under the original plan is E, whose window begins at 11:05 - after the old 11:00 release. In the plan already produced, E sits on platform 1 from 11:05 to 11:50, following C (which clears at 11:00).
So: the change makes platform 3 unavailable for 30 extra minutes, but the plan never used platform 3 at all. A constraint that is not binding cannot break the schedule.
Judgement point: before re-planning, always check whether the relaxed/tightened constraint actually touches the solution. Re-planning on instinct here would create unnecessary delays and confuse the control office.
3. A safety circular tightens the rule: a platform must stay empty for at least 10 minutes between one train's occupancy ending and the next one beginning. Does a plan using only platforms 1, 2 and 4 still exist? If yes, give it.
Read the worked answer
Yes, but the old plan no longer works.
Under the 10-minute rule, pairs that merely touch now conflict, and pairs separated by less than 10 minutes conflict:
- A–B (overlap), A–C (only 0 min gap), B–C (overlap), B–D (0 min gap), C–D (overlap), C–E (5 min gap), D–E (overlap).
- A–D, A–E, B–E are still fine (gaps of 25 min, 45 min, 20 min).
A valid three-platform plan:
- Platform 1: A (09:40–10:20), then D (10:45–11:25) - gap 25 min ✔
- Platform 2: B (10:00–10:45), then E (11:05–11:50) - gap 20 min ✔
- Platform 4: C (10:20–11:00) alone ✔
- Platform 3: still under work, unused
Check the crowded pairs: A and D have no overlap and 25 minutes of clearance; B and E have 20 minutes; C stands alone. The plan holds.
Lesson: the same five trains can be impossible under one rule and easy under another - the rule, not the trains, decides feasibility.