ABOUT ROUTING IN THE SHEET CUTTING
DOI:
https://doi.org/10.14529/mmp170303Keywords:
routing problem, precedence conditions, engineering constraintsAbstract
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 dierent 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.References
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,
