Two station single track railway scheduling problem with equal speed of trains

Abstract : The single track railway scheduling problem with two stations and Q segments of the track is considered. Two subsets of trains N′1 and N′2 are given, where trains from N′1 go from the station 1 to the station 2, and trains from N′2 go in the opposite direction. The speed of trains over each segment is the same. A polynomial time reduction from the problem under consideration to a special case of the single machine equalprocessing- time scheduling problem with setup times is presented. For this special case with different objective function under different constraints, polynomial time solution algorithms are presented.