ЗАДАЧИ КОМПОНОВКИ ПРОИЗВОЛЬНЫХ ОБЪЕКТОВ В ВЫПУКЛЫХ ОБЛАСТЯХ

image_print
DOI https://doi.org/10.15407/pmach2016.03.043
Журнал Проблемы машиностроения
Издатель Институт проблем машиностроения им. А. Н. Подгорного Национальной академии наук Украины
ISSN 0131-2928 (print), 2411-0779 (online)
Выпуск Том 19, № 3, 2016 (сентябрь)
Страницы 43-60

 

Авторы

А. В. Панкратов, Институт проблем машиностроения им. А. Н. Подгорного НАН Украины (61046, Украина, г. Харьков, ул. Пожарского, 2/10), e-mail: impankratov@mail.ru, ORCID: 0000-0002-2958-8923

Т. Е. Романова, Институт проблем машиностроения им. А. Н. Подгорного НАН Украины (61046, Украина, г. Харьков, ул. Пожарского, 2/10), e-mail: sherom@kharkov.ua, ORCID: 0000-0002-8618-4917

А. И. Котелевский, Институт проблем машиностроения им. А. Н. Подгорного НАН Украины (61046, Украина, г. Харьков, ул. Пожарского, 2/10)

 

Аннотация

Рассмотрена оптимизационная задача упаковки произвольных объектов, ограниченных дугами окружностей и отрезками прямых в выпуклые области. Построена математическая модель в виде задачи недифференцируемой оптимизации, множество реализаций которой покрывает широкий класс научных и прикладных задач геометрического проектирования. Разработана методология решения задач упаковки с учетом технологических ограничений (минимально допустимые расстояния, зоны запрета, возможность непрерывных трансляций и вращений объектов). Предложен генератор пространства решений и решатель (solver) для автоматического решения NLP-задач рассматриваемого класса.

 

Ключевые слова: задача упаковки, произвольные объекты, непрерывные вращения, допустимые расстояния, phi -функции; генератор пространства решений; нелинейная оптимизация.

 

Литература

  1. Wаscher, G. An improved typology of cutting and packing problems / G. Wаscher, H. Hauner, H. Schumann // European J. Operational Research. – 2007. – № 183 (3). – P. 1109–1130. https://doi.org/10.1016/j.ejor.2005.12.047
  2. Gomes, A. M. Irregular Packing Problems: Industrial Applications and New Directions Using Computational Geometry / A. M. Gomes // IFAC Proc. Volumes. – 2013. – Vol. 46 (7). – P. 378–383. https://doi.org/10.3182/20130522-3-BR-4036.00113
  3. Chazelle, B. The complexity of cutting complexes / B. Chazelle, H. Edelsbrunner, L. J. Guibas // Discr. & Comput. Geom. – 1989. – № 4 (2). – P. 81–139. https://doi.org/10.1007/BF02187720
  4. Bennell, J. A. The geometry of packing problems: A tutorial / J. A. Bennell, J. F. Oliveira // European J. Operational Research. – 2008. – № 184 (2) – P. 397–415. https://doi.org/10.1016/j.ejor.2006.11.038
  5. Bennell, J. A tutorial in irregular shape packing problem / J. A. Bennell, J. F. Oliveira // Oper. Research Soc. – 2009. – Vol. 60. – P. 93–105. https://doi.org/10.1057/jors.2008.169
  6. Two-dimensional cutting problem basic complexity results and algorithms for irregular shapes / J.Blazewicz, M. Drozdowski, B. Soniewicki, R. Walkowiak // Found. Cont. – 1989. – № 14 (4). – P. 137–160.
  7. 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. – № 179 (1). – P. 27–49. https://doi.org/10.1016/j.ejor.2006.03.011
  8. 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.
  9. Irregular packing using the line and arc no-fit polygon / E. Burke, R. Hellier, G. Kendall, G. Whitwell // Operations Research. –2010. – № 58 (4). – P. 948–970. https://doi.org/10.1287/opre.1090.0770
  10. Milenkovic, V. Rotational polygon containment and minimum enclosure using only robust 2d constructions / V. Milenkovic // Computational Geometry. –1999. – №13 (1). – P. 3–19. https://doi.org/10.1016/S0925-7721(99)00006-1
  11. Milenkovic, V. Rotational polygon overlap minimization and compaction / V. Milenkovic // Computational Geometry. –1998. – № 10 (4). – P. 305–318. https://doi.org/10.1016/S0925-7721(98)00012-1
  12. Circle Covering Representation for Nesting problems with continuous rotations / P. Rocha, R. Rodrigues, A. M. Gomes et al. // Preprints of the 19th World Congress, The International Federation of Automatic Control, Cape Town, South Africa. August 24–29. – 2014. https://doi.org/10.3182/20140824-6-ZA-1003.01663
  13. Leung, S. C. H. Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem / S. C. H. Leung, Y. Lin, D. Zhang // Computers & Operations Research. – 2012. – № 39 (3). – P. 678–686. https://doi.org/10.1016/j.cor.2011.05.025
  14. Tools of mathematical modelling of arbitrary object packing problems/ J.Bennell, G.Scheithauer, Yu. Stoyan, T. Romanova // J. Annals of Operations Research, Publisher Springer Netherlands. – 2010. – № 179(1). – P. 343–368. https://doi.org/10.1007/s10479-008-0456-5
  15. Chernov, N. Mathematical model and efficient algorithms for object packing problem / N. Chernov, Yu. Stoyan, T.  Romanova // Computational Geometry: Theory and Appl. – 2010. – № 43 (5). – P. 533–553. https://doi.org/10.1016/j.comgeo.2009.12.003
  16. Phi-functions for 2D objects formed by line segments and circular arcs / N. Chernov, Y. Stoyan, T. Romanova, A. Pankratov // Advances in Operations Research. –2012. – 26 p. https://doi.org/10.1155/2012/346358
  17. Optimal clustering of a pair of irregular objects / J. Bennell, G. Scheithauer, Y. Stoyan et al. // J. Global Optimisation. – 2015. – № 61 (3). – P. 497–524. https://doi.org/10.1007/s10898-014-0192-0
  18. Pankratov, A. V. Placement of non-convex polygons with rotations into a non-convex polygon / A. V. Pankratov, Yu. G. Stoyan // Proc. Workshop Cutting Stock Problems. – 2005. Alutus, Miercurea-Ciuc, Romania. – P. 29–57.
  19. Wachter, A. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming/ A. Wachter, L.  T.  Biegler // Mathematical Programming. – 2006. – № 106 (1). – P. 25–57. https://doi.org/10.1007/s10107-004-0559-y
  20. Stoyan, Yu. Cutting and Packing problems for irregular objects with continuous rotations: mathematical modeling and nonlinear optimization / Yu. Stoyan, A. Pankratov, T. Romanova // J. Operational Research Society, – 2016. –№ 67 (5). – P. 786–800. https://doi.org/10.1057/jors.2015.94
  21. Kallrath, J. Cutting Ellipses from Area-Minimizing Rectangles / J.Kallrath, S. Rebennack // J. Global Optimisation. – 2014. – № 59 (2–3). – P. 405–437. https://doi.org/10.1007/s10898-013-0125-3

 

Поступила в редакцию 06 сентября 2016 г.