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

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