ЕФЕКТИВНИЙ МЕТОД ОПТИМІЗАЦІЇ В ЗАДАЧАХ ЛІНІЙНОГО РОЗКРОЮ МАТЕРІАЛІВ
Journal Title: Математичне моделювання - Year 2018, Vol 1, Issue 1
Abstract
EFFECTIVE METHOD OF OPTIMIZATION IN A LINEAR MATERIAL CUTTING Kosolap A.I., Kodola G.M. Abstract In this paper the problem of one-dimensional cutting is considered, which has practical application, for example, on the majority of enterprises for the production of double-glazed windows and related enterprises (production of windows, balconies, doors, partitions, etc.). The problem of this industry lies in the fact that a large number of construction companies, using cutting algorithms, which lack an optimization component, are present on the market, and scientific research in this field has been focused on specific modern production tasks. There are many approaches for solving the problem, a thorough analysis of each of which gives its own ways and means to save materials, but often the proposed solutions are either highly specialized or generalized. The urgent task is to create more effective optimization algorithms for solving a cutting task. In the paper, issues of classification of rational cutting and packaging problems were considered. The general scheme of classification of problems of this type is given, mathematical models of this class of problems are considered. The problem of rational decomposition belongs to the class of NP-complete discrete optimization problems of the combinatorial type. An overview of the methods for solving problems of this type, which arise in the production with the implementation of linear cutting of dimensional material, is performed. The scheme-classification of approaches to the solution of the problem of cutting-packing is made. An effective method for solving complex problems of linear cutting is proposed, based on the method of exact quadratic regularization (EQR). The EQR method has an algorithmic basis, therefore, in the presented classification, was attributed to algorithmic methods. The EQR method has shown far better results in solving many of the test multi-extreme problems compared with existing methods. The same is what we observe when solving problems of linear cutting of materials. Examples are given of the solution of the linear cutting problem using residues. References [1] Kantorovich L.V. and Zalgaller V.A. A rational cutting of industrial materials, Edition 3, revised and enlarged. Saint Peterburg: Nevskij Dialekt. 2012. 303 p. (in Russian) [2] Gilmore P.C. A linear programming approach to cutting-stock problem [Text] /P.C. Gilmore, R.E. Gomory //Operations Research. – 1961. – Vol. 9, N 6. – P.849–859. [3] Desaulniers G. Column generation / G. Desaulniers, J. Desrosiers, M. M. Solomon. – New-York: Springer Science + Business Media, Inc., 2005. – 358 p. [4] Dyckhoff H. Cutting and packing in production and distribution [Text]: A typology and bibliography /H. Dyckhoff, U. Finke. – Heidelberg: Physica-Verlag, 1992. – 248 p. [5] Wascher G. An improved typology of cutting and packing problems [Text] /G. Wascher, H. Haussner, H. Schumann //European Journal of Operational Research. – 2007. – Vol. 183, N 3. – P.1109–1130. [6] Romanovskij I. V. Algoritmy resheniya ehkstremal'nyh zadach. – Moscow: Nauka, 1971. 352 p. (in Russian) [7] Martello, S., and Toth, P. Optimal and canonical solutions of the change making problem // European Journal of Operational Research 4, 1980: 322–329. [8] Karelahti, J., Solving the cutting stock problem in the steel industry. Department of Engineering Physics and Mathematics. Master’s thesis, 2002: 1–39. [9] Skobcov YU.A., Balabanov V. N. K voprosu o primenenii metaehvristik v reshenii zadach racional'nogo raskroya i upakovki. Vіsnik Hmel'nic'kogo nacіonal'nogo unіversitetu. 2008. T. 1. no 4. pp. 205–217. (in Russian) [10] Belov G. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths [Text] /G. Belov, G.Scheithauer //European Journal of Operational Research. – 2002. – Vol. 141, N 2. – P. 274–294. [11] Fekete S.P. An exact algorithm for higher-dimensional orthogonal packing [Text] /S.P. Fekete, J. Schepers, J.C. van der Veen //Operations Research. – 2007. – Vol. 55, N 3. – P. 569–587. [12] Poldi K.C. Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths [Text] /K.C. Poldi, M.N. Arenales //Computers & Operations Research. – 2009. – Vol. 36, N 6. – P.2074–2081. [13] Kosolap A.I. (2015), Global optimization. The method of exact quadratic regularization. Dnepropetrovsk: PGASA. 2015. 164 p. (in Russian) [14] Fonotov A. N. Avtomatizirovannaya sistema gil'otinnogo raskroya na osnove geneticheskogo programmirovaniya (na primere mebel'nogo proizvodstva): Dis .... kand. tekhn. nauk: 05.13.07. – Doneck, 2006. (in Russian) [15] Muhacheva EH. A., Kartak V. M. Modificirovannyj metod vetvej i granic: algoritm i Chislennyj ehksperiment dlya zadachi odnomernomu raskroya // Informacionnye tekhnologii. 2000. no 9. pp. 15–22. (in Russian) [16] Kodola G.M., Rogoza B.Є. Pobudova tekhnologіchnoї matricі varіantіv lіnіjnogo rozkroyu [Text] Vіsnik Nacіonal'nogo tekhnіchnogo unіversitetu «HPІ». Harkіv: NTU «HPІ». 2017. – № 23(1245)2017. pp. 111–116. doi:10.20998/2413-4295.2017.23.18. (in Ukrainian) [17] Kosolap A. I. Global'naya optimizaciya. Chislennye ehksperimenty / A. I. Kosolap. Dnepr: PGASA. 2017. 112 p.(in Russian)
Authors and Affiliations
А. І. Косолап, Г. М. Кодола
Keywords
Related Articles
- EP ID EP294849
- DOI 10.31319/2519-8106.1(38)2018.128942
- Views 92
- Downloads 0
ДО ОПТИМІЗАЦІЇ УПРАВЛІННЯ ТЕПЛОВОЮ РОБОТОЮ ПОЛУМЕНЕВИХ ТЕРМІЧНИХ ПЕЧЕЙ КАМЕРНОГО ТИПУ ПІД ЧАС НАГРІВАННЯ МАСИВНИХ ЗЛИВКІВ
TO OPTIMIZATION OF CONTROL BY HEAT WORK FOR FLAMING THERMAL FURNACES CHAMBER TYPE AT HEATING OF MASSIVE BARS Zinchenko V.Yu., Ivanov V.I., Cheprasov A.I., Kayukov Yu.M. Abstract The flaming thermal furnaces of chamber t...
Моделирование получения жаростойких защитных покрытий в условиях самораспространяющегося высокотемпературного синтеза
MODELING OF OBTAINING WELDING PROTECTIVE COATINGS UNDER THE CONDITIONS OF SELF-SPREADING HIGH-TEMPERATURE SYNTHESIS Beigyl O.A., Sereda D.B. Abstract Practical use of carbon-carbon composite materials (CCCM) in high-tem...
Оптимізація роботи металургійного підприємства шляхом аналізу експлуатаційних показників роботи кар’єрних самоскидів
OPTIMIZATION OF THE WORKOF METALLURGICAL ENTERPRISES BY ANALYZING OPERATIONAL PARAMETERS OF THE WORK OF DUMPTRUCKS Sereda B.P., Mukovska D.Y. Abstract In the article a comparative analysis of the spatial performance in...
Про комплексну оцінку фінансової безпеки з лінгвістичним класифікатором
The paper presents the results of the simplest complex estimation of financial safety of the enterprise on the basis of a trapezoidal number a linguistic classifier. Using this method can give the opportunity to improve...
NUMERICAL SIMULATION OF BIOLOGICAL WASTEWATER TREATMENT IN AERATION TANK
NUMERICAL SIMULATION OF BIOLOGICAL WASTEWATER TREATMENT IN AERATION TANK Biliaiev M.M., Kirichenko P.S., Lemesh M.V. Abstract Aeration tanks are widely used in practice for wastewater treatment. Prediction of aeration t...