maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2015-2-278-294mais-246Research ArticleОригинальные статьиArticlesОб одной задаче маршрутизации перемещений инструмента при листовой резке деталейAbout a Routing Problem of the Tool Motion on Sheet CuttingПетунинАлександр АлександровичPetuninA. A.

доктор технических наук, профессор, 620002, Россия, г.Екатеринбург, ул. Мира, 19,

доктор технических наук, профессор, Mira str., 19, Ekaterinburg, 620002, Russia

aapetunin@gmail.comЧенцовАлександр ГеоргиевичChentsovA. G.

член-корреспондент РАН, профессор,  620990, Россия, г.Екатеринбург, ул. Софьи Ковалевской, 16

член-корреспондент РАН, профессор, Sofia Kovalevskaya str., 16, Ekaterinburg, 620990, Russia

chentsov@imm.uran.ruЧенцовПавел АлександровичChentsovP. A.

кандидат физико-математических наук, 620990, Россия, г.Екатеринбург, ул. Софьи Ковалевской, 16

кандидат физико-математических наук, Sofia Kovalevskaya str., 16, Ekaterinburg, 620990, Russia

chentsov.p@uran.ruУральский федеральный университетРоссияUral Federal UniversityRussian FederationИнститут математики и механики им. Н.Н. Красовского УрО РАН, Уральский федеральный университетРоссияN.N. Krasovskii Institute of Mathematics and MechanicsRussian Federation201520042015222278294Copyright © Петунин А.А., Ченцов А.Г., Ченцов П.А., 20152015Петунин А.А., Ченцов А.Г., Ченцов П.А.Petunin A.A., Chentsov A.G., Chentsov P.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/246

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

For the routing problem of tool permutations under the thermal cutting of parts from sheet material realized on CNC machines, questions connected with constructing precise (optimal) and heuristic algorithms used on the stage of mathematical simulation of route elements under sequential megalopolises circuit are investigated. Cutting points and points of tool cut-off are items (cities) of the above-mentioned megalopolises. In each megalopolis, interior works are provided. These works are connected with motion to the equidistant curve of the cut contour of a part from the cutting point and (with cutting completed) with motion from the equidistant curve to the tool cut-off (we keep in mind a working run). The problem about the time-optimal process of cutting which is a special variant of the generalized courier problem is investigated (the problem of the routing on the megalopolises with precedence conditions). An optimal procedure based on the dynamic programming and an effective heuristic algorithm realized on a multicore computer are proposed. A dynamic programming based procedure uses a special extension of the main problem. This extension provides the replacement of admissibility by precedence with the admissibility by deletion (from the list of tasks). Precedence conditions are used for decreasing computational complexity: it excludes the building of the whole array of the Bellman function values (this function is replaced by the layers system).

