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.

Keywords

routing problem; precedence conditions; engineering constraints.

References

1. Petunin A.A. [About Some Strategies of the Programming of Tool Route by Developing of Control Programs for Thermal Cutting Machines]. Scientific Journal of Ufa State Aviation Technical University, 2009, vol. 13, no. 2 (35), pp. 280-286. (in Russian)
2. 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)
3. 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]. Scientific Journal of Ufa State Aviation Technical University, 2008, vol. 10, no. 2 (27), pp. 123-130. (in Russian)
4. 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.
5. Chentsov A.A., Chentsov A.G. Dynamic Programming Method in the Generalized Traveling Salesman Problem: the Influence of Inexact Calculation. Mathematical and Computer Modelling, 2001, vol. 33, issues 8-9, pp. 801-819. DOI: 10.1016/S0895-7177(00)00282-X
6. 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. 275-292. (in Russian)
7. 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
8. 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
9. Garey M., Johnson D. Computers and Intractability: A Guide to the Theory of NP-Completeness. N.Y., W.H. Freeman & Co., 1979, 338 p.
10. 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)
11. 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.
12. 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. 1459-1479.
13. Gutin G., Punnen A. The Traveling Salesman Problem and Its Variations. Berlin, Springer, 2002.
14. Cook W.J. In Pursuit of the Traveling Salesman, Mathematics at the Limits of Computation. New Jersey, Princeton University Press, 2012.
15. 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
16. 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
17. 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
18. 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
19. Lee M.-K., Kwon K.-B. Cutting Path Optimization in CNC Cutting Processes Using a Two-Step Genetic Algorithm. International Journal of Production Research, 2006, vol. 44, issue 24, pp. 5307-5326. DOI: 10.1080/00207540600579615
20. Jing Y., Zhige C. An Optimized Algorithm of Numerical Cutting-Path Control in Garment Manufacturing. Advanced Materials Research, 2013, vol. 796, pp. 454-457.
21. 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)
22. Chentsov A.G. Ekstremal'nye zadachi marshrutizacii i raspredeleniya zadaniy: voprosy teorii [Extreme Tasks of Routing and Distribution of Tasks: Theory Questions], Izhevsk, 2008.
23. Kuratowski K., Mostowski A. Set Theory. Amsterdam, North-Holland Publishing Company, 1967.
24. Dieudonne J. Foundations of Modern Analysis. N.Y., London, Academic Press, 1960.
25. Cormen T., Leiserson C., Rivest R. Introduction to Algorithms. MIT Press, McGraw-Hill, 1990.