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

• Автор: Смагин, Михаил Анатольевич
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Уфа
• Количество страниц: 115 с. : ил.

Оглавление
Оглавление
Введение

1. Анализ современных моделей и методов проектирования двумерного размещения.

1.1. Автоматизация проектирования и технологической подготовки заготовительного производства.

1.2. Классификация задач размещения и место исследуемых задач в ней

1.3. Общая постановка задач двумерного размещения.

1.4. Математические модели двумерного размещения

1.5. Обзор методов решения задачи двумерного размещения.

1.5.1. Точные методы, их достоинства и недостатки.

1.5.2. Простые эвристики

1.5.3. Методы локального поиска оптимума. Общая схема и метаэвристики.
1.6. Автоматизированные системы проектирования размещения деталей
1.7. Выводы.
2. Эвристические методы размещения деталей на заданных объектах
2.1. Схемы кодирования
2.1.1. Прямая схема кодирования.
2.1.2. Кодирование приоритетным списком, перестановкой
2.1.3. Кодирование парой последовательностей
2.1.4. Кодирование блокструктурой
2.2. Однопроходные эвристики проектирования размещения
2.2.1. Декодер нижний левый.
2.2.2. Декодер усовершенствованный нижний левый.
2.2.3. Блочный декодер
2.2.4. Двойственный декодер.
2.2.5. Метод размещения деталей в открытую область на базе двойственного алгоритма
2.2.6. Декодер замещения.
2.2.7. Метод локальной перестройки.
2.2.8. Схема применения алгоритма замещения для размещения деталей на листы.
2.3. Выводы.
3. Генетический алгоритм решения задач прямоугольной упаковки
3.1. Генетический алгоритм с позиций локального поиска экстремума.
3.2. Процедуры скрещивания и мутации
3.3. Модификации генетического алгоритма
3.4. Схема ограничения поиска решений в генетическом алгоритме
3.5. Выводы.
4. Автоматизированный комплекс построения рационального размещения. Численные эксперименты
4.1. Организация раскройнозаготовительного производства
4.2. Структура САПР рационального размещения
4.3. Описание автоматизированного комплекса построения рационального размещения
4.3.1. Схема нахождения рационального размещения.
4.3.2. Выполнение задачи размещения автоматизированным комплексом.
4.3.3. Функциональные возможности автоматизированного комплекса
4.4. Постановка численных экспериментов и анализ их результатов.
4.4.1. Исследование работы генетического алгоритма с различными декодерами.
4.4.2. Решение задач размещения на полосу на примерах .
4.4.3. Решение задач размещения на листы на примерах . и . .
4.4.4. Решение задач размещения прямоугольных объектов в свободной
области
4.5. Выводы.
Заключение.
Список литературы


Это означает, что не известно алгоритма полиномиальной сложности для поиска оптимального решения, и точный результат в общем случае может быть получен только за экспоненциальное время. Поскольку при производстве, как правило, задачи размещения имеют большую размерность, а решение должно быть получено в ограниченное время, актуальной становится проблема разработки и использования эвристических методов поиска и построения решения с организацией эффективных способов перебора. При этом существенную роль выполняют различные алгоритмы конструирования упаковок - декодеры. В настоящее время используются системы автоматизированного проектирования размещения деталей (как отечественных, так и зарубежных разработок), отличающиеся структурой и объемом выполняемых работ, качеством конструирования решения и технологической подготовки производства. В первую очередь были разработаны автоматизированные системы «Нсстинга» (размещение деталей сложных форм), особого внимания заслуживают разработки В. Д. Фроловского и A. A. Петунина. Система «Техтран-Раскрой» компании «НИП-Информатика», разработанная под руководством Фроловского В. Д., объединяет возможности CAM-системы с функциями организации производственного процесса []. Система «Сириус» (A. A. Петунии) предназначена для проектирования рационального раскроя, а также для подготовки управляющих программ резки []. Однако в различных системах проектирования долгое время вопросы экономии материальных ресурсов уходили на второй план. Внимание уделялось главным образом логическим, а не расчетным операциям. Расчеты и проектирование выполнялись быстро за счет использования простых однопроходных эвристик. Попытка объединить два критерия, затраты времени и экономия материала, была осуществлена в докторской диссертации ЭА. Мухачевой[]. Она использовала в системах автоматизации линейное программирование. Это оказалось возможным в условиях массового производства. В современную эпоху, когда появилось много средних и малых предприятий, непрерывная релаксация в линейном программировании оказывается мало приемлемой. Сиразетдинов Т. П. развил эффективные подходы для расчета гильотинного раскроя, которые базируются на локальном поиске оптимума, и они дали прекрасные результаты. Предлагаемый комплекс посвящен не гильотинному размещению деталей на материале различного вида: рулонах, листах, открытых областях (производство плат). Для внедрения оптимизационных систем расчета упаковки в АСТПП требуются существенные временные и материальные затраты, что непозволительно для мелких и средних предприятий. Поэтому и разрабатываются быстрые алгоритмы, значительно превосходящие по эффективности использования материала простые эвристики. Все вышесказанное определяет актуальность решаемой в данной работе задачи расчета рационального размещения деталей в системах автоматизированного проектирования. Создание автоматизированного комплекса проектирования размещения прямоугольных деталей на рулонах, листах и в открытых областях на базе математического моделирования и численных методов решения задач рационального размещения. Провести анализ существующих систем автоматизации проектирования размещения прямоугольных деталей, а также методов и алгоритмов решения данной задачи. Исследовать эффективность предложенных алгоритмов с помощью численного эксперимента и выработать рекомендации по их использованию. Результаты исследований, выполненных в работе, базируются на теории и практике автоматизации проектирования, методах исследования операций, принципах модульного и структурного программирования. Для анализа эффективности методов применялись численные эксперименты и методы их обработки. Результаты численных экспериментов и рекомендации по использованию предлагаемых алгоритмов. Разработана схема ограничения области поиска решений генетическим алгоритмом. Основан на ограничении одной из направляющих открытой области. Разработан автоматизированный комплекс размещения деталей на полосу, листы, открытую область в составе автоматизированного рабочего места технолога раскройно-заготовительного производства. Разработаны методики применения комплекса в составе АСТПП.