«Программный модуль для предоптимизационного анализа информации в задаче двумерного размещения»

Актуальность работы

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

Тема выпускной квалификационной работы: программный модуль для предоптимизационного анализа информации в задаче двумерного размещения

Цель выпускной квалификационной работы

Целью выпускной квалификационной работы является: Разработка предоптимизационного модуля для повышения эффективности поиска решений в задаче геометрического размещения

Задачи выпускной квалификационной работы

Для достижения цели были поставлены следующие задачи:

1. Провести анализ моделей и методов решения задачи двумерного размещения объектов, различных геометрических форм;

2. Провести вычислительный эксперимент для анализа эффективности известных алгоритмов решения задачи двумерного размещения;

3. Разработать программный модуль для предоптимизационного анализа информации и выбора эффективного алгоритма решения;

4. Протестировать и произвести отладку программного модуля.

многопроцессорных систем. При этом любая из задач может быть конкретизирована по-своему. Например, если рассматривать только задачи раскроя запаса можно встретить несколько постановок. Они могут различаться по различным признакам: размеры и ассортимент материала и заготовок, геометрией материала и полученных из них заготовок, условиями реализации раскроя и другими дополнительными признаками [1].

В задачах двумерного раскроя по своей сложности лидирующими по отношению к другим задачам раскроя находятся задачи нерегулярного размещения геометрических объектов сложных форм. Это связано с тем, что достаточно сложно учитывать все условия взаимного не пересечения объектов и условий их размещения в заданных областях раскрой упаковки.

Впервые данные задачи раскроя геометрических объектов были рассмотрены великим русским математиком П.Л.Чебышевым в докладе «О кройке одежды» 1878 года [2]. В нем были рассмотрены вопросы о лучшем покрытии кривых поверхностей плоскими выкройками из ткани. В дальнейшем развитие интереса к данной задаче все больше развивалось, так 80-х годы для решения проблемы раскроя-упаковки была использована 6

теория искусственного интеллекта. В эти же годы было признано, что применение различных эвристик, возможно, лучший способ для нахождения хороших решений за приемлемое время [5].

1.2 Содержательная постановка задачи двумерного размещения

В рамках данной выпускной квалификационной работы рассмотрим задачу размещения двумерной прямоугольной упаковки.

Рассматривается задача двумерной прямоугольной упаковки (1,5 Dimensional Bin Packing Problem, 1,5DBPP) об упаковке прямоугольников в полубесконечную по длине полосу. Она состоит в следующем [4].

Рассмотрим пример, при котором в грузовиках контейнеры, возможно, размещать, не ставя друг на друга и не превышая допустимых параметров.

Данная задача имеет следующий вид. Имеется прямоугольная полоса заданной ширины W, а также набор прямоугольных предметов T заданных размеров wi; li, i = 1, m . Найти упаковку предметов в полосу при следующих условиях:

1) ребра упакованных предметов параллельны ребрам полосы;

2) упакованные предметы не пересекаются друг с другом;

3) упакованные предметы не пересекаются со сторонами полосы.

Прямоугольная упаковка (Rectangular Packing, RP), удовлетворяющая условиям 1 - 3, называется допустимой.

Если длина L(RP) занятой части полосы достигает минимума, то RP называется оптимальной упаковкой и является решением задачи 2DBPP.

• Разработан программный модуль для предоптимизационного анализа информации, который позволяет подбирать эффективные алгоритмы и настройки;

• Протестирована и произведена отладка программного модуля.

Поставленная цель достигнута. Задачи решены в полном объеме.

4. Гаврилова Т.С., Галина Р.Р., Михайлова А.Н. Эволюционный алгоритм для маршрутизации транспорта с учетом грузоподъемности [Текст]/ Динамика сложных сетей и их применение в интеллектуальной робототехнике. Сборник материалов Международной школы-конференции молодых ученых - Саратов: ООО «Издательство «Научная книга»», -2017, с. 31-32.

5. Филиппова А.С., Михайлова А.Н., Гаврилова Т.С., Галина Р.Р. Использование эволюционного алгоритма для изучения студентами дисциплины «Прикладные методы оптимизации» [Текст]/ Гуманистическое наследие просветителей в культуре и образовании: материалы XII Международной научно-практической конференции 14 декабря 2017 г. - Уфа: Издательство БГПУ, 2018. С. 108 -109.

6. Лаптенок Е.Д., Гаврилова Т.С., Галина Р.Р., Михайлова А.Н. Разработка эволюционного алгоритма для транспортно-логистических информационных систем [Текст]/ Актуальные проблемы науки и техники. Информационные и инфокоммуникационные технологии. УГАТУ. с. 43- 45 7. Филиппова А.С., Михайлова А.Н., Галина Р.Р., Гаврилова Т.С.

Алгоритмическое обеспечение транспортно-логистических

информационных систем [Текст]/ Материалы Всероссийской (с международным участием) студенческая научно-практической

конференции «Наука 2020» (20 апреля 2018 г.) / сост. Л.Р. Саитова, Р.Н. Измайлов. - Уфа: Изд-во БГПУ, 2018. С. 215-220.

8. Филиппова А.С., Андреева Е.В., Дяминова Э.И., Лаптенок Е.Д. Матричный алгоритм роя частиц для поддержки принятия решений при составлении расписания обслуживающих бригад // Материалы VI Всероссийской конференции «Информационные технологии

интеллектуальной поддержки принятия решений» (ITIDS’2018). - Уфа, УГАТУ, 2018. Т. 2. С. 125-128.

9. Смагин М.А., Хасанова Э.И., Басимов Э.Р. Проектирование сквозного размещения прямоугольных предметов в многосвязный ортогональный полигон. Программа для ЭВМ Смагина М.А. Уфа 2005 год

Диссертация Смагин М.А. Автоматизация проектирования рационального размещения прямоугольных деталей с использованием генетического метода на множестве эвристик автореф. на соискание степени кандидата технических наук Уфа-2005.