К вопросу о маршрутизации перемещений при листовой резке деталей
Автор: Петунин Александр Александрович, Ченцов Александр Георгиевич, Ченцов Павел Александрович
Рубрика: Математическое моделирование
Статья в выпуске: 3 т.10, 2017 года.
Бесплатный доступ
Рассматривается решение задачи управления инструментом при листовой резке на машинах с ЧПУ. Предполагается, что исходная постановка осложнена различными ограничениями. Требуется построить решение возникающей задачи маршрутизации, соблюдающее ограничения и минимизирующее аддитивный критерий, включающий стоимости (внешних) перемещений и внутренних работ, связанных с резкой деталей по замкнутому контуру. Соблюдение ограничений предполагается обеспечивать за счет специального задания функций стоимости, т.е. (по сути) за счет формирования штрафов за нарушение требуемых условий. Главную роль играет при этом процедура на базе широко понимаемого динамического программирования. Конструируемый на данной основе алгоритм реализован в виде стандартной программы на многоядерной ПЭВМ. Изложение этого алгоритма составляет основную цель настоящей работы.
Маршрутные задачи, условия предшествования, инженерные ограничения
Короткий адрес: https://sciup.org/147159440
IDR: 147159440 | УДК: 519.6 | DOI: 10.14529/mmp170303
About routing in the sheet cutting
The solution of the problem of tool routing in CNC sheet cutting machines is considered. It is assumed that the initial problem formulation is complicated by different restrictions. It is required to construct a solution of this routing problem that respects the constraints and minimizes the additive criterion, including the costs of (external) displacements and "internal" related to cutting parts on a closed contour works. Compliance of the constraints is supposed to be provided through a special assignment of cost functions, i.e. (in fact) due to the formation of penalties for the restriction violation. The procedure based on widely understood dynamic programming is the main way of problem solving in this paper. The program of problem solving on a multi-core PC is constructed. The presentation of this algorithm is the main goal of this paper.
Список литературы К вопросу о маршрутизации перемещений при листовой резке деталей
- Петунин, А.А. О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала/А.А. Петунин//Вестник УГАТУ. -2009. -Т. 13, № 2 (35). -С. 280-286.
- Фроловский, В.Д. Автоматизация проектирования управляющих программ тепловой резки металла на оборудовании с ЧПУ/В.Д. Фроловский//Информационные технологии в проектировании и производстве. -2005. -№ 4. -С. 63-66.
- Верхотуров, М.А. Математическое обеспечение задачи оптимизации пути режущего инструмента при плоском фигурном раскрое на основе цепной резки/М.А. Верхотуров, П.Ю. Тарасенко//Вестник УГАТУ. -2008. -Т. 10, № 2 (27). -С. 123-130.
- Петунин, А.А. К вопросу о маршрутизации движения инструмента в машинах листовой резки с числовым программным управлением/А.А. Петунин, А.Г. Ченцов, П.А. Ченцов//Научо-технические ведомости СПбГПУ. Серия: Информатика. Телекоммуникации. Управление. -2013. -№ 2 (169). -С. 103-111.
- 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.
- Ченцов, А.Г. Дискретно-непрерывная задача маршрутизации с условиями предшествования/А.Г. Ченцов, А.А. Ченцов//Труды Института математики и механики УрО РАН. -2017. -Т. 23, № 1. -С. 275-292.
- Ченцов, А.Г. Задача маршрутизации с ограничениями, зависящими от списка заданий/А.Г. Ченцов, А.А. Ченцов//Доклады Академии наук. -2015. -Т. 465, № 2. -С. 154-158.
- Ченцов, А.Г. Маршрутизация в условиях ограничений: задача о посещении мегаполисов/А.Г. Ченцов, П.А. Ченцов//Автоматика и телемеханика. -2016. -№ 11. -С. 96-117.
- Гэри, М. Вычислительные машины и труднорешаемые задачи/М. Гэри, Д. Джонсон. -М.: Мир, 1982.
- Меламед, И.И. Задача коммивояжера. Вопросы теории/И.И. Меламед, С.И. Сергеев, И.Х. Сигал//Автоматика и телемеханика. -1989. -№ 9. -С. 3-34.
- Меламед, И.И. Задача коммивояжера. Точные методы/И.И. Меламед, С.И. Сергеев, И.Х. Сигал//Автоматика и телемеханика. -1989. -№ 10. -С. 3-29.
- Меламед, И.И. Задача коммивояжера. Приближенные алгоритмы/И.И. Меламед, С.И. Сергеев, И.Х. Сигал//Автоматика и телемеханика. -1989. -№ 11. -С. 3-26.
- Gutin, G. The Traveling Salesman Problem and Its Variations/G. Gutin, A. Punnen. -Berlin: Springer, 2002.
- Cook, W.J. In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation/W.J. Cook. -New Jersey: Princeton University Press, 2012.
- Беллман, Р. Применение динамического программирования к задаче о коммивояжере/Р. Беллман//Кибернетический сборник. -1964. -Т. 9. -С. 219-228.
- Хелд, М. Применение динамического программирования к задачам упорядочения/М. Хелд, Р.М. Карп//Кибернетический сборник. -1964. -Т. 9. -С. 202-218.
- Литл, Дж. Алгоритм для решения задачи о коммивояжере/Дж. Литл, К. Мурти, Д. Суини, К. Кэрел//Экономика и математические методы. -1965. -Т. 1, № 1. -С. 94-107.
- 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.
- 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.
- 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.
- Ганелина, Н.Д. Исследование методов построения кратчайшего пути обхода отрезков на плоскости/Н.Д. Ганелина, В.Д. Фроловский//Сибирский журнал вычислительной математики. -2006. -Т. 9, № 3. -С. 241-252.
- Ченцов, А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории/А.Г. Ченцов. -Ижевск: НИЦ Регулярная и хаотическая динамика. Ижевский институт компьютерных исследований, 2008.
- Куратовский, К. Теория множеств/К. Куратовский, А. Мостовский. -М.: Мир, 1970.
- Дьедонне, Ж. Основы современного анализа/Ж. Дьедонне. -М.: Мир, 1964.
- Кормен, Т. Алгоритмы: Построение и анализ/Т. Кормен, Ч. Лейзерсон, Р. Ривест. -М.: Московский центр непрерывного математического образования, 2002.
