I'm sure graph theory comes into play pretty soon. Unfortunately, I know nothing about that subject.

However, it also seems like this problem resembles the traditional 'scheduling with constraints' which had been a business problem that has been solved in various ways for decades (5 that I know of). A section of track (block) is a resource. A train is a consumer and it wants to consume a certain number of blocks. Other trains are also consumers and they want to consume blocks as well. No two consumers can utilize a block at the same time.

There are going to be two generic solutions: Let the train with the maximum requirement go first - a greedy algorithm. The other is 'maximum throughput' where more trains with lesser requirements are scheduled to go first.

I have always admired the zero-one optimization approach. I have had a textbook on that subject for nearly 50 years! It was my first introduction to scheduling resources for construction.

http://www.orsj.or.jp/~archive/pdf/e_mag/Vol.13_02_078.pdfThis is a special case of 'integer programming'

http://web.mit.edu/15.053/www/AMP-Chapter-09.pdfGoogle search 'binary zero one programming scheduling constraints' or 'integer programming'

I see Matlab in one of the replies, I wonder how that works...