Минимизация максимального взвешенного временно́го смещения доставки заказов между двумя железнодорожными станциями

Рассматривается задача планирования грузоперевозок между двумя железнодорожными станциями. Требуется выполнить заказы (перевезти вагоны поездами), поступающие в произвольные моменты времени и имеющие различную ценность (вес). Скорость движения поездов между станциями может быть различной. Рассмотрены постановки задачи как с фиксированными, так и с неопределенными моментами отправления поездов. Для задачи с фиксированными моментами отправления поездов представлен алгоритм минимизации взвешенного временно́го смещения заказов трудоемкости $O(qn^2\log n)$ операций, где $q$ – количество поездов, а $n$ – количество заказов. Для задачи с неопределенными моментами отправления и прибытия поездов построено Парето-множество расписаний оптимальных по критериям $wL_\mathrm{max}$ и $C_\mathrm{max}$ за $O(n^2\mathrm{max}\{n\log n,q\log v\})$ операций, где $v$ – количество временны́х окон, в которые возможно отправление поездов. Представленный алгоритм позволяет минимизировать как взвешенное временно́е смещение $wL_\mathrm{max}$, так и общее время выполнения заказов на доставку грузов $C_\mathrm{max}$.