Minimization of maximum lateness for M stations with tree topology
The paper is devoted to a schedulling theory problem. There are some railway stations and a set of orders (cars). Our goal is to transport all cars to destination stations with the minimal maximum lateness. New polynomial-time algorithm is proposed for solving this problem. Firstly, an auxiliary problem is solved. Then a special algorithm improves the received schedule. As a result we have the algorithm which complexity is $O(M^2n^4/k)$, where M is number of stations, n is number of orders, k is number of cars in a train.