ТЕХНОЛОГИИ МОДЕЛИРОВАНИЯ АЛГОРИТМОВ ОРТОГОНАЛЬНОГО РАСКРОЯ-УПАКОВКИ И ГЕОМЕТРИЧЕСКОГО ПОКРЫТИЯ: СРАВНЕНИЕ ЭФФЕКТИВНОСТИ

Ю. И. Валиахметова, Т. И. Григорчук, Л. И. Васильева, Л. М. Карамова

Аннотация


: В статье рассматривается актуальная на сегодняшний день проблема ортогонального раскроя и геометрического покрытия. Математические модели этих двух задач имеют сходства между собой и могут применяться при решении различных актуальных оптимизационных задач. Рассматриваются различные технологии моделирования алгоритмов решения задачи ортогональной упаковки в полосу и в листы (контейнеры) и задачи геометрического покрытия. Приведено описание основных технологий, также рассмотрены некоторые алгоритмы, являющиеся представителями различных технологий моделирования. Технологии моделирования алгоритмов в последнее десятилетие получили значительное развитие, что обусловило появление новых методов и алгоритмов, а также позволило расширить круг задач, решаемых при помощи генерируемых метаэвристик.

В то же время на практике все чаще возникают потребности в решении специфических задач, сводящихся к задачам ортогонального раскроя или геометрического покрытия, для решения которых требуются новые модификации известных эффективных метаэвристических алгоритмов, однако, плохо подходящих для решения возникших задач. В первую очередь это связано с той особенностью метаэвристик, что разрабатываются они, как правило, для решения конкретно взятой задачи, и обладают невысокой эффективностью при использовании их для решения более широкого круга задач. Подходы к конструированию решений, используемые в различных технологиях моделирования алгоритмов, основаны на простых эвристических идеях, что позволяет адаптировать алгоритмы к решению новых задач с помощью несложных модифицирующих процедур.

Статья посвящена исследованию и сравнению эффективности различных подходов к решению поставленных задач. Проведены численные эксперименты, результаты которых позволяют вынести рекомендации относительно области применения алгоритмов, являющихся представителями различных технологий моделирования.


Ключевые слова


cutting;genetic;geometrical covering;heuristics;multimethod;packing;генетический;геометрическое покрытие;мультиметодный;раскрой;упаковка;эвристика

Полный текст:

PDF

Литература


Канторович Л.В. Математические методы организации и планирования производства. Л.: Изд-во ЛГУ. 1939. 68 с.

Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование. Новосибирск: Наука СО. 1987. 272 с.

Канторович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов. Новосибирск: Наука СО. 1971. 299 с.

Valiakhmetova Yu. I., Filippova A.S., Karamova L.M. Ufa scientific group by E. A. Mukhacheva: applied operational research problems // Вестник УГАТУ. Уфа: УГАТУ, 2013. Т. 17. №. 6 (59). С. 83-87.

Романовский И.В. Алгоритмы решения экстремальных задач. М.: Наука, 1977. 352 с.

Мухачева Э.А. Рациональный раскрой промышленных материалов в АСУ. М.: Машиностроение, 1984. 176 с.

Gilmory P., Gomory R.E. Alinear Programming approach to the Cutting-Stock Problem // Operation Research. 1961. Vol. 9. pp. 849-859.

Terno J., Linderman R., Scheithauer G. Zuschnitprobleme und ihre praktische losung. Leipzig. 1987. pp. 207 – 217.

Гэри М., Джонсон Д. Вычислительные машины и трудноразрешимые задачи. М.: Мир, 1979. 416 с.

Мухачева А.С., Валеева А.Ф., Картак В.М. Задачи двумерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума. М.: изд-во МАИ, 2004. 192 с.

Филиппова А.С. Моделирование эволюционных алгоритмов решения задач прямоугольной упаковки на базе технологии блочных структур // Новые технологии. Информационные технологии. 2006. № 6. Приложение. 31 с.

Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации // Информационные технологии. 1999. №1. С. 2-7.

Мультиметодная технология ортогональной упаковки и ее применение в задачах транспортной логистики/ Валиахметова Ю. И. [и др.] // Информационные технологии: прилож. журналу. 2009. № 12. 31 с.

Телицкий С.В., Валиахметова Ю.И. Применение систем автоматизированного проектирования карт раскроя в судостроении // Вестник Воронежского гос. техн. ун-та. 2012. Т. 8. № 6. С. 38-43.

Телицкий С.В., Валиахметова Ю.И., Хасанова Э.И. Гибридный алгоритм на основе последовательного уточнения оценок для задач максимального ортогонального покрытия // Вестник Башкирского университета. 2012. Т.17, №1(I). С. 421-425.

Валиахметова Ю.И., Дяминова Э.И., Филиппова А.С. О многокритериальной задаче геометрического покрытия полигона ортогональным ресурсом// Инф. Бюл. Ассоциации мат. програм. Научное издание. Екатеринбург: ИММ УрО РАН. 2015. № 13. С. 117-118.

Валиахметова Ю.И., Дяминова Э.И. Методика исследования эффективности алгоритмов решения многокритериальной задачи геометрического покрытия и раскроя // Информационные технологии поддержки интеллектуального принятия решений: материалы /2-ой Междунар. конф. Уфа. Т. 3. 2014. С. 112-116.

Lodi A., Martello S., Vigo D. Heuristic algorithms for three-dimensional bin packing problem // European Journal of Operational Research. 2002. 141. pp. 410-420.

Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения/ Мухачева Э.А. [и др.] // Информационные технологии. 2001. №9. (Прилож.) С. 24

Библиотека OR-library наборов тестовых задач исследования операций. [Электронный ресурс]. URL: http://people.brunel.ac.uk/~mastjjb/jeb/info.html (дата обращения 26.09.2015).

Валеева А.Ф. Применение метаэвристики муравьиной колонии к задачам двумерной упаковки // Информационные технологии. 2005. № 10. С. 36-43.

Fekete S.P., Schepers J. New class of lower bounds for bin packing problems // Integer Programming and Combinatorial Optimization (IPCO 98), Lecture Notes in Computer Science, eds. R.E. Bixby, E.A. Boyd and R.Z. Ríos-Mercado, Vol. 1412, Springer, Berlin, 1998, pp. 257-270.

O.Berkey and P.Y.Wang. Two-Dimensional finite bin-packing algorithms // J. Oper. Res. Soc., 38 (5): 1987, pp. 423-429.

Martello S., Vigo D. Exact solution of two-dimensional finite bin packing problem // Management Science. 44. 1998. pp. 388-399.

Bortfeldt, A., 2006. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces. European Journal of Operational Research 172, С. 814–837.

Валиахметова Ю.И., Васильева Л.И., Карамова Л.М. Мультиметодные алгоритмы в задачах ортогональной упаковки // Фундаментальная математика и ее приложения в естествознании. Математика: сб. тр. /Всерос. шк.-конф. для студ., асп. и мол. ученых. Уфа: РИЦ БашГУ, 2008. Т.2. С.49-58.

Метод поиска минимума с запретами в задачах двумерного гильотинного раскроя/ Мухачева Э.А. [и др.]. //Новые технологии. Информационные технологии. 2001. № 6. С. 25-31.




DOI: http://dx.doi.org/10.17122/ogbus-2015-5-424-445

Ссылки

  • На текущий момент ссылки отсутствуют.