phone +7 (3412) 91 60 92
mail imi@udsu.ru
ru-RU Russian
Home » Issues » Archive of Issues » 2014 - 4 issue » pp. 122-141

Archive of Issues

Russia Yekaterinburg
Year
2014
Issue
4
Pages
122-141
<<
>>
Section Mathematics
Title The Bellmann insertions in the route problem with constraints and complicated cost functions
Author(-s) Chentsov A.G.ab
Affiliations Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciencesa, Ural Federal Universityb
Abstract The problem of sequential circuit of megalopolises with precedence conditions and cost functions that permit a dependence on tasks list is considered. Such problems can arise, in particular, in atomic energetic while investigating the questions connected with lowering of workers irradiation under permutations in radiative fields for realization of services connected with division of radiating elements. Another application of the developed methods is connected with important engineering problem of routing the instrument movements under the leaf cutting on numerically controlled machines. This problem has sufficiently large dimensionality and many precedence conditions: if a detail has not only exterior but at least one interior contours (the simplest example is a washer) then the interior contours must be cut before the cutting of exterior contour (finite sets located near corresponding contours are used as megalopolises). In this case the possible dependence of cost functions on tasks list can reflect various technological conditions. We note that perceptible dimensionality characterized by all contours in total leads to necessity of heuristics employment. Therefore, questions concerning at least local improvement of solutions appear sufficiently important for the investigation. The basic attention in the article is devoted to the construction of optimizing insertions in complicated conditions: it is required to reduce the fragment of precedence conditions and to transform the corresponding cost functions; in the last case, it is important to preserve the dependence on tasks list. Both above-mentioned moments are taken into account under the procedure construction having the sense of algorithm on functional level.
Keywords route, trace, precedence conditions
UDC 519.6
MSC 28A33
DOI 10.20537/vm140410
Received 15 November 2014
Language Russian
Citation Chentsov A.G. The Bellmann insertions in the route problem with constraints and complicated cost functions, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2014, issue 4, pp. 122-141.
References
  1. Petunin A.A. About some strategies of the programming of tool route by developing of control programs for thermal cutting machines, Vestnik UGATU, 2009, vol. 13, no. 2 (35), pp. 280-286 (in Russian).
  2. Tashlykov O.L. Remont oborudovaniya atomnykh stantsii (Repair of equipment of nuclear power plants), Yekaterinburg: USTU-UPI, 2003, 320 p.
  3. Garey M.R., Johnson D.S. Computers and Intractability, New York: Macmillan Higher Education, 1979, 340 p. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Moscow: Mir, 1982, 416 p.
  4. Chentsov A.G. To question of routing of works complexes, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2013, no. 1, pp. 59-82 (in Russian).
  5. Chentsov A.A., Chentsov A.G., Chentsov P.A. Elements of dynamic programming in extremal route problems, Problemy upravleniya, 2013, no. 5, pp. 12-21 (in Russian).
  6. Chentsov A.A., Chentsov A.G. Dynamic programming in the routing problem with complex dependence of costs on the list of jobs, Journal of Computer and Systems Sciences International, 2014, vol. 53, issue 2, pp. 172-185.
  7. Chentsov A.G. Ekstremal'nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii (Extremal problems of routing and assignment of tasks: questions of theory), Moscow-Izhevsk: Institute of Computer Science, 2008, 240 p.
  8. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Problems of the theory, Avtomatika i Telemekhanika, 1989, no. 9, pp. 3-34 (in Russian).
  9. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Exact algorithms, Avtomatika i Telemekhanika, 1989, no. 10, pp. 3-29 (in Russian).
  10. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Approximation algorithms, Avtomatika i Telemekhanika, 1989, no. 11, pp. 3-26 (in Russian).
  11. Bellman R. Application of dynamic programming method for the traveling salesman problem, Kibernet. Sb., Moscow: Mir, 1964, vol. 9, pp. 219-228 (in Russian).
  12. Kheld M., Karp R.M. Application of dynamic programming method for the sorting problems, Kibernet. Sb., Moscow: Mir, 1964, vol. 9, pp. 202-218 (in Russian).
  13. Sigal I.Kh. A decomposition approach to solving a travelling salesman problem of large dimensionality and some applications, Sov. J. Comput. Syst. Sci., 1991, vol. 29, no. 6, pp. 48-58.
  14. Sergeev S.I. Algorithms for the minimax problem of the traveling salesman. I: An approach based on dynamic programming, Autom. Remote Control, 1995, vol. 56, no. 7, pp. 1027-1032.
  15. Barvinok A., Gimadi E.Kh., Serdyukov A.I. The Maximum TSP, The Traveling Salesman problem and its variations, Gutin G., Punnen A.P. (Eds.), Dordrecht-Boston: Kluwer Academic Publishers, 2002, pp. 585-607.
  16. Chentsov A.G. Problem of successive megalopolis traversal with the precedence conditions, Automation and Remote Control, 2014, vol. 75, issue 4, pp. 728-744.
  17. Cormen T., Leiserson Ch., Rivest R. Introduction to algorithms (1st ed.), MIT Press and McGraw-Hill, 1990. Translated under the title Algoritmy. Postroenie i analiz (The algorithms. Construction and analysis), Moscow: Moscow Center for Continuous Mathematical Education, 1990, 960 p.
  18. Kuratowski K., Mostowski A. Teoriya mnozhestv (Theory of sets), Moscow: Mir, 1970, 416 p.
  19. Dieudonne J. Osnovy sovremennogo analiza (Foundations of modern analysis), Мoscow: Mir, 1964, 430 p.
  20. Chentsov A.A., Chentsov A.G. The problem of megalopolises consistent detouring, Vestn. Tambov. Univ. Ser. Estestv. Tekh. Nauki, 2014, vol. 19, no. 2, pp. 454-475 (in Russian).
  21. Petunin A.A., Chentsov A.G., Chentsov P.A. Local dynamic programming incuts in routing problems with restrictions, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2014, no. 2, pp. 56-75 (in Russian).
Full text
/doc/issues-2014/14-04-10.pdf
<< Previous article
Next article >>