J. of Mech. Eng., 2016, vol. 19, no. 3, pp. 43-60
|Journal||Journal of Mechanical Engineering|
|Publisher||A. Podgorny Institute for Mechanical Engineering Problems
National Academy of Science of Ukraine
|ISSN||0131-2928 (Print), 2411-0779 (Online)|
|Issue||Vol. 19, no. 3, 2016 (September)|
A. Kotelevskiy, A. Podgorny Institute of Mechanical Engineering Problems of NASU (2/10, Pozharsky St., Kharkiv, 61046, Ukraine)
The optimization problem of packing arbitrary objects bounded by arcs of circles and straight line segments into convex regions is considered. A mathematical model is constructed in the form of a problem of non-differentiable optimization, whose set of realizations covers a wide class of scientific and applied problems of geometric design. A methodology for solving packaging problems is developed, taking into account technological constraints (minimum allowable distances, prohibition zones, possibility of continuous transmissions and rotation of objects). A decision space generator and a solver for automatically solving NLP problems of the class under consideration are proposed.
Keywords: packing problem, arbitrary objects, continuous rotations, allowable distances, phi- functions; decision space generator; nonlinear optimization
- Wascher, G., Hauner, H., & Schuma, H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research, no. 183, pp. 1109-1130. https://doi.org/10.1016/j.ejor.2005.12.047
- Gomes, A. M. (2013). Irregular Packing Problems: Industrial Applications and New Directions Using Computational Geometry. IFAC Proc. Volumes, vol. 46 (7), pp. 378-38311. https://doi.org/10.3182/20130522-3-BR-4036.00113
- Chazelle, B., Edelsbrunner, H., & Guibas, L. J. (1989). The complexity of cutting complexes. Discrete & Computational Geometry, no. 4(2), pp. 139–81. https://doi.org/10.1007/BF02187720
- Bennell, J. A. & Oliveira J. F. (2008). The geometry of packing problems: A tutorial. European Journal of Operational Research, no. 184(2), pp. 397–415. https://doi.org/10.1016/j.ejor.2006.11.038
- Bennell, J. A. & Oliveira J. F. (2009). A tutorial in irregular shape packing problem. Journal of the Operational Research Society, vol. 60, pp. 93–105. https://doi.org/10.1057/jors.2008.169
- Blazewicz, J., Drozdowski, M., Soniewicki, B., & Walkowiak, R. (1989). Two-dimensional cutting problem basic complexity results and algorithms for irregular shapes. Found. Cont. Eng., no. 14 (4), pp. 137–160.
- Burke, E. K., Hellier, R. S. R., Kendall, G., & Whitwell, G. (2007). Complete and robust no-fit polygon generation for the irregular stock cutting problem. EJOR, no. 179, pp. 27–49. https://doi.org/10.1016/j.ejor.2006.03.011
- Whitwell, G. (2005). Novel Heuristic and Metaheuristic Approaches to Cutting and Packing. PhD Thesis. School of Computer Science and Information Technology, University of Nottingham, 313 p.
- Burke, E.K., Hellier, R., Kendall, G., & Whitwell, G. (2010). Irregular packing using the line and arc no-fit polygon. Operations Research, no. 58 (4), pp. 948–970. https://doi.org/10.1287/opre.1090.0770
- Milenkovic, V. (1999). Rotational polygon containment and minimum enclosure using only robust 2d constructions. Computational Geometry, no. 13(1), pp. 3–19. https://doi.org/10.1016/S0925-7721(99)00006-1
- Milenkovic, V. (1998). Rotational polygon overlap minimization and compaction. Computational Geometry, no. 10(4), pp. 305–318. https://doi.org/10.1016/S0925-7721(98)00012-1
- Rocha, P., Rodrigues, R., Gomes, A. M., et al. (2014). 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. https://doi.org/10.3182/20140824-6-ZA-1003.01663
- Leung, S. C. H., Lin, Y., & Zhang, D. (2012). Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem. Computers & Operations Research, vol. 39, no. 3, pp. 678–686. https://doi.org/10.1016/j.cor.2011.05.025
- Bennell, J., Scheithauer, G., Stoyan, Yu., & Romanova, T. (2010) Tools of mathematical modelling of arbitrary object packing problems. Annals of Operations Research, Publisher Springer Netherlands, vol. 179, iss. 1, pp. 343–368. https://doi.org/10.1007/s10479-008-0456-5
- Chernov, N., Stoyan, Y., & Romanova, T. (2010). Mathematical model and efficient algorithms for object packing problem. Computational Geometry, Theory and Applications, vol. 43, no. 5, pp. 535–553. https://doi.org/10.1016/j.comgeo.2009.12.003
- Chernov, N., Stoyan, Y., Romanova, T., & Pankratov, A. (2012). Phi-functions for 2D objects formed by line segments and circular arcs. Advances in Operations Research, 26 p. https://doi.org/10.1155/2012/346358
- Bennell, J., Scheithauer, G., Stoyan, Y., Romanova, T., & Pankratov, A. (2015). Optimal clustering of a pair of irregular objects. Journal of Global Optimization, no. 61(3), pp. 497–524. https://doi.org/10.1007/s10898-014-0192-0
- Pankratov, A. V. & Stoyan, Yu. G. (2005). Placement of non-convex polygons with rotations into a non-convex polygon. Proc. Workshop Cutting Stock Problems, Alutus, Miercurea-Ciuc, Romania, pp. 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, no. 106(1), pp. 25–57. https://doi.org/10.1007/s10107-004-0559-y
- Stoyan, Yu., Pankratov, A., & Romanova, T. (2015). Cutting and Packing problems for irregular objects with continuous rotations: mathematical modeling and nonlinear optimization. Journal of Operational Research Society, no. 67(5), pp. 786–800. https://doi.org/10.1057/jors.2015.94
- Kallrath, J. & Rebennack, S. (2013). Cutting Ellipses from Area-Minimizing Rectangles. Journal of Global Optimization, no. 59(2–3), pp. 405–437. https://doi.org/10.1007/s10898-013-0125-3
Received 06 September 2016