SOLUTION OF THE ORTHOGONAL PACKING OF SHEET MATERIALS BY LINEAR CUTTING

Abstract


Article deals with two-dimensional orthogonal cutting-packing optimization which is the most often in practice. 1.5-DBPP (1.5-Dimensional Bin Packing Problem) and 2-DBPP (2-Dimensional Bin Packing Problem) were considered. Difference between these two problems is following. In 1.5-DBPP we are given half-infinite strip of material while in 2-DBPP sheet of material has fixed length. Algorithm-decoder was proposed, this algorithm was called group decoder. To find group of objects which should fill current block proposed algorithm uses linear cutting methods based on dynamic programming. Choose of precisely group but not single object let us more effectively spend space on the sheet and reduce the amount of waste. Computational experiments were held in which proposed algorithm was compared to existing ones; use of simulated annealing methods to find better priority lists was also considered. In these experiments group decoder applied together with simulated annealing showed the best results. Moreover results group decoder without simulated annealing weren't worse than existing algorithms with simulated annealing. Experiments were hold on two data sets. First data set was test consisted of randomly generated rectangles. For second data set tests were generated so as to one be able to place rectangles on a sheet in a way to sheet was used for 100 %. On several tests from second data set proposed algorithm was able to find optimal solution.

About the authors

R. A Faizrakhmanov

Perm National Research Polytechnic University

Email: fayzrakhmanov@gmail.com

R. T Murzakaev

Perm National Research Polytechnic University

Email: rustmur@gmail.com

V. S Shilov

Perm National Research Polytechnic University

Email: vadim.shilov@gmail.com

A. S Mezentsev

Perm National Research Polytechnic University

Email: alexey537@yandex.ru

References

  1. Applying the greedy algorithm for reducing the dimensionality of the dynamic programming method in solving the one-dimensional cutting stock problem [Электронный ресурс] / R.A. Fayzrakhmanov [и др.] // Middle-East Journal of Scientific Research. - 2014. - Vol. 5, № 19. - URL: http://www.idosi.org/mejsr/mejsr19(3)14/14.pdf (дата обращения: 12.03.2014). doi: 10.5829/idosi.mejsr.2014.19.3.13685.
  2. Application of the Group Decoder for Solving the Orthogonal Materials Cutting Problem [Электронный ресурс] / R.A. Fayzrakhmanov [и др.] // World Applied Sciences Journal. - 2013. - Vol. 10, № 28. - URL: http://www.idosi.org/wasj/wasj28(10)13/4.pdf (дата обращения: 12.03.2014). doi: 10.5829/idosi.wasj.2013.28.10.13872.
  3. Мурзакаев Р.Т., Шилов В.С., Буркова А.В. Основные методы решения задачи фигурной нерегулярной укладки плоских деталей [Электронный ресурс] // Инженерный вестник Дона. - 2013 - № 4. - URL: http://www.ivdon.ru/magazine/archive/n4y2013/2043 (дата обращения: 26.05.2014).
  4. Шилов В.С. The usage of group decoder to solve 1.5-dimension bin packing problem // Инновационные процессы в исследовательской и образовательной деятельности: сб. ст. междунар. конф. - Пермь, 2013. - C. 168-171.
  5. Мезенцев А.С., Шилов В.С. Интерпретация данных для алгоритмов решения задач двумерного раскроя-упаковки // Вестник Пермского национального исследовательского политехнического университета. Электротехника, информационные технологии, системы управления. - 2013. - № 8. - C. 137-143.
  6. Hifi M. Cutting circles and placing various-sized into a strip // Computers and Operations Research. - 2004. - № 31. - P. 675-694.
  7. Wascher Gerhard. An improved typology of cutting and packing problems // European Journal of Operational Research. - 2007. - № 183. - Р. 1109-1130.
  8. Мурзакаев Р.Т., Лялин Д.А. Алгоритм уплотнения карты раскроя на основе двумерной гравитационной имитационной модели // Современная наука: актуальные проблемы теории и практики. - 2013. - № 9-10. - С. 34-41.
  9. Мухачева А.С., Ширгазин Р.Р. Задачи упаковки прямоугольников: рандомизированная эвристика на базе двойственной схемы локального поиска оптимума // Информационные технологии. - 2003. - № 5. - C. 18-22.
  10. Люк Ш. Основы метаэвристик [Электронный ресурс]. - 2009. - URL: http://qai.narod.ru/GA/metaheuristics.html (дата обращения: 16.06.2014.
  11. Сиразетдинова Т.Ю. Решение задачи прямоугольного раскроя на базе процедур метода имитации отжига // Приложения методов оптимизации: труды XIV Байкальской междунар. школы-сем. - Иркутск, 2008. - Т. 4. - С. 223.
  12. Ширгазин Р.Р. Эволюционные методы и программное обеспечение для решения задач ортогональной упаковки на базе блочных структур: дис.. канд. техн. наук: 05.13.18. - Уфа, 2006.

Statistics

Views

Abstract - 58

PDF (Russian) - 35

Refbacks

  • There are currently no refbacks.

Copyright (c) 2014 Faizrakhmanov R.A., Murzakaev R.T., Shilov V.S., Mezentsev A.S.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies