The train marshalling problem

The problem considered in this paper arose in connection with the rearrange ment of railroad cars in China. In terms of sequences the problem reads as follows: Train Marshalling Problem: Given a partition S of {1,...,n} into d isjoint sets S-1,...,S-t, find the smallest number k = K(S) so that there e xists a permutation p(1),..., p(t) of {1,...,t} with the property: The sequ ence of numbers 1,2,..., n, 1,2,..., n,...,1,2,..., n where the interval 1, 2,..., n is repeated k times contains all the elements of S-p(1), then all elements of S-p(2), etc., and finally all elements of S-p(t). The aim of th is paper is to show that the decision problem: "Given numbers n,k and a par tition S of {1,2,...,n}, is K(S)less than or equal to k?" is NP-complete. I n light of this, we give a general upper bound for K(S) in terms of n. (C) 2000 Elsevier Science B.V. All rights reserved.