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

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

Ключевые слова

маршрутные задачи; условия предшествования; инженерные ограничения.

Литература

1. Петунин, А.А. О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала / А.А. Петунин // Вестник УГАТУ. - 2009. - Т. 13, № 2 (35). - С. 280-286.
2. Фроловский, В.Д. Автоматизация проектирования управляющих программ тепловой резки металла на оборудовании с ЧПУ / В.Д. Фроловский // Информационные технологии в проектировании и производстве. - 2005. - № 4. - С. 63-66.
3. Верхотуров, М.А. Математическое обеспечение задачи оптимизации пути режущего инструмента при плоском фигурном раскрое на основе цепной резки / М.А. Верхотуров, П.Ю. Тарасенко // Вестник УГАТУ. - 2008. - Т. 10, № 2 (27). - С. 123-130.
4. Петунин, А.А. К вопросу о маршрутизации движения инструмента в машинах листовой резки с числовым программным управлением / А.А. Петунин, А.Г. Ченцов, П.А. Ченцов // Научо-технические ведомости СПбГПУ. Серия: Информатика. Телекоммуникации. Управление. - 2013. - № 2 (169). - С. 103-111.
5. Chentsov, A.A. Dynamic Programming Method in the Generalized Traveling Salesman Problem: the Influence of Inexact Calculation / A.A. Chentsov, A.G. Chentsov // Mathematical and Computer Modelling. - 2001. - V. 33 - P. 801-819.
6. Ченцов, А.Г. Дискретно-непрерывная задача маршрутизации с условиями предшествования / А.Г. Ченцов, А.А. Ченцов // Труды Института математики и механики УрО РАН. - 2017. - Т. 23, № 1. - С. 275-292.
7. Ченцов, А.Г. Задача маршрутизации с ограничениями, зависящими от списка заданий / А.Г. Ченцов, А.А. Ченцов // Доклады Академии наук. - 2015. - Т. 465, № 2. - С. 154-158.
8. Ченцов, А.Г. Маршрутизация в условиях ограничений: задача о посещении мегаполисов / А.Г. Ченцов, П.А. Ченцов // Автоматика и телемеханика. - 2016. - № 11. - С. 96-117.
9. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. - М.: Мир, 1982.
10. Меламед, И.И. Задача коммивояжера. Вопросы теории / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 9. - С. 3-34.
11. Меламед, И.И. Задача коммивояжера. Точные методы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 10. - С. 3-29.
12. Меламед, И.И. Задача коммивояжера. Приближенные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - № 11. - С. 3-26.
13. Gutin, G. The Traveling Salesman Problem and Its Variations / G. Gutin, A. Punnen. - Berlin: Springer, 2002.
14. Cook, W.J. In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation / W.J. Cook. - New Jersey: Princeton University Press, 2012.
15. Беллман, Р. Применение динамического программирования к задаче о коммивояжере / Р. Беллман // Кибернетический сборник. - 1964. - Т. 9. - С. 219-228.
16. Хелд, М. Применение динамического программирования к задачам упорядочения / М. Хелд, Р.М. Карп // Кибернетический сборник. - 1964. - Т. 9. - С. 202-218.
17. Литл, Дж. Алгоритм для решения задачи о коммивояжере / Дж. Литл, К. Мурти, Д. Суини, К. Кэрел // Экономика и математические методы. - 1965. - Т. 1, № 1. - С. 94-107.
18. Wang, G.G. Optimal Process Planning for a Combined Punch-and-Laser Cutting Machine Using and Colony Optimization / G.G. Wang, S.Q. Xie // International Journal of Production Research. - 2005. - V. 43, № 11. - P. 2195-2216.
19. Lee, M.-K. Cutting Path Optimization in CNC Cutting Processes Using a Two-Step Genetic Algorithm / M.-K. Lee, K.-B. Kwon // International Journal of Production Research. - 2006. - V. 44, № 24. - P. 5307-5326.
20. Jing, Y. An Optimized Algorithm of Numerical Cutting-Path Control in Garment Manufacturing / Y. Jing, C. Zhige // Advanced Materials Research. - 2013. - V. 796. - P. 454-457.
21. Ганелина, Н.Д. Исследование методов построения кратчайшего пути обхода отрезков на плоскости / Н.Д. Ганелина, В.Д. Фроловский // Сибирский журнал вычислительной математики. - 2006. - Т. 9, № 3. - С. 241-252.
22. Ченцов, А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории / А.Г. Ченцов. - Ижевск: НИЦ 'Регулярная и хаотическая динамика'. Ижевский институт компьютерных исследований, 2008.
23. Куратовский, К. Теория множеств / К. Куратовский, А. Мостовский. - М.: Мир, 1970.
24. Дьедонне, Ж. Основы современного анализа / Ж. Дьедонне. - М.: Мир, 1964.
25. Кормен, Т. Алгоритмы: Построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. - М.: Московский центр непрерывного математического образования, 2002.