К вопросу о маршрутизации перемещений при листовой резке деталей
DOI:
https://doi.org/10.14529/mmp170303Ключевые слова:
маршрутные задачи, условия предшествования, инженерные ограниченияАннотация
Рассматривается решение задачи управления инструментом при листовой резке на машинах с ЧПУ. Предполагается, что исходная постановка осложнена различными ограничениями. Требуется построить решение возникающей задачи маршрутизации, соблюдающее ограничения и минимизирующее аддитивный критерий, включающий стоимости (внешних) перемещений и 'внутренних' работ, связанных с резкой деталей по замкнутому контуру. Соблюдение ограничений предполагается обеспечивать за счет специального задания функций стоимости, т.е. (по сути) за счет формирования штрафов за нарушение требуемых условий. Главную роль играет при этом процедура на базе широко понимаемого динамического программирования. Конструируемый на данной основе алгоритм реализован в виде стандартной программы на многоядерной ПЭВМ. Изложение этого алгоритма составляет основную цель настоящей работы.Библиографические ссылки
Petunin A.A. [About Some Strategies of the Programming of Tool Route by Developing of
Control Programs for Thermal Cutting Machines]. Scientic Journal of Ufa State Aviation
Technical University, 2009, vol. 13, no. 2 (35), pp. 280-286. (in Russian)
Frolovskiy V.D. [Automation of Designing of Control Programs of Thermal Cutting of Metal
on the Equipment with CNC]. Information Technology of CAD/CAM/CAE, 2005, no. 4,
pp. 63-66. (in Russian)
Verhoturov M.A., Tarasenko P.Ju. [Mathematical Support of the Task of Optimizing the Path
of the Cutting Tool for Flat Pattern Cutting Based on Chain Cutting]. Scientic Journal of
Ufa State Aviation Technical University, 2008, vol. 10, no. 2 (27), pp. 123130. (in Russian)
Petunin A.A., Chentsov A.G., Chentsov P.A. [To the Question about Instrument Routing in
the Automated Machines of the Sheet Cutting]. St. Petersburg State Polytechnical University
Journal. Computer Science. Telecommunication and Control Systems, 2013, no. 2 (169),
pp. 103-111.
Chentsov A.A., Chentsov A.G. Dynamic Programming Method in the Generalized Traveling
Salesman Problem: the Inffuence of Inexact Calculation. Mathematical and Computer
Modelling, 2001, vol. 33, issues 8-9, pp. 801-819. DOI: 10.1016/S0895-7177(00)00282-X
Chentsov A.G., Chentsov A.A. [A Discrete-Continuous Routing Problem with Precedence
Conditions]. Proceedings of the Institute of Mathematics and Mechanics, 2017, vol. 23, no. 1,
pp. 275292. (in Russian)
Chentsov A.G., Chentsov A.A. Route Problem with Constraints Depending on a List of Tasks.
Doklady Mathematics, 2015, vol. 92, no. 3, pp. 685-688. DOI: 10.1134/S1064562415060083
Chentsov A.G., Chentsov P.A. Routing under Constraints: Problem of Visit to
Megalopolises. Automation and Remote Control, 2016, vol. 77, no. 11, pp. 1957-1974.
DOI: 10.1134/S0005117916110060
Garey M., Johnson D. Computers and Intractability: A Guide to the Theory of NPCompleteness. N.Y., W.H. Freeman & Co., 1979, 338 p.
Melamed I.I., Sergeev S.I., Sigal I.Kh. The Traveling Salesman Problem. Issues in Theory.
Automation and Remote Control, 1989, vol. 50, no. 9, pp. 1147-1173. (in Russian)
Melamed I.I., Sergeev S.I., Sigal I.Kh. The Traveling Salesman Problem. Exact Methods.
Automation and Remote Control, 1989, vol. 50, no. 10, pp. 1303-1324.
Melamed I.I., Sergeev S.I., Sigal I.Kh. The Traveling Salesman Problem. Approximate
Algorithms. Automation and Remote Control, 1989, vol. 50, no. 11, pp. 14590-1479.
Gutin G., Punnen A. The Traveling Salesman Problem and Its Variations. Berlin, Springer,
Cook W.J. In Pursuit of the Traveling Salesman, Mathematics at the Limits of Computation.
New Jersey, Princeton University Press, 2012.
Bellman R. Dynamic Programming Treatment of the Travelling Salesman Problem.
Journal of the Association for Computing Machinery, 1962, vol. 9, issue 1, pp. 61-63.
DOI: 10.1145/321105.321111
Held M., Karp R.M. A Dynamic Programming Approach to Sequencing Problems. Journal
of the Society for Industrial and Applied Mathematics, 1962, vol. 10, no. 1, pp. 196-210.
DOI: 10.1137/0110015
Little J., Murty K., Sweeney D., Karel C. An Algorithm for the Traveling Salesman Problem.
Operations Research, 1963, vol. 11, issue 6, pp. 972-989. DOI: 10.1287/opre.11.6.972
Wang G.G., Xie S.Q. Optimal Process Planning for a Combined Punch-and-Laser Cutting
Machine Using and Colony Optimization. International Journal of Production Research, 2005,
vol. 43, issue 11, pp. 2195-2216. DOI: 10.1080/00207540500070376
Lee M.-K., Kwon K.-B. Cutting Path Optimization in CNC Cutting Processes Using a TwoStep Genetic Algorithm. International Journal of Production Research, 2006, vol. 44, issue 24,
pp. 53075326. DOI: 10.1080/00207540600579615
Jing Y., Zhige C. An Optimized Algorithm of Numerical Cutting-Path Control in Garment
Manufacturing. Advanced Materials Research, 2013, vol. 796, pp. 454-457.
Ganelina N.D., Frolovsky V.D. [On Constructing the Shortest Circuits on a Set of Line
Segments]. Siberian Journal of Numerical Mathematics, 2006, vol. 9, no. 3, pp. 241-252. (in
Russian)
Chentsov A.G. Ekstremal'nye zadachi marshrutizacii i raspredeleniya zadaniy: voprosy teorii
[Extreme Tasks of Routing and Distribution of Tasks: Theory Questions], Izhevsk, 2008.
Kuratowski K., Mostowski A. Set Theory. Amsterdam, North-Holland Publishing Company,
Dieudonne J. Foundations of Modern Analysis. N.Y., London, Academic Press, 1960.
Cormen T., Leiserson C., Rivest R. Introduction to Algorithms. MIT Press, McGraw-Hill,
