Sequencing Four Track Blocks on a Single Line
A single-line section between two stations must absorb four maintenance blocks - W, X, Y and Z - each occupying the section exclusively, one at a time, within one eight-hour window. Three planning rules are in force. First, the track-machine crew that works W is also needed for X, so W must be completed before X starts. Second, because the machine needs a cooling interval, X cannot be taken up in the position immediately after W. Third, the ballast-cleaning unit must finish Y before Z can begin. No two blocks can run together and all four must be completed in the window. The controller has pencilled in W–Y–X–Z and wants to know whether that is the only valid sequence, and whether he can promise the signalling staff that Z will be the last block of the day.
1. Enumerate every sequence that satisfies all three rules. Show how you derive the list rather than guessing it.
Read the worked answer
Anchor on the W–X pair, since the cooling rule restricts it most. With four positions and no adjacency allowed, the possible (position of W, position of X) pairs are (1,3), (1,4) and (2,4).
- W at 1, X at 3: slots 2 and 4 remain for Y and Z; Y must precede Z, so Y=2, Z=4. Sequence: W–Y–X–Z.
- W at 1, X at 4: slots 2 and 3 remain; Y=2, Z=3. Sequence: W–Y–Z–X.
- W at 2, X at 4: slots 1 and 3 remain; Y=1, Z=3. Sequence: Y–W–Z–X.
(W at 3 is impossible because X would need a later slot with a gap.)
So exactly three valid sequences: W–Y–X–Z, W–Y–Z–X and Y–W–Z–X. The controller's plan is valid but not unique.
2. Can Z be promised to the signalling staff as the final block of the day? Answer with reference to the enumeration.
Read the worked answer
No. Z is last in two of the three sequences (W–Y–X–Z and Y–W–Z–X) but third in W–Y–Z–X, where X closes the window.
Because X must follow W with at least one block in between, whichever block fills the gap can push Z earlier. Any operational event that forces W to slot 1 and X to slot 4 - for example, the machine being ready early but the cooling interval being unavoidable - produces W–Y–Z–X.
The correct commitment to signalling staff is: 'Z will be completed within the window, and will not start before slot 3 at the earliest' - that is, a guarantee about Z's earliest start, not about its being last.
3. If the cooling rule is withdrawn because a second machine becomes available, how many sequences become feasible, and which new ones appear?
Read the worked answer
Without the adjacency ban the only constraints are W before X and Y before Z. Choose any 2 of the 4 slots for W and X: that is 4C2 = 6 ways, and in each case the earlier slot must be W. Y and Z then fill the remaining two slots with Y first - exactly one arrangement.
So 6 sequences, an increase of 3. The new ones are the adjacency cases:
- W–X–Y–Z (W at 1, X at 2)
- Y–W–X–Z (W at 2, X at 3)
- Y–Z–W–X (W at 3, X at 4)
The original three remain valid. Note the practical point: the extra freedom comes only because a second machine removes the cooling constraint, not because the crew rule was relaxed - the crew rule still binds W before X in every one of the six.