| Тема выпускной работы | Подсистема оптимизации работы автоматизированных технологических комплексов с использованием многокритериальных генетических алгоритмов |
| Научный руководитель | к.т.н. доцент Секирин Александр Иванович |
| Факультет | Компьютерных наук и технологий |
| Кафедра | Автоматизированных систем управления |
| Специальность | Информационные управляющие системы |
Содержание
1. Цели и задачи работы
2. Введение. Обоснование актуальности работы.
3. Предполагаемая научная новизна
4. Предполагаемая практическая ценность
5. Обзор исследований и разработок по теме
6. Постановка задачи исследования
7. Описание объектно-ориентированного моделирования
8. Многокритериальные генетические алгоритмы
9. Заключение
10.Список литературы
Обеспечение высокой эффективности работы автоматизированных технологических комплексов механообработки и максимального использования возможностей оборудования за счет использования разработанной компьютерной подсистемы многокритериальной оптимизации.
• Провести анализ методов, моделей, алгоритмов и инструментальных средств для оптимизации работы АТК
• Провести выбор и обоснование метода для оптимизации работы производственного участка, выбрать основные критерии для оценки эффективности работы АТК
• Разработать обобщенную модель АТК
• Используя модель АТК разработать и программно реализовать алгоритм для составления субоптимальных расписаний работы оборудования учитывая одновременно несколько критериев
В практике человеческой деятельности, будь то профессиональная сфера или повседневная жизнь, постоянно возникают задачи выбора, предполагающие в результате принятие решения. Только в ряде случаев, лицо принимающее решение осуществляет выбор (принимает решение) интуитивно, опираясь на собственный опыт и здравый смысл, а решение более сложных задач требует особого подхода, так как в данном случае задача принятия решения представляет собой, по сути, уже оптимизационную задачу.
В процессе управления сложными технологическими комплексами и организационно-техническими системами необходимо постоянно принимать непростые решения, связанные с учетом многих критериев протекания производственных процессов и ограничений на ресурсы. Без использования возможностей современной вычислительной техники достаточно сложно сделать оптимальный выбор. В этой связи необходимо разрабатывать и внедрять системы поддержки принятия решений.[1]
Необходимость внедрения информационных систем управления более остро стоит перед предприятиями машиностроительной отрасли. Машиностроение является одной из наиболее наукоемких, сложных, требующих высококвалифицированных кадров отраслей материального производства. Уровень развития машиностроения определяет уровень развития государства в целом.[2]
Основой для создания компьютеризированных производственных систем являются автоматизированные технологические комплексы (АТК). Это технологические структуры с законченным производственным циклом (участок, цех) и различной степенью автоматизации. АТК включает в себя автоматизированное технологическое оборудование для механообработки деталей, а также вспомогательное оборудование: автоматизированный транспорт и автоматизированную складскую систему.
АТК представляет собой сложный динамический объект. Для эффективного использования такого объекта необходимо формировать и динамически корректировать с учетом изменения ситуации на производстве оптимальное расписание работы оборудования. На реальный производственный процесс влияет ряд внешних факторов:
- сбои в транспортно-складской системе;
- введение в производство новой детали;
- выход из строя технологического оборудования.
Для разработки метода оптимизации необходима модель АТК, которая обеспечит близкое к реальности отображение процесса работы оборудования и движения материальных и информационных потоков.
Оптимизации работы АТК очень трудоемкая задача, решение которой имеет огромное значение для работы всего предприятия. В традиционном подходе присутствуют существенные недостатки, поэтому в результате работы планируется получить новые методы, которые позволяют создавать более гибкие модели, чем методы статистической обработки информации.
Для обеспечения высокой эффективности работы производственных участков и максимального использования возможности оборудования, необходимо создавать близкие к оптимальному расписанию работы станков (ГПМ). Основным инструментом для этого являются моделирование и оптимальное управление.
Неизученным остается движение партий деталей непосредственно в производственной среде, на производственном участке согласно технологическому маршруту. Создание программных комплексов для моделирования и управления работой производственных участков, составление близких к оптимальным расписаниям работы оборудования, есть актуальной научно-технической задачей [3].
На основе анализа существующих разработок в области эволюционных методов перспективным решением сложных комбинаторных задач многокритериальной оптимизации есть использования генетических алгоритмов. Это позволит сократить время получения оптимальных или приемлемых расписаний работы, и быстро реагировать на изменение производственной ситуации.
Данная задача уже решалась с помощью генетических алгоритмов, где хромосомы делились на 2 уровня. Первый уровень отвечал за очередность запуска партий деталей в обработку, а второй за размер этих партий.[3] Научная новизна моей работы заключается в учете одновременно нескольких критериев благодаря использованию многокритериального подхода к оптимизации.
Моделирование работы автоматизированных технологических комплексов механообработки позволит получать оценки загрузки всех видов оборудования и выявлять «узкие места», снижающие эффективность работы АТК. Проведение на модели анализа различных вариантов их устранения позволит разрабатывать практические рекомендации, обеспечивающие повышение загрузки технологического оборудования. Применение модифицированного двухуровневого генетического алгоритма совместно с объектной моделью позволит получать субоптимальные расписания работы оборудования по нескольким критериям, что обеспечивает высокую эффективность функционирования АТК механообработки.
• глобальный
Создан ряд программных продуктов, которые можно отнести к ERP системам, например, LEKIN и TACTIC. Из зарубежных авторов можно выделить: Rong Zhou, Jun Zhang, Alan S. Manne и др.
• национальный
В целом по Украине было найдено множество работ по смежным областям с разрабатываемой подсистемой. Можно выделить также существующие разработки по данной теме: система технологической подготовки, оперативного планирования и диспетчерского контроля «ФОБОС», (MRP-II) ERP-системы «Компас», СПРУТ-ОКП, Zenith SPPS и др.
• локальный
По результатам поиска среди материалов портала магистров ДонНТУ были найдены работы Андреенковой Е. А. и Башева В.Г. в которых рассматривались проблемы оптимальной загрузки оборудования и управления производственным участком в различных отраслях. Из научных работ преподавателей нашего университета по данной теме были найдены
работы Секирина А. И.
Фактически задача оптимизации работы состоит из двух этапов:
- разработка модели АТК
- разработка алгоритма оптимизации
Укрупнено работа подсистемы показана рисунке 1
Рисунок 1 – схема работы подсистемы оптимизации
В общем виде задачу оптимизации можно описать следующим образом: имеется n деталей, которые необходимо обработать на L станках. При этом необходимо составить расписание работы оборудования, очередность запуска деталей в производство и размеры партий запуска, которые будут удовлетворять одновременно нескольким критериям оценки качества расписания.
Запишем основные критерии, по которым может быть произведена оценка эффективности полученного расписания:
1. Минимизация длительности цикла изготовления деталей
Tопт = Т > min, (1.1)
где Т - общее время производственного цикла.
где Тij - длительность цикла технологической операции i-ой партии деталей;
αij - длительность простоя перед началом выполнения j-ой технологической операции над i-ой партией деталей;
2. Максимизация среднего коэффициента загрузки технологического оборудования (максимизация загрузки оборудования)
Копт з = 1/m∑Kз -> max, или Копт з = -1/m∑-Kз -> min (1.3)
где m - количество оборудования;
Kз – коэффициент загрузки i-го оборудования.
Коэффициент загрузки i-гo оборудования определяется отношением времени производительной работы к общему времени по формуле:
3. Минимизация временных затрат на перенастройку оборудования
где tн – общее время затраченное на перенастройку оборудования
Τij – время затраченное на перенастройку i-го станка j-ый раз
n – количество перенастроек
Т.е. фактически необходимо минимизировать количество перенастроек:
n -> min (1.6)
При этом необходимо учитывать следующие ограничения:
1. Ограничения по объемам изготовления:
Nпл=Nф, (1.7)
где Nф - фактическое изготовленное количество деталей i-го типа (i=l,...,K);
Nпл - заданное в производственной программе количество деталей i-гo типа.
К - номенклатура изготавливаемых деталей.
2. Ограничения по срокам изготовления:
Tпл ≥Tф , (1.8)
где Tф - фактический срок изготовления i-ой детали (i=l,...,K);
Tпл - директивный срок изготовления i-ой детали.
3. Ограничения по фонду времени работы технологического оборудования:
где Тij - длительность выполнения технологической операции;
Ri - ресурс i-ой группы оборудования.
В реальных условиях производства на функционирование цеха механообработки оказывают влияние различные возмущающие воздействия {Vk}, которые приводят к отклонениям выпуска деталей от производственной программы.
Задачей управления является обеспечение выпуска продукции согласно производственной программе (Nпл) по количеству и в установленные сроки при эффективном использовании ресурсов (Rl) в условиях действия возмущений (Vk). Обеспечение высокой эффективности использования ресурсов (Rl) и функционирования цеха в целом достигается за счет оптимизации расписаний работы оборудования.
Процесс изготовления деталей Di (i=l, ..., п) разбивают на технологические операции Оij (i=1,..., п; j=l,..., m). Детали одного типа объединяются в транспортные партии и в разрезе расписаний рассматриваются как технологическая единица. Каждая операция может быть выражена:
Оij = <Нij ,Тij>, (1.10)
где Нij - номер группы технологического оборудования;
Тij - продолжительность выполнения операции.
Технологический маршрут представляет собой последовательность выполняемых операций, которые проходит i-я деталь в процессе обработки:
Мi = < Оi1, Оi2,..., Оim > (1.11)
Операция Оij должна выполняться без перерыва с самого начала. Если обозначить через tij - время начала выполнения операции Оij, а через tij' -момент окончания обработки, то должно выполнятся равенство:
tij' = tij + Tij (1.12)
Очевидно, что время начала обработки зависит от времени выполнения предыдущих операций и всегда выполняется неравенство: tij ≤ tij+1. Тогда совокупность {tij} (i=1,..., n; j=l,..., m), удовлетворяющих всем технологическим и временным ограничениям, является расписанием работы.
Описание объектно-ориентированного моделирования
Объектное моделирование – моделирование, при котором все моделируемые компоненты системы представляются в виде объектов с особой структурой, набором параметров и методов, описанных с помощью компьютерных языков моделирования. Такой подход позволяет легко создавать модели объектов из уже созданных прототипов, что делает процесс моделирования и организации процесса взаимодействия более простым [7].
В современном объектно-ориентированном моделировании часто большое значение имеет понятие события. Объекты представляют собой упрощенное описание реальной сути наглядной области, которая идеализируется. Если соответствующие модели адекватные решаемой задаче, то работать с ними оказывается намного удобнее, чем с низкоуровневым описанием всех возможных свойств и реакций объекта.
Объектно-ориентированное моделирование основывается на описании структуры и поведения проектируемой системы, то есть, фактически, отвечает на два основных вопроса:
1) из каких частей состоит система;
2) в чем состоит ответственность каждой из частей.
Учитывая модульный принцип построения АТК, данный подход является наиболее приемлемым. При построении модели выделены следующие классы:
- гибкий производственный модуль (ГПМ);
- автоматизированный транспортный модуль (АТМ);
- автоматизированный склад (АС);
- система управления (СУ).
Для управления комплексом и создания событий введен дополнительный управляющий класс «диспетчер событий».
Многокритериальные генетические алгоритмы
Генетический алгоритм — это алгоритм, который позволяет найти удовлетворительное решение к аналитически неразрешимым или тяжело разрешимым проблемам через последовательный подбор и комбинирование искомых параметров с использованием механизмов, напоминающих биологическую эволюцию.[8]
При использовании ГА задача оптимизации переформулируется в задачу нахождения максимума некоторой функции f(x1, x2, …, xn), называемой функцией приспособленности (fitness function). Она должна принимать неотрицательные значения на ограниченной области определения (для того, чтобы мы могли для каждой особи считать её приспособленность, которая не может быть отрицательной), при этом не требуются непрерывность и дифференцируемость.
Работа классического ГА состоит из трех операций: селекция, кроссинговер и мутация. На рисунке они обозначены соответственно цифрами 1, 2 и 3.
Присущие генетическим алгоритмам свойства способствуют их эффективному применению при решении задач многокритериальной оптимизации, поскольку ГА основаны на использовании множества потенциальных решений – популяции и глобальном поиске в нескольких направлениях. Также ГА не предъявляют никаких требований к виду целевых функций и ограничениям.[10]
При применении генетических алгоритмов для решения конкретной задачи необходимо выбрать или разработать основные компоненты, такие как метод кодирования потенциального решения, генетические операторы кроссинговера и мутации, метод отбора родителей, построить функцию приспособленности (фитнесс-функцию), позволяющую оценивать потенциальные решения.
Поскольку многокритериальная оптимизация является естественным развитием обычной численной или комбинаторной оптимизации, то многие разработанные методы были распространены на этот более общий случай. При использовании ГА для многокритериальной оптимизации центральным вопросом является построение функции приспособленности. За последние десятилетия разработано несколько подходов.
Для оптимизации работы АТК предлагается использовать метод взвешенной функции. Он является естественным развитием классических методов оптимизации, где новая «общая» целевая функция строится из заданных в виде взвешенной суммы:
Здесь каждой целевой функции fi(x) присваивается свой вес wi и задача сводится к скалярному случаю. При этом различные веса wi дают разные решения в смысле Парето.
Учитывая специфику области применения, метод является оптимальным, т.к. критерии оценки имеют различную значимость. Например, при упоре на сокращении времени длительности цикла обработки детали, тем самым уменьшая время «пролеживания» детали на складе, может увеличиться время простоя рабочих мест, что является экономически нецелесообразным [2].
Заключение
Автоматизация обрабатывающего и вспомогательного оборудования с использованием современных компьютерных технологий, в условиях развития машиностроения, есть одним из основных направлений технического прогресса в машиностроении. Оборудование должно обеспечивать выполнение заданной номенклатуры технологических операций на участке в установленный срок и обладать способностью оперативно реагировать на изменение производственной ситуации.
Для обеспечения высокой эффективности работы автоматизированных производственных комплексов необходимо создавать близкие к оптимальному расписанию работы оборудования.
В работе был проведений анализ методов, моделей и алгоритмов для оптимизации работы АТК, рассмотрены инструментальные средства, которые используются для оперативного управления производством в машиностроении. В результате работы был исследован вопрос разработки методов многокритериальной оптимизации, выявленные достоинства и недостатки существующих компьютерных систем, методов и алгоритмов.
Для преодоления недостатков предложен многокритериальный генетический алгоритм для оптимизации работы АТК на машиностроительном предприятии.
Список литературы
1. Шеховцов А.В., Крючковский В.В., Мельник А.Н. «Решение многокритериальной оптимизации с использованием адаптивных алгоритмов» [электронный ресурс] — Режим доступа: http://aaecs.org/shehovcov
2. Сачко Н.С. Организация и оперативное управление машиностроительным производством // Н.С. Сачко – Новое знание, 2006. – 520 с.
3. Секирин А.И. Использование генетических алгоритмов для оптимизации работы автоматизированных технологических комплексов механообработки [электронный ресурс] — Режим доступа: http://masters.donntu.ru/2009/kita/aleksandrova
4. В.И. Ковальский Организация и планирование производства на машиностроительном предприятии. // М.: Машиностроение, 1986. – 288с.
5. Туровец О.Г. Организация производства и управления предприятием. // О.Г. Туровец, В.Б. Родионов, М.И. Бухалков. – М: Издательский дом «Инфа-М», 2005. – 346с.
6. М. Скворцова Математическое моделирование [электронный ресурс] — Режим доступа: http://mat.1september.ru
7. Николаенко В.Л., Паршук А.П. Статья: Методика объектного моделирования системы оптимизации производственных затрат [электронный ресурс] — Режим доступа: http://www.pdaa.edu.ua/np/pdf2/36.pdf
8. Исаев С. Популярно о генетических алгоритмах [электронный ресурс] — Режим доступа: http://algolist.manual.ru
9. Дилигенский Н.В., Дымова Л.Г., Севастьянинов П.В. «Нечеткое моделирование и многокритериальная оптимизация производственных систем» // М.: «Издательство Машиностроение - 1», 2004
10. В.М. Курейчик "Генетические алгоритмы и их применение" // Издательство ТРТУ, издание второе, 2002. - 242 с.