In this paper, we consider a two-machine job-shop scheduling problem of minimizing
total completion time subject to n jobs with two operations and equal processing times on each
machine. This problem occurs e.g., as a single-track railway scheduling problem with three stations
and constant travel times between any two adjacent stations. We present a polynomial dynamic
programming algorithm of the complexity O(n5) and a heuristic procedure of the complexity O(n3).
This settles the complexity status of the problem under consideration which was open before and
extends earlier work for the two-station single-track railway scheduling problem. We also present
computational results of the comparison of both algorithms. For the 30,000 instances with up to
30 jobs considered, the average relative error of the heuristic is less than 1%. In our tests, the practical
running time of the dynamic programming algorithm was even bounded by O(n4)