Разработка метода эффективного решения задач плоского раскроя с использованием генетических алгоритмов

• Автор: Подлазова, Анастасия Викторовна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Москва
• Количество страниц: 98 с. : ил.

Содержание
Введение

Глава 1. Проблемы раскроя и упаковки

Определение и дуальность понятий раскроя и упаковки.

Классификация задач раскроя.

Регулярная и нерегулярная упаковка.

Упаковка полосы и прямоугольника.

Практические аспекты.

ЫРполнота проблем раскроя и упаковки

Алгоритмы и их сложность.

полнота задачи.

Глава 2. Генетические алгоритмы.
Эволюционные вычисления
Эволюционные алгоритмы.
Формализация генетического алгоритма.
Оценка эффективности генетического алгоритма.
Основная теорема о генетических алгоритмах.
Применение генетических алгоритмов.
Комбинирование методов.
Вопросы разработки и использования.
Достоинства и недостатки.
Глава 3. Решение задачи раскроя полубесконечной полосы
Задача прямоугольного раскроя
Содержательная постановка задачи.
Математическая постановка задачи.
Методы решения задачи прямоугольного раскроя
Блок структуры упаковок
Блочный декодер
Задача круглого раскроя
Содержательная постановка задачи.
Математическая постановка задачи.
Методы решения задачи круглого раскроя.
Структура края круглой упаковки
Краевой декодер
Другие задачи плоского раскроя.
Практическая задача раскроя листов.
Задача нерегулярного раскроя.
Перспективы развития метода
Выводы.
Глава 4. Вычислительный эксперимент.
Программное обеспечение
Общая характеристика результатов.
Прямоугольный раскрой
Круглый раскрой
Показатели качества раскроя
Прямоугольный раскрой
Круглый раскрой
Оценка сложности алгоритма.
Показатель качества генетического алгоритма
Другие оценки
Выводы.
Глава 5. Область применения метода
Технологии раскроя материалов
Лазерная промышленность в России.
Устройство лазерных установок
Примеры программного обеспечения.
Выводы.
Заключение.
Список использованных источников


При раскрое дорогостоящих материалов, материалов, имеющих особенные физические свойства, целесообразность сведения потерь к минимуму также имеет очевидное экономическое обоснование. Необходимость разработки рациональных методов раскроя обоснована еще в -х годах XX века. В СССР первые разработки принадлежат академику Л. В. Канторовичу. На сегодняшний день существует множество алгоритмов, созданных для решения подобных задач. В то же время практически нет универсальных разработок, которые позволили бы решать различные (в рамках некоторого класса) задачи раскроя на основе одного и того же метода. Последние несколько лет ряд металлургических и машиностроительных предприятий впервые приобрели или заменяют морально и физически устаревшую технику, осуществляющую лазерный раскрой листового металла (в том числе, Западно-сибирский металлургический комбинат (г. Новокузнецк), Курганский автобусный завод, «Химконцентрат» (г. Новосибирск), «ЭлСиб» (г. Новосибирск), Тверской вагоностроительный завод) и другие. Установки для лазерной резки на некоторых предприятиях имеются уже десятилетие, но только в настоящее время руководство получает возможность модернизировать процесс производства. Лазерный раскрой имеет ряд безусловных достоинств: высокая точность резки и как следствие легкость сборки конструкций из вырезанных деталей; возможность существенно уменьшить потери металла за счет маневренности режущего устройства и программного управления; высокое качество среза края заготовки и как следствие экономия средств на последующую обработку; автоматизированность процесса, быстрое осуществление раскроя. Область применения технологии лазерной резки очень широка, с ее помощью раскраивают и детали для железнодорожных вагонов, и комплектующие для бытовой техники, и различные декоративные элементы. Для подобного современного оборудования целесообразна разработка эффективного метода раскроя плоского материала на наборы деталей различных размеров, решающего задачу для различной геометрической формы деталей. Целью работы является создание метола, позволяющего решать различные задачи плоского раскроя. Стохастическая оптимизация, имитационное моделирование, векторная алгебра и геометрия, численные методы. В настоящее время при решении оптимизационных задач все чаще используются методы, основанные на эволюционном подходе. Генетические алгоритмы целесообразно использовать как метод решения задач раскроя и упаковки, которые, являясь ИР-полными, не имеют эффективных точных методов решения. Генетический алгоритм, как правило, находит решение за полиномиальное время (т. Это свойство имеет особенное значение при решении задач раскроя большого количества деталей. Кроме того, за счет уменьшения времени, затраченного на составление плана раскроя, можно более эффективно эксплуатировать дорогостоящее оборудование. ЫР-полной задачи имеет полиномиальную сложность. Для решения задачи круглого раскроя полосы разработан специальный краевой декодер, основная идея которого носит общий характер и применима для упаковки предметов других несложных геометрических форм; для задачи прямоугольного раскроя полосы реализован блочный декодер; для задачи прямоугольного раскроя набора листов модифицирован блочный декодер и алгоритм раскроя полосы. Московского государственного института стали и сплавов. ЫР-полной задачи имеет полиномиальную сложность. Научные положения, выводы и практические рекомендации корректно обоснованы и подтверждены математически путем анализа результатов экспериментальных исследований разработанного метода. На основе сформулированного метода разработано математическое и программное обеспечение, реализующее эффективный алгоритм решения задач оптимизации плоского раскроя различных прямоугольных, либо различных круглых деталей. Данное программное обеспечение можно использовать; для решения практических промышленных задач (например, в НИЛ ГТПДиУ МГИСиС); как обучающее и демонстрационное средство для проведения практических занятий и лабораторных работ (например, на кафедре обработки металлов давлением МГИСиС); как базовый проект для разработки нового программного обеспечения для решения других задач плоского раскроя.