ИСТИНА

Рассматривается задача составления плана движения грузовых составов между двумя станциями, соединенными двухпутной железной дорогой. Данная задача состоит из двух подзадач: компоновки составов и отправки поездов. Составы представлены в виде множества вагонов, каждый из которых соответствует заказу на доставку груза. Для заказов определены такие параметры как: момент поступления, директивный срок и важность. При составлении расписания учитываются ограничения движения, связанные с плановыми работами, движением пассажирских поездов и другими причинами. Представлена постановка задачи в терминах теории расписаний. Предлагается алгоритм динамического программирования, минимизирующий максимальное взвешенное временное смещение доставки заказов за полиномиальное число шагов .