Содержание к диссертации
Введение 4
Глава 1. Проблемы раскроя и упаковки 10
Определение и дуальность понятий раскроя и упаковки 10
Классификация задач раскроя 10
Регулярная и нерегулярная упаковка 11
Упаковка полосы и прямоугольника 12
Практические аспекты 13
NP-полнота проблем раскроя и упаковки 14
Алгоритмы и их сложность 14
NP-полнота задачи 17
Выводы 18
Глава 2. Генетические алгоритмы 19
Эволюционные вычисления 19
Эволюционные алгоритмы 20
Формализация генетического алгоритма 22
Оценка эффективности генетического алгоритма 24
Основная теорема о генетических алгоритмах 25
Применение генетических алгоритмов 26
Комбинирование методов 28
Вопросы разработки и использования 30
Достоинства и недостатки 32
Выводы 33
Глава 3. Решение задачи раскроя полубесконечной полосы 34
Задача прямоугольного раскроя 37
Содержательная постановка задачи 38
Математическая постановка задачи 38
Методы решения задачи прямоугольного раскроя 40
Блок - структуры упаковок 41
Блочный декодер 43
Задача круглого раскроя 44
Содержательная постановка задачи 44
Математическая постановка задачи 45
Методы решения задачи круглого раскроя 46
Структура края круглой упаковки 48
Краевой декодер 50
Другие задачи плоского раскроя 53
Практическая задача раскроя листов 55
Задача нерегулярного раскроя 58
Перспективы развития метода 59
Выводы 60
Глава 4. Вычислительный эксперимент 61
Программное обеспечение 61
Общая характеристика результатов 63
Прямоугольный раскрой 65
Круглый раскрой 67
Показатели качества раскроя 70
Прямоугольный раскрой 70
Круглый раскрой 70
Оценка сложности алгоритма 72
Показатель качества генетического алгоритма 77
Другие оценки 79
Выводы 81
Глава 5. Область применения метода 82
Технологии раскроя материалов 82
Лазерная промышленность в России 85
Устройство лазерных установок 86
Примеры программного обеспечения 89
Выводы 90
Заключение 91
Список использованных источников 91
Приложение 98
Введение к работе
Актуальность темы исследования
Плоский раскрой - это оптимизационная задача поиска плотного размещения множества меньших по размеру предметов, называемых деталями, на больших объектах, называемых заготовками. Она ставится во многих областях промышленности. Цель постановки и решения такой задачи - максимальное использование заготовок или минимизация потерь раскроя.
Сокращение величины обрези, объема незанятого пространства и т.д. - всегда было особенно важным в отраслях промышленности массового производства, так как малые усовершенствования размещения могут приводить к большим сбережениям материала и значительно уменьшать себестоимость продукции. Ручной подбор размещений - процесс субъективный, неэффективный при большом количестве деталей и, соответственно, далеко не всегда дающий удовлетворительный результат. При раскрое дорогостоящих материалов, материалов, имеющих особенные физические свойства, целесообразность сведения потерь к минимуму также имеет очевидное экономическое обоснование.
Необходимость разработки рациональных методов раскроя обоснована еще в 40-х годах XX века. В СССР первые разработки принадлежат академику Л.В. Канторовичу. На сегодняшний день существует множество алгоритмов, созданных для решения подобных задач. В то же время практически нет универсальных разработок, которые позволили бы решать различные (в рамках некоторого класса) задачи раскроя на основе одного и того же метода.
Последние несколько лет ряд металлургических и машиностроительных предприятий впервые приобрели или заменяют морально и физически устаревшую технику, осуществляющую лазерный раскрой листового металла (в том числе, Западно-сибирский металлургический комбинат (г. Новокузнецк), Курганский автобусный завод, «Химконцентрат» (г. Новосибирск), «ЭлСиб» (г. Новосибирск), Тверской вагоностроительный завод) и другие. Установки для лазерной резки на некоторых предприятиях имеются уже десятилетие, но только в настоящее время руководство получает возможность модернизировать процесс производства.
Лазерный раскрой имеет ряд безусловных достоинств: высокая точность резки и как следствие легкость сборки конструкций из вырезанных деталей; возможность существенно уменьшить потери металла за счет маневренности режущего устройства и программного управления; высокое качество среза края заготовки и как следствие экономия средств на последующую обработку; автоматизированность процесса, быстрое осуществление раскроя.
5 Область применения технологии лазерной резки очень широка, с ее помощью раскраивают и детали для железнодорожных вагонов, и комплектующие для бытовой техники, и различные декоративные элементы.
Для подобного современного оборудования целесообразна разработка эффективного метода раскроя плоского материала на наборы деталей различных размеров, решающего задачу для различной геометрической формы деталей.
Цель работы и решаемые задачи
Целью работы является создание метода, позволяющего решать различные задачи плоского раскроя. Для ее достижения последовательно проведены следующие исследования и разработки:
постановка и формализация задач раскроя полубесконечной полосы на наборы прямоугольников («прямоугольный раскрой») или кругов («круглый раскрой») различного размера;
решение поставленных задач при помощи генетического алгоритма, в котором за геометрическую форму упаковываемых предметов отвечает специальная процедура -декодер; декодер выступает параметром генетического алгоритма, то есть сам алгоритм оптимизации не зависит от формы предметов;
разработка «краевого» декодера для задачи круглого раскроя;
реализация «блочного» декодера для задачи прямоугольного раскроя;
разработка математического и программного обеспечения для решения поставленных задач;
исследование эффективности разработанного алгоритма;
расширение метода раскроя полубесконечной полосы до раскроя набора листов;
разработка математического и программного обеспечения для решения практической задачи прямоугольного раскроя листов для технологического лазерного участка с учетом специфических ограничений на размеры рабочего поля;
рассмотрение перспектив развития и возможностей по реконструкции и применению метода для решения различных задач плоского раскроя.
Методы исследования
Стохастическая оптимизация, имитационное моделирование, векторная алгебра и геометрия, численные методы.
В настоящее время при решении оптимизационных задач все чаще используются методы, основанные на эволюционном подходе. В частности, генетические алгоритмы зарекомендовали себя как метод, достигающий компромисса между качеством решения и
вычислительными затратами, то есть достаточно быстро получающий решение приемлемой точности. Генетические алгоритмы целесообразно использовать как метод решения задач раскроя и упаковки, которые, являясь NP-полными, не имеют эффективных точных методов решения. Генетический алгоритм, как правило, находит решение за полиномиальное время (т.е. за время, полиномиально зависящее от размерности задачи). Это свойство имеет особенное значение при решении задач раскроя большого количества деталей. Кроме того, за счет уменьшения времени, затраченного на составление плана раскроя, можно более эффективно эксплуатировать дорогостоящее оборудование.
Основные защищаемые положения
1. Построен генетический алгоритм, работающий с перестановками абстрактных
предметов и не зависящий от их геометрической формы; параметром такого алгоритма
является декодер, трансформирующий перестановку в карту раскроя объектов на предметы;
проведена серия вычислительных экспериментов, которая:
показала, что асимптотическая сходимость алгоритма сохраняется при смене декодера;
позволяет предположить, что разработанный алгоритм решения NP-полной задачи имеет полиномиальную сложность.
Для решения задачи круглого раскроя полосы разработан специальный краевой декодер, основная идея которого носит общий характер и применима для упаковки предметов других несложных геометрических форм; для задачи прямоугольного раскроя полосы реализован блочный декодер; для задачи прямоугольного раскроя набора листов модифицирован блочный декодер и алгоритм раскроя полосы.
При помощи разработанных алгоритмов:
решена задача прямоугольного раскроя полубесконечной полосы;
поставлена и решена задача круглого раскроя полубесконечной полосы;
поставлена и решена задача прямоугольного раскроя набора листов с осуществлением предварительного раскроя листов на крупные заготовки, необходимого в связи с наложенным технологическим ограничением на размер поля резки лазера;
разработано соответствующее программное обеспечение.
4. Разработанное программное обеспечение (для решения задачи прямоугольного
раскроя набора листов с учетом технологических ограничений на размер поля резки лазера)
принято в эксплуатацию и используется для повышения экономичности лазерного раскроя
плоских металлических материалов в научно-исследовательской лаборатории процессов
7 пластической деформации и упрочнения Московского государственного института стали и сплавов.
Научная новизна
Поставлена и решена малоизученная задача круглого раскроя; разработан оригинальный «краевой» декодер для использования в предложенном генетическом алгоритме; основная идея декодера носит общий характер и применима для упаковки предметов других несложных геометрических форм;
поставлена и решена практическая задача раскроя набора листов на прямоугольные детали с осуществлением предварительного раскроя листов на крупные заготовки; для решения задачи разработана модификация предложенного генетического алгоритма и блочного декодера;
для построенной разновидности генетического алгоритма, работающей с перестановками абстрактных предметов и не зависящей от их геометрической формы предметов, проведена серия вычислительных экспериментов, которая показала, что асимптотическая сходимость алгоритма сохраняется при смене декодера, и позволяет предположить, что разработанный алгоритм решения NP-полной задачи имеет полиномиальную сложность.
Обоснованность научных положений и выводов
Научные положения, выводы и практические рекомендации корректно обоснованы и подтверждены математически путем анализа результатов экспериментальных исследований разработанного метода.
Практическая значимость
На основе сформулированного метода разработано математическое и программное обеспечение, реализующее эффективный алгоритм решения задач оптимизации плоского раскроя различных прямоугольных, либо различных круглых деталей. Данное программное обеспечение можно использовать: для решения практических промышленных задач (например, в НИЛ ППДиУ МГИСиС); как обучающее и демонстрационное средство для проведения практических занятий и лабораторных работ (например, на кафедре обработки металлов давлением МГИСиС); как базовый проект для разработки нового программного обеспечения для решения других задач плоского раскроя.
8 Реализация результатов
Метод разрабатывался преимущественно для лазерной технологии резки материала. Непосредственно задача плоского раскроя на произвольное число предметов различной формы часто встречается в сервисных металлоцентрах и заготовительных цехах машиностроительных предприятий. Там лазерный аппарат, оснащенный координатным столом, осуществляет раскрой стального или, например, алюминиевого листа по заданному плану раскроя, а управление перемещением режущего устройства осуществляется программным путем.
В НИЛ ППДиУ МГИСиС часто встает задача рационализации карты раскроя прямоугольных листов на прямоугольные предметы. Задача осложняется тем, что размер листов, как правило, превышает размер рабочего поля резки лазера. В связи с этим требуется осуществлять предварительный раскрой листов на крупные заготовки.
Предложенный метод был модифицирован в соответствии накладываемыми технологическими ограничениями. Разработанное программное обеспечение принято в эксплуатацию и используется для повышения экономичности лазерного раскроя плоских металлических материалов (нержавеющей, конструкционной, инструментальной, броневой марок сталей). При этом в процессе раскроя обеспечивается экономия материала на 3-16%, а также достигается повышение производительности работы лазерной установки типа «ТЛУ-1000».
Апробация работы
Основные положения диссертации докладывались на 57-ой научно-технической конференции студентов и аспирантов МГИСиС в 2002 году, на Всероссийской конференции «Высокопроизводительные вычисления и технологии» в 2003 году, на I и II Международных конференциях «Параллельные вычисления и задачи управления» в 2001 и 2004 годах.
Публикации
Содержание диссертации отражено в 4 печатных работах [47,48,49,50]. Кроме того, опубликовано еще 2 работы, посвященных решению NP-полных проблем с использованием генетических алгоритмов [45,46].
Структура и объем работы
Работа состоит из введения, пяти глав и заключения. Первые две главы носят обзорный характер. В Главе 1 подробно анализируется современное состояние проблем раскроя и упаковки, Глава 2 посвящена методу стохастической оптимизации - генетическим алгоритмам.
В Главе 3 ставится задача раскроя полубесконечной полосы на предметы несложной геометрической формы. Предлагается схема генетического алгоритма, использующая в качестве параметра процедуру декодирования или декодер. Декодер - единственная структурная единица метода, зависящая от геометрической формы предметов. Решаются задачи прямоугольного и круглого раскроя полосы с использованием одного и того же генетического алгоритма. Описьшается разработанный для решения задачи круглого раскроя оригинальный краевой декодер. Предложенный метод расширяется для решения задачи раскроя набора листов. Решается практическая задача прямоугольного раскроя набора листов с учетом технологического ограничения на размер поля резки лазера. Рассматриваются возможности использования предложенного метода для решения других задач плоского раскроя.
В Главе 4 описывается разработанное на основе проведенных исследований программное обеспечение, приводятся и анализируются результаты поставленных с его помощью вычислительных экспериментов. Глава 5 посвящена области применения разработанного метода и особенностям практической реализации раскроя плоского листа. В заключении формулируются основные результаты проведенной работы.
![Разработка методов, моделей и алгоритмов прогнозирования и донозологической диагностики кожных болезней, имеющих представительство на проекционных зонах, с использованием нечеткой логики принятия решений и рефлексодиагностики [Электронный ресурс]](/i/i/4381/168311.png "Разработка методов, моделей и алгоритмов прогнозирования и донозологической диагностики кожных болезней, имеющих представительство на проекционных зонах, с использованием нечеткой логики принятия решений и рефлексодиагностики [Электронный ресурс] Ходеев Денис Владимирович")
