БИОИНСПИРИРОВАННЫЙ АЛГОРИТМ ПЛОТНОЙ УПАКОВКИ ДЛЯ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ РАСКРОЯ ПОЛУОГРАНИЧЕННОЙ ПОЛОСЫ
Ключевые слова:
Раскрой-упаковка, полуограниченная полоса, декомпозиция, методология, задача об упаковке в контейнеры, компакция, поисковая оптимизация, роевой интеллект, муравьиная колония, адаптивное поведениеАннотация
Предлагается архитектура и методология раскроя-упаковки полуограниченной полосы на
основе методов биоинспирированного поиска. В основе подхода к декомпозиции обшей задачи упа-
ковки и методологии формированию карт раскроя лежат эвристики уровневого подхода к упаков-
ке полосы. Архитектура сформирована на основе декомпозиции общей задачи и включает 5 основ-
ных секций: управление процессом поиска; формирования блоков; формирование контейнеров;
компакция контейнеров; заполнения полосы контейнерами. Упаковка ориентирована на двухуров-
невый раскрой полосы. На первом уровне путем гильотинного разреза выполняется раскрой на
контейнеры. На втором уровне два варианта раскроя: путем гильотинного или путем не гильо-
тинного разреза выполняется раскрой контейнеров на детали (элементы прямоугольной формы).
Упаковка выполняется путем последовательного заполнения уровней полосы контейнерами.
В основу методологии раскроя-упаковки полуограниченной полосы положен иерархический подход
снизу вверх. Задача, решаемая на первом уровне иерархии, заключается в формировании множе-
ства блоков B одинаковой ширины на базе исходного набора A прямоугольников, включаемых в
блоки. Для решения поставленной задачи авторами разработан биоинспирированный алгоритм
одномерной упаковки элементов в одинаковые блоки. На втором уровне иерархии решается задача
распределения блоков по контейнерам. Все контейнеры и блоки имеют одинаковую ширину D,
равную ширине полосы. В каждом контейнере помещаются два блока. Задача распределения бло-
ков по контейнерам сведена к задаче нахождения максимального паросочетания минимальной
стоимости. В отличие от канонической метаэвристики муравьиного алгоритма в работе аген-
том на графе поиска решений строится максимальная клика, которая является интерпретацией
решения. На третьем уровне иерархии решается задача компакции контейнеров. Процесс распре-
деления блоков по контейнерам сопровождается процедурой сжатия каждой пары блоков, назна-
чаемых в один контейнер. Целью компакции является минимизация общей площади контейнера
путем плотного размещении блоков. Компакцию последовательно проводят во всех контейнерах.
На четвертом уровне иерархии решается задача заполнения полосы контейнерами. В качестве
модели для представления решения на графе поиска решений служит клика. Разработана база
данных коллективной эволюционной памяти. Разработана методика формирования феромоновых
точек и структур данных коллективной эволюционной памяти. Для проведения объективных экс-
периментов были использованы известные тестовые задачи, представленные в литературе и
сети Интернет. По сравнению с существующими алгоритмами достигнуто улучшение результа-
тов на 3-5%. Временная сложность алгоритма, полученная экспериментальным путем, практи-
чески совпадает с теоретическими исследованиями и для рассмотренных тестовых задач со-
ставляет (ВСА ≈ О(n2)).
