One task of routing jobs in high radiation conditions

A. G. Chentsov ; A. A. Chentsov ; A. N. Sesekin

Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 58 (2021), pp. 94-126.

Résumé

The problem of sequential bypass of megalopolises is investigated, focused on the problem of dismantling a system of radiation hazardous objects under constraints in the form of precedence conditions. The radiation impact on the performers is assessed by the doses received during movements and during the performance of dismantling works. The route problem of minimizing the dose load of workers carrying out dismantling in one or another sequence of operations is considered. The procedure for constructing an optimal solution using a variant of dynamic programming is investigated. On this basis, an algorithm is built, implemented on a PC. Examples of the numerical solution of a model problem for the minimum dose load are given.

Détail

Keywords: dynamic programming, dismantling
Mots-clés : route.

Bibliographie

[1] Petunin A. A., “About some strategies of the programming of tool route by developing of control programs for thermal cutting machines”, Vestnik Ufimskogo Gosudarstvennogo Aviatsionnogo Tekhnicheskogo Universiteta, 13:2(35) (2009), 280–286 (in Russian)

[2] Chentsov A. G., Chentsov P. A., Petunin A. A., Sesekin A. N., “Model of megalopolises in the tool path optimisation for CNC plate cutting machines”, International Journal of Production Research, 56:14 (2018), 4819–4830 | DOI

[3] Chentsov A. G., Chentsov A. A., Sesekin A. N., Move routing problems with non-additive cost aggregation, URSS, M., 2020

[4] Korobkin V. V., Sesekin A. N., Tashlykov O. L., Chentsov A. G., Routing methods and their applications in improving the safety and efficiency of nuclear power plants operation, Novye Tekhnologii, M., 2002

[5] Chentsov A. G., Chentsov A. A., Sesekin A. N., “On the problem of sequential traversal of megalopolises with precedence conditions and cost functions depending on a list of tasks”, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 26, no. 3, 2020, 219–234 | DOI

[6] Chentsov A. G., Extreme problems of routing and distribution of tasks: theoretical questions, Institute of Computer Science, Izhevsk, 2008

[7] Gutin G., Punnen A. P., The traveling salesman problem and its variations, Springer, Boston, 2007 | DOI | Zbl

[8] Cook W. J., In pursuit of the traveling salesman: mathematics at the limits of computation, Princeton University, Princeton, 2012 | Zbl

[9] Gimadi E. Kh., Khachai M. Yu., Extreme problems on sets of permutations, UMC UPI, Yekaterinburg, 2016

[10] Little G. D. C., Murty K. G., Sweeney D. W., Karel C., “An algorithm for the traveling salesman problem”, Operations Research, 11:6 (1963), 972–989 | DOI | Zbl

[11] Bellman R., “Dynamic programming treatment of the travelling salesman problem”, Journal of the ACM, 9:1 (1962), 61–63 | DOI | Zbl

[12] 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 | Zbl

[13] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. I: Theoretical issues”, Automation and Remote Control, 50:9 (1989), 1147–1173 | Zbl

[14] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. II: Exact methods”, Automation and Remote Control, 50:10 (1989), 1303–1324 | Zbl

[15] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. Approximate algorithms”, Automation and Remote Control, 50:11 (1989), 1459–1479 | Zbl

[16] Kuratowski K., Mostowski A., Set theory, North-Holland, Amsterdam, 1967

[17] Dieudonné J., Foundations of modern analysis, Academic Press, New York, 1960 | Zbl

[18] Cormen T. H., Leiserson C. E., Rivest R. L., Introduction to algorithms, MIT Press, Cambridge, MA, 1990 | Zbl

[19] Chentsov A. G., “To question of routing of works complexes”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2013, no. 1, 59–82 (in Russian) | DOI | Zbl

[20] Cheblokov I. B., Chentsov A. G., “About one route problem with interior works”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2012, no. 1, 96–119 (in Russian) | DOI | Zbl

[21] Chentsov A. G., “A parallel procedure of constructing Bellman function in the generalized courier problem with interior works”, Vestnik Yuzhno-Ural'skogo Universiteta. Ser. Matematicheskoe Modelirovanie i Programmirovanie, 2012, no. 12, 53–76 | Zbl

[22] Chentsov A. A., Chentsov A. G., Sesekin A. N., “An extremal routing problem with constraints and complicated cost functions”, Advanced Control Systems: Theory and Applications, River Publishers, 2021, 21–52

[23] Lawler E. L., Efficient implementation of dynamic programming algorithms for sequencing problems, Stichting Mathematisch Centrum, 1979

[24] Chentsov A. G., Chentsov A. A., “On the question of finding the value of the route problem with restrictions”, Problemy upravleniya i informatiki, 2016, no. 1, 41–54 (in Russian)

[25] Petunin A. A., Chentsov A. G., Chentsov P. A., Optimal tool routing of CNC shaped sheet cutting machines. Mathematical models and algorithms, Ural Federal University, Yekaterinburg, 2020

[26] Chentsov A. G., Chentsov A. A., “A model variant of the problem about radiation sources utilization (iterations based on optimization insertions)”, Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 50 (2017), 83–109 (in Russian) | DOI | Zbl