БИОИНСПИРИРОВАННЫЙ АЛГОРИТМ ПЛОТНОЙ УПАКОВКИ ДЛЯ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ РАСКРОЯ ПОЛУОГРАНИЧЕННОЙ ПОЛОСЫ

Аннотация

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