Рассматривается следующая задача теории
расписаний. Имеется две станции,
соединенные двухпутной железной
дорогой. Необходимо обслужить множества
заказов $N^1 = \{J_1^1,\dots,J_n^1\}$ и $N^2=\{J_1^2,\dots,J_m^2\}$
на поставку грузов между станциями.
Заказы множества $N^1$ необходимо
доставить с первой станции на вторую, а
заказы множества $N^2$ --- со второй на
первую. Каждый заказ состоит из одного
вагона. Все вагоны однотипные. Так как
железная дорога двухпутная, то
расписания для множества $N^1$ и $N^2$
независимы и составляются отдельно. Не
ограничивая общности будем
рассматривать одно из множеств $N = \{J_1,
\dots, J_n\}$. Пусть $r_j$ --- время поступления
заказа $J_j$, на станцию. Без потери
общности предположим, что заказы
пронумерованы в порядке их поступления.
Каждый заказ имеет свою ценность $w_j > 0$.
Доставка вагонов с одной станции на
другую осуществляется составами, каждый
из которых состоит из $k$ вагонов. Пусть $p$
--- время движения состава между
станциями, а $\alpha$ --- время, которое должно
разделять моменты отправки двух поездов.
Каждый заказ имеет директивный срок $d_j =
r_j + \delta$ --- момент времени, до которого
заказ может быть доставлен на станцию
назначения без опоздания, где $\delta$ ---
запас времени на доставку. Пусть $C_j$ ---
время фактической доставки заказа $J_j\in N$
на станцию назначения. Целевая функция
задачи
$$\min\max\limits_{j=\overline{1,n}}(w_j(C_j - d_j)).$$
Предлагается алгоритм динамического
программирования, минимизирующий
максимальное взвешенное временное
смещение доставки заказов за O(n^6)
операций.
