ON THE MERLIN-RANDELL PROBLEM OF TRAIN JOURNEYS
Naciej Koutny · 2005
I n t h e p a p e r [MR78] , M e r l i n a n d R a n d e l l i n t r o d u c e d a s y n c h r o n i s a t i o n p r o b l e m wh ich may be f o r m u l a t e d a s f o l l o w s : There is a finite set of trains and a layout. The layout is represented by an undirected graph, the nodes of which represent places where train can reside (stations), the arcs of which represent possible moves. Each station can hold only one train. Each train has a program to follow, consisting of directed path through the graph. The train can leave a station only when the station it is immediately to travel to is empty. The problem is to find a synchronlsation among train movements which allows parallel movements where possible. In fact this is rather a problem of flow control in networks, but writing in terms of trains and stations makes the problem and the solution more intuitive and readable. Some partial but rather insufficient solutions were discussed in [MR78, $79, JL82 and D82] . In this memo we present a solution of the train journeys problem based on the synchronisation idea of [JL82] . The solution is partial in the sense that we assume train routes contain no non-deterministic choices and no loops.