аршрутная задачаусловие предшествованияouting problempreceding conditionПрезидиум РАН, РФФИ, региональная целевая программа РЦП-13-П1-1030ReferencesМеламед И. И., Сергеев С. И., Сигал И. Х., “Задача коммивояжера. Вопросы теории”, Автоматика и телемеханика, 1989, № 9, 3–34; English transl.: Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. Issues in theory”, Automation and Remote Control, 50:9 (1989), 1147–1173.Меламед И. И., Сергеев С. И., Сигал И. Х., “Задача коммивояжера. Вопросы теории”, Автоматика и телемеханика, 1989, № 9, 3–34; English transl.: Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. Issues in theory”, Automation and Remote Control, 50:9 (1989), 1147–1173.Меламед И. И., Сергеев С. И., Сигал И. Х., “Задача коммивояжера. Точные алгоритмы”, Автоматика и телемеханика, 1989, № 10, 3–29; English transl.: Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman’s problem. Exact methods”, Automation and Remote Control, 50:10 (1989), 1303–1324.Меламед И. И., Сергеев С. И., Сигал И. Х., “Задача коммивояжера. Точные алгоритмы”, Автоматика и телемеханика, 1989, № 10, 3–29; English transl.: Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman’s problem. Exact methods”, Automation and Remote Control, 50:10 (1989), 1303–1324.Меламед И. И., Сергеев С. И., Сигал И. Х., “Задача коммивояжера. Приближенные алгоритмы”, Автоматика и телемеханика, 1989, № 11, 3–26; English transl.: Melamed I. I., Sergeev S.I., Sigal I. Kh., “The traveling salesman problem. Approximate algorithms”, Automation and Remote Control, 50:11 (1989), 1459–1479.Меламед И. И., Сергеев С. И., Сигал И. Х., “Задача коммивояжера. Приближенные алгоритмы”, Автоматика и телемеханика, 1989, № 11, 3–26; English transl.: Melamed I. I., Sergeev S.I., Sigal I. Kh., “The traveling salesman problem. Approximate algorithms”, Automation and Remote Control, 50:11 (1989), 1459–1479.Сигал И. Х., “Декомпозиционный подход к решению задачи коммивояжера большой размерности и некоторые его приложения”, Известия АН СССР, Техническая кибернетика, 1990, № 6, 143–155; English transl.: Sigal I. Kh., “A decomposition approach to solving a travelling salesman problem of lange dimensionality and some applications”, Soviet journal of Computer and Systems Sciences, 1991, № 6, 48–60.Сигал И. Х., “Декомпозиционный подход к решению задачи коммивояжера большой размерности и некоторые его приложения”, Известия АН СССР, Техническая кибернетика, 1990, № 6, 143–155; English transl.: Sigal I. Kh., “A decomposition approach to solving a travelling salesman problem of lange dimensionality and some applications”, Soviet journal of Computer and Systems Sciences, 1991, № 6, 48–60.Schrijver A, Combinatorial Optimization, Springer, Berlin, 2003, 648 pp.Schrijver A, Combinatorial Optimization, Springer, Berlin, 2003, 648 pp.Ченцов А. Г., Экстремальные задачи маршрутизации и распределения заданий: вопросы теории, НИЦ “Регулярная и хаотическая динамика”, Ижевский институт компьютерных исследований, М.; Ижевск, 2008, 240 с., [Chentsov A. G., Ekstremalnye zadachi marshrutizatsii i raspredeleniya zadaniy: voprosy teorii, NITs “Regulyarnaya i khaoticheskaya dinamika”, Izhevskiy institut kompyuternykh issledovaniy, Moskva; Izhevsk, 2008, 240 s., (in Russian).]Ченцов А. Г., Экстремальные задачи маршрутизации и распределения заданий: вопросы теории, НИЦ “Регулярная и хаотическая динамика”, Ижевский институт компьютерных исследований, М.; Ижевск, 2008, 240 с., [Chentsov A. G., Ekstremalnye zadachi marshrutizatsii i raspredeleniya zadaniy: voprosy teorii, NITs “Regulyarnaya i khaoticheskaya dinamika”, Izhevskiy institut kompyuternykh issledovaniy, Moskva; Izhevsk, 2008, 240 s., (in Russian).]Петунин А. А., “О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала”, Вестник УГАТУ, Сер. Управление, вычислительная техника и информатика, 13, 2009, 280–286; [Petunin A. A., “O nekotorykh strategiyakh formirovaniya marshruta instrumenta pri razrabotke upravlyayushchikh programm dlya mashin termicheskoy rezki materiala”, Vestnik UGATU, Ser. Upravlenie, vychislitelnaya tekhnika i informatika, 13, 2009, 280–286, (in Russian).]Петунин А. А., “О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала”, Вестник УГАТУ, Сер. Управление, вычислительная техника и информатика, 13, 2009, 280–286; [Petunin A. A., “O nekotorykh strategiyakh formirovaniya marshruta instrumenta pri razrabotke upravlyayushchikh programm dlya mashin termicheskoy rezki materiala”, Vestnik UGATU, Ser. Upravlenie, vychislitelnaya tekhnika i informatika, 13, 2009, 280–286, (in Russian).]Ченцов А. Г., “К вопросу о маршрутизации комплексов работ”, Вестн. УдГУ, Математика. Механика. Компьютерные науки, 1, 2013, 59–82; [Chentsov A. G., “K voprosu o marshrutizatsii kompleksov rabot”, Vestn. UdGU, Matematika. Mekhanika. Kompyuternye nauki, 1, 2013, 59–82, (in Russian).]Ченцов А. Г., “К вопросу о маршрутизации комплексов работ”, Вестн. УдГУ, Математика. Механика. Компьютерные науки, 1, 2013, 59–82; [Chentsov A. G., “K voprosu o marshrutizatsii kompleksov rabot”, Vestn. UdGU, Matematika. Mekhanika. Kompyuternye nauki, 1, 2013, 59–82, (in Russian).]Burkard R., Dell’Amico M., Martello S., Assignment Problem, SIAM, Philadelphia, 2009, 382 pp.Burkard R., Dell’Amico M., Martello S., Assignment Problem, SIAM, Philadelphia, 2009, 382 pp.Gutin G., Punnen A., The Traveling Salesman Problem and Its Variations, Springer, Berlin, 2002, 850 pp.Gutin G., Punnen A., The Traveling Salesman Problem and Its Variations, Springer, Berlin, 2002, 850 pp.Chentsov A. A., Chentsov A. G., “Dynamic Programming Method in the Generalized Traveling Salesman Problem: The Influence of Inexact Calculations”, Mathl. Comput. Modelling, 33 (2001), 801–819.Chentsov A. A., Chentsov A. G., “Dynamic Programming Method in the Generalized Traveling Salesman Problem: The Influence of Inexact Calculations”, Mathl. Comput. Modelling, 33 (2001), 801–819.Chentsov A. G., Korotayeva L. N., “The Dynamic Programming Method in the Generalized Salesman Problem”, Mathl. Comput. Modelling, 25:1 (1997), 93–105.Chentsov A. G., Korotayeva L. N., “The Dynamic Programming Method in the Generalized Salesman Problem”, Mathl. Comput. Modelling, 25:1 (1997), 93–105.Renaud J., Boctor F. F., Ouenniche J., “A heuristic for the pickup and delivery traveling salesman problem”, Computers & Operations Research, 2000, № 27, 905–916.Renaud J., Boctor F. F., Ouenniche J., “A heuristic for the pickup and delivery traveling salesman problem”, Computers & Operations Research, 2000, № 27, 905–916.Garey M., Johnson D., Computers and Intractability: A Guide to the Theory of NPCompleteness, ed. W. H. Freeman, 1979, 338 pp.; Гэри М., Джонсон Д., Вычислительные машины и труднорешаемые задачи, Мир, М., 1982, 416 с.Garey M., Johnson D., Computers and Intractability: A Guide to the Theory of NPCompleteness, ed. W. H. Freeman, 1979, 338 pp.; Гэри М., Джонсон Д., Вычислительные машины и труднорешаемые задачи, Мир, М., 1982, 416 с.Bellman R., “On a Routing Problem”, Quart. Appl. Math., 16 (1958), 87–90.Bellman R., “On a Routing Problem”, Quart. Appl. Math., 16 (1958), 87–90.Held M., Karp R. M., “A Dynamic Programming Approach to Sequencing Problems”, Journal of the Society for Industrial and Applied Mathematics, 1962, № 10(1), 196–210.Held M., Karp R. M., “A Dynamic Programming Approach to Sequencing Problems”, Journal of the Society for Industrial and Applied Mathematics, 1962, № 10(1), 196–210.Castelino K., D’Souza R., Wright P., “Toolpath optimization for minimizing airtime during machining”, Journal of Manufacturing Systems, 2003, № 22(3), 173–180.Castelino K., D’Souza R., Wright P., “Toolpath optimization for minimizing airtime during machining”, Journal of Manufacturing Systems, 2003, № 22(3), 173–180.Dewil R., Vansteenwegen P., Cattrysse D., “Cutting Path Optimization Using Tabu Search”, Key Engineering Materials 473, 2011, 739–748.Dewil R., Vansteenwegen P., Cattrysse D., “Cutting Path Optimization Using Tabu Search”, Key Engineering Materials 473, 2011, 739–748.Jing Y., Zhige C, “An Optimized Algorithm of Numerical Cutting-Path Control in Garment Manufacturing”, Advanced Materials Research 796, 2013, 454–457.Jing Y., Zhige C, “An Optimized Algorithm of Numerical Cutting-Path Control in Garment Manufacturing”, Advanced Materials Research 796, 2013, 454–457.Wang G. G., Xie S. Q., “Optimal process planning for a combined punch-and-laser cutting machine using ant colony optimization”, International Journal of Production Research, 43:11 (2005), 2195–2216.Wang G. G., Xie S. Q., “Optimal process planning for a combined punch-and-laser cutting machine using ant colony optimization”, International Journal of Production Research, 43:11 (2005), 2195–2216.Куратовский К., Мостовский А., Теория множеств, Мир, М., 1970, 416 с.; Kuratowski K., Mostowski A., Set Theory, North-Holland Publishing Company, Amsterdam, 1967, 417 pp.Куратовский К., Мостовский А., Теория множеств, Мир, М., 1970, 416 с.; Kuratowski K., Mostowski A., Set Theory, North-Holland Publishing Company, Amsterdam, 1967, 417 pp.Дьедонне Ж., Основы современного анализа, Мир, М., 1964, 430 с.; Dieudonne J., Foundations of Modern Analysis, Academic Press, New York, 1960, 361 pp.Дьедонне Ж., Основы современного анализа, Мир, М., 1964, 430 с.; Dieudonne J., Foundations of Modern Analysis, Academic Press, New York, 1960, 361 pp.Варга Дж., Оптимальное управление дифференциальными и функциональными уравнениями, Наука, М., 1977, 624 с.; Warga J., Optimal Control of Differential and Functional Equations, Academic Press, 1972, 546 pp.Варга Дж., Оптимальное управление дифференциальными и функциональными уравнениями, Наука, М., 1977, 624 с.; Warga J., Optimal Control of Differential and Functional Equations, Academic Press, 1972, 546 pp.Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: Построение и анализ, МЦН-МО, 2002, 960 с.; Chentsov A. G., Ekstremalnye zadachi marshrutizatsii i raspredeleniyazadaniy: voprosy teorii, NITs ”Regulyarnaya i khaoticheskaya dinamika”, Izhevskiy institut kompyuternykh issledovaniy, Moskva; Izhevsk, 2008, 240 pp.Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: Построение и анализ, МЦН-МО, 2002, 960 с.; Chentsov A. G., Ekstremalnye zadachi marshrutizatsii i raspredeleniyazadaniy: voprosy teorii, NITs ”Regulyarnaya i khaoticheskaya dinamika”, Izhevskiy institut kompyuternykh issledovaniy, Moskva; Izhevsk, 2008, 240 pp.Энгелькинг Р., Общая топология, Мир, М., 1986, 751 с., Engelking R., General Topology, Polish Scientific Publishers, 1977, 626 pp.Энгелькинг Р., Общая топология, Мир, М., 1986, 751 с., Engelking R., General Topology, Polish Scientific Publishers, 1977, 626 pp.Dewil R., Vansteenwegen P., Cattrysse D., “Construction heuristics for generating tool paths for laser cutters”, International Journal of Production Research, 2014, 1–20.Dewil R., Vansteenwegen P., Cattrysse D., “Construction heuristics for generating tool paths for laser cutters”, International Journal of Production Research, 2014, 1–20.

The authors declare that there are no conflicts of interest present.