АЛГОРИТМ МИНИМИЗАЦИИ СТУПЕНЧАТОСТИ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ОРТОГОНАЛЬНОГО ФИГУРНОГО РАСКРОЯ

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

Аннотация


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

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


раскрой;многосвязный ортогональный полигон;ступенчатость;эвристика;алгоритм;decomposition;multicoherent orthogonal ground;gradation;heuristics;algorithm;

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

PDF

Литература


Павлова Е.В., Исламгулова Г.Ф. Применение статистических методов для имитации моделирования сложных систем технологического оборудования // Перспективы науки. 2016. № 5 (80). С. 5-8

Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя упаковки геометрических объектов. Уфа: УГАТУ, 1998. 216 с

Валиахметова Ю.И., Филиппова А.С. Теория оптимального использования ресурсов Л.В. Канторовича в задачах раскроя-упаковки: обзор и история развития методов решения // Вестник УГАТУ. 2014. Т. 18. № 1 (62). С. 186-197

Исламгулова Г.Ф. Инфографика в курсе аналитической геометрии // Перспективы науки. 2016. № 11 (86). С. 63-67

Rechenberg I. Evolutions Strategic: Optimerung Technischer Systeme nach Prinzipen der Biologischen Evolution. Stuttgart: Formann - Holzboog Verlag, 1973. Рp. 44-92

Loris Faina. An Application of Simulated Annealing to the Cutting Stock Problem // European Journal of Operational Research. 1999. Vol. 114. Рp. 532-556

Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by Simulated Annealing // Science. 1983. Vol. 220. Р. 671-680

Кочетов Ю.А., Усманова А. Вероятностный поиск с запретами для задачи упаковки в контейнеры // Методы оптимизации и их приложения: 12-я Байкальская международная конференция. Иркутск, 2001. С. 22-27

Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения: сб. лекций молодежн. и научн. школ по дискр. мат-ке и ее прилож. М., 2000. С. 87-117

Борисовский П.А., Еремеев А.В. О сравнении некоторых эволюционных алгоритмов // Автоматика и телемеханика. 2004. № 3. С. 3-9

Валиахметова Ю.И. Мультиметодная технология моделирования ортогональной упаковки. LAP LAM-BERT Academic Publishing, Saarbrucken, Germany, 2011. 176 с. ISBN: 978-3-8465-1420-7

Мухачева Э.А., Валиахметова Ю.И., Хасанова Э.И., Телицкий С.В. Проектирование размещения ортогональных объектов на полигонах с препятствиями // Новые технологии. Информационные технологии. 2010. № 10. С. 16-22

Филиппова А.С., Дяминова Э.И., Валиахметова Ю.И. Метод ограниченной декомпозиции для решения комплексной задачи геометрического покрытия и раскроя // Новые технологии. Информационные технологии. 2016. Т. 22. № 3. С. 179-187

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




DOI: http://dx.doi.org/10.17122/ngdelo-2018-3-120-127

Ссылки

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


(c) 2018 Т. И. Григорчук, Ю. И. Валиахметова

Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.

УФА, УГНТУ, 2017