Об одной задаче маршрутизации перемещений инструмента при листовой резке деталей

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