Мультиметодная технология моделирования ортогональной упаковки и размещения прямоугольно-ориентированных заготовок

• Автор: Валиахметова, Юлия Ильясовна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Уфа
• Количество страниц: 176 с. : ил.

Оглавление

Использованные обозначения

Введение

1. Проблемы раскрояупаковки. Комбинаторные методы решения

1.1. Одномерный раскрой. Двумерная упаковка

1.2. Методы решения задач размещения

1.3. Выводы по главе 1

2. Моделирование схем прямоугольного размещения

2.1 Постановка основных задач размещения прямоугольноориентированных предметов в двумерных контейнерах

2.2 Математические модели конструирования упаковки в полосу и на

2.3. Краткие характеристики основных технологий моделирования

ортогональных размещений
2.4. Способы кодирования упаковок
2.5. Алгоритмыдекодеры
2.6. Эволюционные алгоритмы
2.7. Генетический мультиметодный алгоритм в задачах дискретной
оптимизации
2.8. Выводы по главе 2
3. Мулыпиметодная технология моделирования ортогональной упаковки
3.1. Общая схема мультиметодной технологии для решения задач
дискретной оптимизации
3.2. Модификации алгоритма комбинирования эвристик
3.3. Методы дискриминации и форсирования простых эвристик
декодеров
3.4. Мультиметодные алгоритмы для решения задачи размещения
прямоугольноориентированных предметов
3.5. Использование мультиметодной технологии для решения других
комбинаторных задач
3.6. Выводы по главе 3
4. Численные эксперименты
4.1 Программная реализация алгоритмов
4.2. Определение рационального количества итераций
4.3. Оценка эффективности алгоритмов. Нижние границы
4.4. Подготовка исходной информации
4.5. Исследование эффективности мультиметодного генетического алгоритма вМА и мультиметодного эволюционного алгоритма 11МЕА
4.6. Сравнение результатов работы различных декодеров в составе мультиметодного эволюционного алгоритма
4.7. Выводы по главе 4
5. Исследование эффективности методов дискриминации и форсирования эвристик
5.1. Анализ решения задач упаковки в полубесконечную полосу
5.2. Анализ решения задач упаковки в контейнеры
5.3. Выводы по главе 5
Заключение
Список использованной литературы


Это позволяет использовать разработанные алгоритмы при практических расчетах. По полученным результатам разработанный алгоритм может быть рекомендован к решению задач прямоугольно-ориентированного размещения на листовой и рулонный материал с определенным набором диапазонов значений вероятностных показателей для входящих в состав декодера эвристик. Разработанный комплекс внедрен на ряде предприятий, в том числе на ООО «Европак» и ООО «Матрица-Трейд», а также в учебном процессе, в том числе на факультете информатики и робототехники УГАТУ, и в БГАУ на факультете информационных технологий и факультете механизации сельского хозяйства. Апробация работы. Всероссийская научно-практическая конференция молодых ученых. Научные семинары кафедры Вычислительной Математики и Кибернетики Уфимского Государственного Авиационного Технического Университета. По теме диссертации опубликовано работ, в том числе 1 статья в рецензируемом журнале из списка ВАК. Правовая сторона программного продукта защищена «Свидетельством об официальной регистрации программ для ЭВМ» № и №. Диссертация состоит из введения, пяти глав и заключения. Объем работы составляет 6 страниц машинописного текста, включая рисунков, таблиц, и библиографию, содержащую 0 названий. Содержание диссертации. Во введении к диссертации обоснована актуальность работы; сформулирована цель и задачи исследования; приведены результаты, выносимые на защиту; отмечена их практическая значимость и научная новизна. Приведены сведения об апробации работы и публикациях. В первой главе проведен аналитический обзор моделей и методов решения задач прямоугольно-ориентированного размещения и выделен класс задач, решаемых в рамках диссертационной работы. Приводятся математические постановки задач прямоугольно-ориентированного размещения в полубесконечную полосу и на листах. Вторая глава посвящена рассмотрению способов кодирования и декодирования упаковок. Рассматриваются различные способы кодирования схем размещения, указываются недостатки и достоинства каждого из приведенных способов. Предложен новый способ кодирования размещения — последовательностью эвристик. Кроме этого приведены краткие характеристики основных технологий - блочной, уровневой и безуровневой. Также приведены новые детерминированные алгоритмы-декодеры, МЫ) и РВЭ, предназначенные для проектирования допустимых схем размещения прямоугольников. Разработаны эффективные декодеры для решения задач прямоугольноориентированного размещения, являющиеся модификациями оригинального декодера комбинирования эвристик, предложенного И. П.Норенковым. Приводятся описания различных декодеров как простых эвристик, а также эволюционных генетических алгоритмов, таких как (1+1)-МЕА, алгоритма имитации отжига, классического генетического алгоритма и генетического блочного алгоритма, а также генетического алгоритма комбинирования эвристик. Третья глава посвящена разработке мультиметодной технологии для решения задачи прямоугольно-ориентированного размещения в иолубесконечную полосу и на листы. Рассматриваются классические генетические алгоритмы, генетический блочный алгоритм, а также модификации генетического алгоритма, в которых задействованы новые декодеры ММО и ММО(1ЛЬ). Описаны методы дискриминации и форсирования эвристик. Рассмотрены основные особенности задач, к решению которых могут быть применены генетические алгоритмы. Четвертая глава посвящена исследованию эффективности мультиметодной технологии на задачах рулонного и листового размещения. Приводятся результаты проведенных численных экспериментов. Описан разработанный программный продукт согласно принципам объектно-ориентированного программирования. Показана эффективность разработанных декодеров. Проведено сравнение результатов работы разработанных декодеров с другими известными алгоритмами, а также между собой. Подтверждена плодотворность включения в состав декодеров «либеральных» эвристик. В пятой главе описаны методика проведения и результаты численных экспериментов, направленных на выявление целесообразности использования методов дискриминации и форсирования эвристик.