РЕШЕНИЕ ЗАДАЧИ ОРТОГОНАЛЬНОЙ УПАКОВКИ ЛИСТОВЫХ МАТЕРИАЛОВ МЕТОДАМИ ЛИНЕЙНОГО РАСКРОЯ
- Авторы: Файзрахманов Р.А1, Мурзакаев Р.Т1, Шилов В.С1, Мезенцев А.С1
- Учреждения:
- Пермский национальный исследовательский политехнический университет
- Выпуск: № 2 (2014)
- Страницы: 29-41
- Раздел: Статьи
- URL: https://ered.pstu.ru/index.php/elinf/article/view/2765
- DOI: https://doi.org/10.15593/вестник%20пермского%20национального%20исследовательского%20политехнического%20университета.%20электротехника,%20информационные%20технологии,%20системы%20управления.v0i2.2765
- Цитировать
Аннотация
Статья посвящена проблеме оптимизации процесса двумерного ортогонального раскроя-упаковки, которая наиболее часто встречаются на практике. Были рассмотрены задачи 1.5-DBPP (1.5-Dimensional Bin Packing Problem) и 2-DBPP (2-Dimensional Bin Packing Problem). Различие данных задач состоит в том, что в первой происходит размещение объектов на полубесконечной полосе материала, в то время как во второй задаче длина листа материала ограничена. Для их решения предложен алгоритм-декодер, названный групповым декодером. Данный алгоритм использует методы линейного раскроя, основанные на динамическом программировании, для поиска группы объектов, которой необходимо заполнить текущий рассматриваемый блок. Выбор именно группы, а не отдельного объекта позволяет более эффективно расходовать пространство на листе и тем самым снижать количество отходов. Были проведены вычислительные эксперименты, в которых предложенный алгоритм сравнивался с уже существующими; также было рассмотрено применение метода имитации отжига для поиска лучших вариантов приоритетных списков. По результатам вычислительных экспериментов групповой декодер, примененный совместно с методом имитации отжига, показал наилучшие результаты, кроме того, групповой декодер без использования метода имитации отжига показал результаты, не уступающие существующим алгоритмам, примененным совместно с методом имитации отжига. Эксперименты проводились на двух наборах данных. Первый набор представлял собой тесты, состоящие из случайно сгенерированных прямоугольников. Для второго набора данных тесты генерировались таким образом, чтобы была возможность разместить имеющиеся прямоугольники на листе таким образом, чтобы материал был использован на 100 %. Предложенный алгоритм на ряде тестов из второй группы данных смог найти оптимальное решение.
Об авторах
Р. А Файзрахманов
Пермский национальный исследовательский политехнический университет
Email: fayzrakhmanov@gmail.com
Р. Т Мурзакаев
Пермский национальный исследовательский политехнический университет
Email: rustmur@gmail.com
В. С Шилов
Пермский национальный исследовательский политехнический университет
Email: vadim.shilov@gmail.com
А. С Мезенцев
Пермский национальный исследовательский политехнический университет
Email: alexey537@yandex.ru
Список литературы
- 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.
- 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.
- Мурзакаев Р.Т., Шилов В.С., Буркова А.В. Основные методы решения задачи фигурной нерегулярной укладки плоских деталей [Электронный ресурс] // Инженерный вестник Дона. - 2013 - № 4. - URL: http://www.ivdon.ru/magazine/archive/n4y2013/2043 (дата обращения: 26.05.2014).
- Шилов В.С. The usage of group decoder to solve 1.5-dimension bin packing problem // Инновационные процессы в исследовательской и образовательной деятельности: сб. ст. междунар. конф. - Пермь, 2013. - C. 168-171.
- Мезенцев А.С., Шилов В.С. Интерпретация данных для алгоритмов решения задач двумерного раскроя-упаковки // Вестник Пермского национального исследовательского политехнического университета. Электротехника, информационные технологии, системы управления. - 2013. - № 8. - C. 137-143.
- Hifi M. Cutting circles and placing various-sized into a strip // Computers and Operations Research. - 2004. - № 31. - P. 675-694.
- Wascher Gerhard. An improved typology of cutting and packing problems // European Journal of Operational Research. - 2007. - № 183. - Р. 1109-1130.
- Мурзакаев Р.Т., Лялин Д.А. Алгоритм уплотнения карты раскроя на основе двумерной гравитационной имитационной модели // Современная наука: актуальные проблемы теории и практики. - 2013. - № 9-10. - С. 34-41.
- Мухачева А.С., Ширгазин Р.Р. Задачи упаковки прямоугольников: рандомизированная эвристика на базе двойственной схемы локального поиска оптимума // Информационные технологии. - 2003. - № 5. - C. 18-22.
- Люк Ш. Основы метаэвристик [Электронный ресурс]. - 2009. - URL: http://qai.narod.ru/GA/metaheuristics.html (дата обращения: 16.06.2014.
- Сиразетдинова Т.Ю. Решение задачи прямоугольного раскроя на базе процедур метода имитации отжига // Приложения методов оптимизации: труды XIV Байкальской междунар. школы-сем. - Иркутск, 2008. - Т. 4. - С. 223.
- Ширгазин Р.Р. Эволюционные методы и программное обеспечение для решения задач ортогональной упаковки на базе блочных структур: дис.. канд. техн. наук: 05.13.18. - Уфа, 2006.
Статистика
Просмотры
Аннотация - 52
PDF (Russian) - 26
Ссылки
- Ссылки не определены.