Geodesic
About routing in the sheet cutting
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 10 (2017) no. 3, pp. 25-39 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{VYURU_2017_10_3_a2,
     author = {A. A. Petunin and A. G. Chentsov and P. A. Chentsov},
     title = {About routing in the sheet cutting},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {25--39},
     year = {2017},
     volume = {10},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2017_10_3_a2/}
}
TY  - JOUR
AU  - A. A. Petunin
AU  - A. G. Chentsov
AU  - P. A. Chentsov
TI  - About routing in the sheet cutting
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2017
SP  - 25
EP  - 39
VL  - 10
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VYURU_2017_10_3_a2/
LA  - ru
ID  - VYURU_2017_10_3_a2
ER  - 
%0 Journal Article
%A A. A. Petunin
%A A. G. Chentsov
%A P. A. Chentsov
%T About routing in the sheet cutting
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2017
%P 25-39
%V 10
%N 3
%U http://geodesic.mathdoc.fr/item/VYURU_2017_10_3_a2/
%G ru
%F VYURU_2017_10_3_a2
A. A. Petunin; A. G. Chentsov; P. A. Chentsov. About routing in the sheet cutting. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 10 (2017) no. 3, pp. 25-39. http://geodesic.mathdoc.fr/item/VYURU_2017_10_3_a2/

[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, 13:2(35) (2009), 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, 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, 10:2(27) (2008), 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), 103–111

[5] A.A. Chentsov, A.G. Chentsov, “Dynamic Programming Method in the Generalized Traveling Salesman Problem: the Influence of Inexact Calculation”, Mathematical and Computer Modelling, 33:8–9 (2001), 801–819 | DOI | MR | Zbl

[6] Chentsov A. G., Chentsov A. A., “A Discrete-Continuous Routing Problem with Precedence Conditions”, Proceedings of the Institute of Mathematics and Mechanics, 23, no. 1 (2017), 275–292 (in Russian) | Zbl

[7] Chentsov A. G., Chentsov A. A., “Route Problem with Constraints Depending on a List of Tasks”, Doklady Mathematics, 92:3 (2015), 685–688 | DOI | DOI | MR | Zbl

[8] Chentsov A. G., Chentsov P. A., “Routing under Constraints: Problem of Visit to Megalopolises”, Automation and Remote Control, 77:11 (2016), 1957–1974 | DOI | Zbl

[9] Garey M., Johnson D., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman Co., N.Y., 1979, 338 pp. | Zbl

[10] 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 | MR | Zbl

[11] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The Traveling Salesman Problem. Exact Methods”, Automation and Remote Control, 50:10 (1989), 1303–1324 | MR | Zbl

[12] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The Traveling Salesman Problem. Approximate Algorithms”, Automation and Remote Control, 50:11 (1989), 1459–1479 | MR | Zbl

[13] G. Gutin, A. Punnen, The Traveling Salesman Problem and Its Variations, Springer, Berlin, 2002 | MR

[14] W.J. Cook, In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation, Princeton University Press, New Jersey, 2012 | MR | Zbl

[15] Bellman R., “Dynamic Programming Treatment of the Travelling Salesman Problem”, Journal of the Association for Computing Machinery, 9:1 (1962), 61–63 | DOI | MR | Zbl

[16] Held M., Karp R. M., “A Dynamic Programming Approach to Sequencing Problems”, Journal of the Society for Industrial and Applied Mathematics, 10:1 (1962), 196–210 | DOI | MR | Zbl

[17] Little J., Murty K., Sweeney D., Karel C., “An Algorithm for the Traveling Salesman Problem”, Operations Research, 11:6 (1963), 972–989 | DOI | Zbl

[18] G.G. Wang, S.Q. Xie, “Optimal Process Planning for a Combined Punch-and-Laser Cutting Machine Using and Colony Optimization”, International Journal of Production Research, 43:11 (2005), 2195–2216 | DOI | MR

[19] M.-K. Lee, K.-B. Kwon, “Cutting Path Optimization in CNC Cutting Processes Using a Two-Step Genetic Algorithm”, International Journal of Production Research, 44:24 (2006), 5307–5326 | DOI | Zbl

[20] Y. Jing, C. Zhige, “An Optimized Algorithm of Numerical Cutting-Path Control in Garment Manufacturing”, Advanced Materials Research, 796 (2013), 454–457 | DOI

[21] Ganelina N. D., Frolovsky V. D., “On Constructing the Shortest Circuits on a Set of Line Segments”, Siberian Journal of Numerical Mathematics, 9:3 (2006), 241–252 (in Russian)

[22] Chentsov A. G., Extreme Tasks of Routing and Distribution of Tasks: Theory Questions, Izhevsk, 2008

[23] Kuratowski K., Mostowski A., Set Theory, North-Holland Publishing Company, Amsterdam, 1967 | MR

[24] Dieudonne J., Foundations of Modern Analysis, Academic Press, N.Y.–London, 1960 | MR | Zbl

[25] Cormen T., Leiserson C., Rivest R., Introduction to Algorithms, MIT Press, McGraw-Hill, 1990 | MR | Zbl