Layout problems for arc objects in convex domains
Ключові слова:
задача упаковки, довільні об’єкти, неперервні обертання, допустимі відстані, phi-функції, генератор простору розв’язків, вирішувач, нелінійна оптимізаціяАнотація
Розглянуто оптимізаційну задачу упаковки довільних об’єктів, обмежених дугами кіл та відрізками прямих в опуклі області. Побудовано математичну модель у вигляді задачі недиференційованої оптимізації, множина реалізацій якої покриває широкий клас наукових і прикладних задач геометричного проектування. Розроблено методологію розв’язання задач упаковки з урахуванням технологічних обмежень (мінімально допустимі відстані, зони заборони, можливість неперервних трансляцій та обертань об’єктів). Запропоновано генератор простору розв’язків та вирішувач (solver) для автоматичного розв’язання NLP-задач розглянутого класу.Посилання
Wascher, G., Hauner, H., Schuma, H.: An improved typology of cutting and packing problems. European Journal of Operational Research. 183, 1109-1130 (2007).
Gomes, A. M. Irregular Packing Problems: Industrial Applications and New Directions Using Computational Geometry Volume 11 (2014)| Part 1 (DOI) 10.3182/20130522-3-BR-4036.00113, – P. 378-383.
Chazelle, B., Edelsbrunner, H., Guibas, L.J.: The complexity of cutting complexes. Discrete & Computational Geometry. 4(2), 139–81 (1989).
ennell J.A., Oliveira J.F.: The geometry of packing problems: A tutorial. European Journal of Operational Research. 184:397–415 (2008).
Bennell, J.A., Oliveira J.F, A tutorial in irregular shape packing problem, Journal of the Operational Research Society, 60:s93-s105 (2009).
Blazewicz, J., Drozdowski, M., Soniewicki, B., Walkowiak, R.: Two-dimensional cutting problem basic complexity results and algorithms for irregular shapes. Found. Cont. Eng., 14(4), 137-60 (1989).
Burke E.K. Complete and robust no-fit polygon generation for the irregular stock cutting problem / E.K. Burke, R. S. R. Hellier, G. Kendall, G. Whitwell. EJOR 2007 27-49.
Whitwell G. Novel Heuristic and Metaheuristic Approaches to Cutting and Packing. School of Computer Science and Information Technology. University of Nottingham; 2005, PhD Thesis, 313 p.
Burke, E.K., Hellier, R., Kendall, G., Whitwell, G.: Irregular packing using the line and arc no-fit polygon. Operations Research. 58(4), 948–970 (2010).
Milenkovic, V.: Rotational polygon containment and minimum enclosure using only robust 2d constructions. Computational Geometry. 13(1), 3–19 (1999).
Milenkovic, V.: Rotational polygon overlap minimization and compaction. Computational Geometry. 10(4), 305–318 (1998).
Pedro Rocha, Rui Rodrigues, A. Miguel Gomes, Franklina M.B. Toledo, Marina Andretta Circle/ Covering Representation for Nesting problems with continuous rotations. Preprints of the 19th World Congress, The International Federation of Automatic Control, Cape Town, South Africa. August 24-29, 2014.
Leung, Stephen C.H. Lin, Yangbin Zhang, Defu Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem Computers & Operations Research, v.39, no.3, 2012 March, p.678(9) (ISSN: 0305-0548).
J. Bennell, G. Scheithauer, Yu. Stoyan, and T. Romanova (2010) Tools of mathematical modelling of arbitrary object packing problems// J. Annals of Operations Research, Publisher Springer Netherlands: V 179, Issue 1, pp. 343-368.
Chernov N., Stoyan Y., Romanova T. (2010) Mathematical model and efficient algorithms for object packing problem// Computational Geometry: Theory and Applications, vol. 43:5, pp. 535-553.
Chernov N, Stoyan Y, Romanova T and Pankratov A (2012) Phi-functions for 2D objects formed by line segments and circular arcs. Advances in Operations Research. doi:10.1155/2012/346358.
Bennell J., Scheithauer G., Stoyan Y., Romanova T., and Pankratov A. (2014) Global optimisation"Optimal clustering of a pair of irregular objects" Journal of Global Optimisation, JOGO-D-13-00328R2.
Pankratov A.V., Stoyan Yu. G. Placement of non-convex polygons with rotations into a non-convex polygon// Proc. Workshop Cutting Stock Problems. – 2005. Alutus, Miercurea-Ciuc, Romania. – P. 29-36.
Wachter, A., Biegler, L. T. (2006) On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming.106, 1, 25-57.
Yu. Stoyan, A. Pankratov, T. Romanova (2015) Cutting and Packing problems for irregular objects with continuous rotations: mathematical modeling and nonlinear optimization. Journal of Operational Research Society, DOI 10.1057/jors.2015.94.
Josef Kallrath and Steffen Rebennack, "Cutting Ellipses from Area-Minimizing Rectangles" Journal of Global Optimisation, (2013), DOI10.1007/s10898-013-0125-3.
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Авторське право (c) 2016 А. В. Панкратов, T. Romanova, A. Kotelevskiy
Ця робота ліцензується відповідно до Creative Commons Attribution-NoDerivatives 4.0 International License.
Автори, які публікуються в цьому журналі, погоджуються з наступними умовами:
- Автори залишають за собою право на авторство своєї роботи і передають журналу право першої публікації цієї роботи на умовах ліцензійного договору (угоди).
- Автори мають право самостійно укладати додаткові договори (угоди) з неексклюзивного поширення роботи в тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати в складі монографії), за умови збереження посилання на першу публікацію роботи в цьому журналі.
- Політика журналу дозволяє розміщення авторами в мережі Інтернет (наприклад, у сховищах установи або на персональних веб-сайтах) рукопису роботи як до подачі цього рукопису в редакцію, так і під час її редакційної обробки, оскільки це сприяє виникненню продуктивної наукової дискусії і позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
