УПАКОВКА В ПОЛУБЕСКОНЕЧНУЮ ПОЛОСУ НА ОСНОВЕ ДЕКОМПОЗИЦИИ И ГИБРИДИЗАЦИИ БИОИСПИРИРОВАННЫХ МЕТОДОВ

Аннотация

Объектом исследования является задача прямоугольной упаковки в полубесконечную
полосу. Задан набор прямоугольников. Дан один большой объект (называемый полосой), чья
ширина D задана, а HP высота – искомое значение переменной. Цель состоит в том, что-
бы минимизировать высоту HP полосы, содержащей прямоугольники, помещенные в поло-
су без их взаимного перекрытия. Для решения задачи упаковки предложен новый гибридный
подход на основе декомпозиции общей задачи упаковки и гибридизации биоиспирированных
методов, а также новый гибридный подход к декомпозиции общей задачи упаковки. Разра-
ботаны новые архитектура и методы решения задачи упаковки, построенные на основе
декомпозиции и гибридизации разработанных авторами роевых методов, использующие
различные стратегии поиска, функционирующие параллельно-последовательно и реали-
зующие более широкий обзор пространства решений, что позволяет обеспечить более
высокую вероятность локализации глобального экстремума за приемлемое время. Разра-
ботана методология нового направления поиска решений задач ортогональной упаковки на
основе моделей адаптивного поведения биологических систем. Разработан высокоэффек-
тивный гибридный биоинспирированный метод решения задач одномерной и прямоугольной
упаковки, основанный на декомпозиции задачи на множество подзадач и интеграции ме-
тодов поисковой оптимизации. Предложены новые механизмы решения задачи упаковки,
использующие математические методы, в которых заложены принципы природных меха-
низмов принятия решений. В отличие от канонической парадигмы муравьиного алгоритма
агентом на графе поиска решений в качестве решения формируется разбиение множества
прямоугольных элементов A на подмножества Ak
i, где Ak
j ‒ подмножество элементов, на-
значенных агентом в блок. Разработаны поисковые методы для решения задач гильотин-
ного и не гильотинного прямоугольного раскроя. Для проведения объективных эксперимен-
тов были использованы известные тестовые задачи, представленные в литературе и Ин-
тернет. Получены лучшие результаты по сравнению с тестируемыми методами. Пред-
ложенные в работе теоретические положения для решения задач упаковки и раскроя про-
мышленных объектов в условиях единичного производства реализованы в виде методик,
алгоритмов и прикладного программного обеспечения. По сравнению с существующими
алгоритмами достигнуто улучшение результатов на 3–5%. Временная сложность алго-
ритма, полученная экспериментальным путем, практически совпадает с теоретическими
исследованиями и для рассмотренных тестовых задач составляет О(n2).