Экстремальная двухэтапная задача маршрутизации и процедуры на основе динамического программирования

Исследуется задача маршрутизации, в которой множество заданий представлено в виде суммы двух дизъюнктных подмножеств. Задания из первого подмножества должны быть выполнены прежде, чем начнется выполнение заданий из второго. Каждое задание связано с посещением мегаполиса (непустого конечного множества) с целью выполнения некоторых работ. Выбор очередности выполнения заданий может быть стеснен условиями предшествования, которые локализуются для двух вышеупомянутых подмножеств полного множества заданий. Функции стоимости, участвующие в формировании аддитивного критерия, допускают зависимость от списка заданий. Для построения решения предлагается двухэтапная процедура на основе динамического программирования. Построен оптимальный алгоритм, реализованный на ПЭВМ; приведено решение модельной задачи, связанной с фигурной листовой резкой на машинах с ЧПУ.