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

Аннотация

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