Введение к работе
Актуальность теш.
Одним пз основных достижений в развития автоматизации промш-ленного производства на современном этапе является создание гибких производственных систем (ПІС), внедрение которых позволяет бистро реагировать на изменения требований к производимой продукции, повышать качество и объема производства яри значительном сокрацении его затрат.
Эффективность фушсционирования ГПС во многом определяется качеством их систем оперативного управления (СОУ). При этом такие свойства ПІС как гибкость, высокая динамичность, многономенклатур-ность обусловливают появление целого ряда проблем перед разработчиками СОУ. Несмотря на значительное число работ по данной тематике, общая теория и методология построения и исследования СОУ ГПС в настоящее время значительно отстают от требований практики.
Опыт создания ШС показал, что разработка унифицированной СОУ ППС наталкивается на целый ряд принципиальных трудностей, поскольку казвдое производство обладает набором специфических признаков, в результате чего в каждом конкретном случае возникают особые требования к СОУ. В то же время можно выделить основные функций и задает СОУ ГПС, являвшиеся общими для болышгства производственных зистем. Специфика производства отрезается главным образом на алго-зитмах решения задач оперативного управления ГПС. В этих условиях актуальніш становится вопрос разработки маїеиатических моделей и методов, а также развитых инструментальных средств для аЕтскатиза-дии исследования (анализа и синтеза) математического обеспечения ЗОУ ГПС. При этом в качестве одного из наиболее перспективны;': средств для исследования СОУ ГПС выделяются сети Петри, обладающие <ак мощным формально-логическим аппаратом анализа структурных и гинамических свойств ШС, так и возможностью графического представления модели объекта управления (ОУ), адекватно инторпретируе-лого понятиями предметной области.
Целью диссертационной работа является разработка комплекса троблемно-ориентироаанных моделей, методов и программных инструментальных средств, основанных на использовании аппарата сетей Іетри, для автоматизации исследований математического и программ-юго обеспечения СОУ ШС.
Достижение указанной цели требует постановки и решения следующих основных задач:
построения концептуальной модели объекта исследования;
разработки модели ОУ на основе сетей Петри;
разработки методов решения типовых задач оперативного управления на осаово сетевого представления ОУ;
разработки и реализации программных, инструментальных средств для проготипирования и исследования СОУ ГПС.
Методы исследования. Основные результаты работы получены с использованием аппаратов теории управления, теории исследования операций, сетей Петри и методов логического программирования.
Научная новизна работы.
1. Предложена сетевая модель ОУ ШС, основанная на
декомпозиции описания производственного процесса на модели техно
логического комплекса и технологических процессов обработки изде
лий.
2. Впервые, в рамках формализма сетей Петри, для решения за
дач объемного планирования производственных систем дискретного ти
па разработан метод комбинаторной оптимизации, основанный на ана
лизе t-кнвариантов сети.
3. Разработана оригинальная модель оперативно-календарного планирования, в основе которой лежит эвристический поиск на дереве достижимости временных сетей Петри, управляемый правилами приоритета.
Практические результаты работы.
-
Разработанные в рамках формализма сетей Петра модели, пос-тановки задач, алгоритмы и методы являются эффективным и гибким средством формализации и решения задач управления, планирования и проектирования дискретных производств.
-
Средетвада стандартного Пролога получены исполнимые спецификации разработанных моделей решения типовых задач оперативного управления ГПС, которые могут быть реализованы с помощью большинства версий языка для различных типов ЭВМ.
-
На ПЭВМ IBM PC/AT на базе языка Turbo-Prolog 2.0 реализованы инструментальные средства, предназначенные для автоматизации исследований систем оперативного управления ГПС, которые также могут быть использованы при создании систем оперативно-календарногс
лавирования дискретных производств и систем проектирования техно-эгических КОМПЛЄКС0В.
4. С использованием разработанных инструментальных средств эализована система поддеркки принятия решений в оперативно-кален-арном планировании сборочно-сварочпых участков судокорпусного роЕзводства верфи.
Внедрение результатов лиссе ртанионной работы.
Исследования, выполь'эчнне в диссертационной работе, является астью тематика научно-исследовательских госбюджетных и хоздого-зрннх работ, пронодикык в лаборатории интегрированных систем ав-матизацкя Ленинградского института информатики ж автоматизации 1 СССР (ЛМАН).
Разработанные в диссертационной работе модели операгивно-ка-5йдарного планирования используются в рамках системи организаци-зной подготовки судокорпусного производства на судостроительных, зводах г. Санкт-Петербурга "Северная верфь" и ПО "Балтийский за-зд". Внедрение результатов работа существенно сокращает срока эдготовкц производства, снижает трудоемкость и повышает качество эшшмземых peacHrit, «то обусловливает повышение эффективности :<жзводства в целом.
Сетевые модели и программные средства реиения оздоч шзяаче-ія деталеонерандй и оперативно-календарного планирования были ио-зльзованы при разработке исследовательского варианта системы нод-їряжи принятия решений при переілхіфїлировании прошшленвл зедприятнй по договору на НИР медпу .*ШИАН і* ЛФ ЩПШК. Ожидаемый шально-экономический эффект от использовать и данной системы, появляющийся в повышении эффективности и снижении трудоемкости '.следований при выработке рекомендацій по перепрофилированию прошенных предприятий Северо-Западного региона, частично достигался за счет применения указанных результатов диссертационной раті.
Модели и методу, разработанные в диссертационной работе, пользуются в учебном процессе на кафедре технологии' приборострое-ія JMTM0 в рамках курсов "Оптимизация в ГШІ", "САПР ТП", "Проок-іровзіше ГПС" и "Специальные' глппн математики".
Акты, подтверждающие внедрение основных результатов работы, зиведены в приложении.
Апробация работа.
Основные результаты диссертационной работы докладывались і обсувдзлись на следукещх конференциях., симпозиумах и семинарах:
VI Международной конференции по ГПС, Пула, Югославия: 19S9 г.;
Международной научно-технической конференции "Интеграции систем целевой подготовки специалистов и автоматизированных систег различного назначения", Алушта, 1990 г.;
V Ленинградском симпозиуме по теории адаптивных систе? "Адаптивные и экспертные системы в управлении", Ленинград 1991 г.;
V Всесоюзной школе молодых ученых и специалистов "Проблем управления 91", М.Маяк Крымской обл., 1991 г.;
Всесоюзной научно-практической конференции "Гибридные ин теллектуальше системы", Терскол, 1991 г.;
Всесоюзной научно-технической конференции "Интеллектуальны системы в машиностроении", Самара, 1991 г.;
Fourth World Conference on Robotic Research, Pittsburg USA, 1991;
IX Всесоюзной школе "Программное обеспечение матемагическо го моделирования, управления и искусствешюго интеллекта", Адлер 1991 г.
Публикации по теме диссертации.
Результаты диссертационной работы опубликованы в 9 печатни работах.
Структура к объем работы.
Диссертационная работа состоит из введения, четырех глан заключения, списка литературы, включающего 106 наименований, приложений. Содержаїжо работы излслкно ни 153 страницах машинопис іїого текста, иллюстрировано 35 рисунками и 4 таблицами.
КРАТКОЙ содержание работы
Во введении обоснована актуальность диссертационной работа сформудироваш ее цель и задачи.
Глава I- В первой главе рассмотрены основные принципы оргаш зации процесса оперативного управления в ГЯС, определяющие ег< структуру как совокупность взаимосвязанных задач опоративно-кален
дарного планирования, лиспе тчирования и корректировки модели ОУ.
Выделены специфические свойства ГНС, обусловливающие особен-ости решения задач оперативного управления и, в первую очередь, адач оперативного планирования.
Приводится краткий обзор существующие моделей оперзтішно-ка-ендарного лланяровашя ГНС. Предлагается подход, основанный на екомпозиции задачи оперативно-календарного планирования на задач]' азначения деталеоперацШ на элементы техно лопне ского комплекса ТК) и задачу определения расписания, реализующего полученное ная-ачение. Решение нервой задачи гарантирует получение техкологичес-а допустимого расписания, позволяет определить оценки и ограничена наилучшего решения, а такие сократить общее пространство эиска допустимых реиений. Вторая задача заключается в определении зегшеания, реализующего полученное казнь\ош:е и удовлетворяющего зожеству ограничений на вшоддае расчетам характеристики (максп-зльное время простоя, максимальная длина очереди к т.п.). Показа-V что, учитывая случайный характер изменений характеристик ОУ, зязанных со сбоями и отказами элементов ТК, целесообразно искать ниение данной задачи путем определения только части расписания на зкоторый горизонт планирования с последующим покрытием всего пе-юда исходя из принципа скользящего планирования. В случае изме-;ния характеристик ОУ, система инициирует корректировку ото моде-1, определение нового назначения деталеопераций и расписания на йранный горизонт планирования.
Предложена концептуальная модель объекта оперативного управ-іния ГПС, которая дает формальное описание процесса выполнения, юизводственного задания на множестве элементов ТК ГПС.
Производствешюе задание включает номенклатуру изделий, их їличество и технологические процессы обработки. Ограничение еле-івания, определяющее допустимые альтернативные варианты последо-ітельностей обработки каждого изделия, представляет собой отнеше— '.е частичного порядка, заданное на мжжестве технологических ;ераций.
Технологические возможности ТК ГПС характеризуются множеством новных элеметов (ОЭ), предназначешшх для выполнения заданных хнологических операций. Каждый 03 получает задания с входного копителя и передзет результаты обработки на выходной н:>.коп;пч\чь.
Транспортная система ТК ГПС характеризуется множеством транспортных операций, какдая из которых осуществляет перемещение заготовок и деталей между определенной парой накопителей в следующих направлениях: с накопителей склада заготовок на входные накопители 03; с выходных накопителей 03 на входные накопители ОЭ; с выходных накопителей 03 на накопителя склада готовых деталей.
Основным понятием производственного процесса является детале-ояерация, характеризующаяся наименованием типа задания, взятого из гюменклатуры изделий, типом операции, назначением ее на кошфетный элемент ТК и длительностью. Последовательность деталеопераций при изготовлении единицы изделия называется технологическим маршрутом.
Введены основные понятия теории сетей Петри, рассмотрены базовые классы сетей Петри, дан анализ возможностей и ограничений их использования в исследовании СОУ ГПС. Отмечена целесообразность выделения специального класса сетей Петри для формализации ОУ ГПС, связанного с введением, с одной стороны, расширений для адекватного представления модели производственного процесса и понижением размерности сєтєеого описания ОУ, а с другой - ограничений на топологию сети, определяющих условия применения методов исследования , основанных на использовании дерева достижимости и матричного уравнения состояний.
Сформулирована задача построения формальных моделей и инструментальных средств для исследования математического обеспечения СОУ ГПС на базе представления ОУ средствами проблемно-ориентированных сетей Петри.
Глава 2. Вторая глава посвячена вопросам разработки сетевые моделей и методов решения задач оперативного управления ГПС.
Формализация описания производственного процесса Я как 0J ГПС с помощью сетей Петри основана на введении операции композита сетевой модели ТК JfTK и технологических процессов обработки изделий, входящих в описание модели производственного задания Мд .
Модель ТК представляется автоматной сетью Петри (рис.1, а):
to-(T.P,F+,F^,V),
v)v. '!' 'Р U 1,ь ~ конечное множество переходов сети, в кoтopo^ .'jjieMfjHTu подмножества 'Р соответствуют ОЭ, и элементы Ї'1 транспортным о/го рациям ;
р10-—>\гА-&.
?3
>о-
*0
"5
i^A
tl p?
+0
>D
/
^
'to
djo-
~+&
,, r
-*-o lii
-D—*
-*0 cT;
гас. 1. Пример формализации производственного процесса средствами сетей Петри
і) модель ТК ГПС; 0) модель технологических процессов; і) модель производственного процесса
P - конечное кнокесгво позиций, соответствующее множеству накопителей ТК;
F*sP*T, F~zT»P - отношение инциденций сети Из; отображение 7: Р -* Ы определяет емкость накопителей. Сеть Тр, описывающая технологические процессы (рис.1, б), содержит набор компонент связности, квздая из которых соответствует списанию техвологаческого процесса для конкретного изделия. Технологический процесс обработки 1-го изделия представляется ацикличной автоматной сетью Петри:
Трг=(Сг,Dl,Pre1,Post1),
где С1 - конечное множество переходов сети Тр1, соответствующее
множеству обрабатывающих операций;
г - конечное множество позиций, соответствующее множеству
состояний изделия I;
Prels.I)l«Gl, P03tlsCl*Dl - отношения инциденций сети Тр1.
Для построения модели произБОДственного процесса вводятся отношения совместимости моделей ТК и технологических процессов производственного задания - Лсї«с и А*еГ*«1>, а также отоОракение В : А -* Ш, определяющее длительности деталеоперацкй, где А = A0 U Л*.
Операция композиции моделей Rs и Тр определяется следущю* образом:
каждая позиция сети Ra заменяется множеством позиций, связанных с возможными состояниями изделий;
переход сети из, отображающий ОЭ, заменяется множеством переходов, соответствующих допустимым на данном элементе деталеопе-рациям в соответствии с отношением А0;
переход, связанный с транспортной операцией, заменяется множеством переходов в соответствии с отношением At.
Показано, что получаемая в результате операции композиции ординарная сеть Потри (рис.1, в), описывающая структуру производственного процесса на уровне доталеоггераций, является ограниченно! и не содержит ориентированных циклов.
Состояние модели производстгягтого процесса S определяете, набором:
:; - -М, К, Q. Н>.
- if: P'D -* Si - маркировка позицій;
-К: T -* {idle,active} - состояние переходов;
Q: Т -* С определяет операцию, выполняемую активным переходом;
R: Т -* Ш определяет время, оставшееся до срабатывания активных переходов.
Определены правила запуска и срабатывания переходов сетевой моделі производственного процесса.
В терминах сетей Петри задача назначения деталэошрашй сформулирована как задача определения количества срабатываний переходов, необходимого для перевода модели из начального состояния в целевое, при этом состояния определяются только маркировкой позиций. Используя матричное уравнение состояния сети Петри, эта задача в общем случае монет быть представлена как задача целочисленного линейного программирования следующего вида:
mln F'X1 ІУ.ХТ = й.-ЛГ,
Ft О
Ш,
где К - вектор срабатываний переходов;
F - некоторый вектор стоимостей срабатывания переходов;
IV - матрица инциденций сети Петри;
М0.Мк - начальная и целевая маркировка сети.
Для решения этой задачи разработан метод комбинаторной оптимизации, заключающийся в итеративном изменении назначения деталеопераций (X' =X+Y), улучшающего на кавдой итерации целевую функцию на основе поиска вектора У (являющегося t-инвариантом сети), такого что:
' №«r'r = О
F*Y7 < О
Y і 2
у( J 0 для І такого, что 2{ = о.
Дается определение множества генераторов t-инваряаптов и начального опорного решения. Для этого каждому изделию сопоставляется дополнительный переход, входной и выходной позицией которого
являются соответствующий исток и сток сетевой модели производственного процесса. Множество генераторов t-инвариантов определяется как множество минимальных t-инвариантов, включающих дополнительный переход с отрицательным знаком. Физический смисл введенного множества заключается в том, что оно определяет множество допустимых технологических маршрутов обработки изделий с учетом альтернативности технологии и взаимозаменяемости оборудования. Показано, что любой t-инваріаят сети моает быть представлен лиеєйнов комбинацией введенных генераторов t-инвариантов. Опираясь на данное представление, начальному рєшешпо задачи сопоставляется вектор срабатываний, элементы которого, соответствуюдие дополнительным переходам, равна количеству единиц изделия, определяемому производственным заданием, а остальные равны 0.
Задача оперативно-календарного планирования сформулирована как задача поиска пути на дереве достижимости временной сети Петри, проходящему через Еершны, допустимые с точки зрения множества заданных ограничений на возможные состояния модели ОУ и выходные расчетные характеристики расписания. При этом каждая вершина характеризуется состоянием модели. ОУ и множеством значений интегральных параглетров пути от начальной до текущей вершины. В общей случае., в качестве условий, определякцих долевую вершину, мокеа бить задан горизонт планирования.
Основу процедуры поиска составляет дсиск в глубину, которые рассматривается как механизм организации многовариантного имитационного моделирования с возвратом. Такой подход позволяет использовать теоретические результаты и практически! опыт решения зада1: поиска аффективных расписаний с помощи развитого аппарата имитационного моделирования, эффективным образом организовать интерфейс с пользователем для контроля процесса генерации расписания и не требует дополнительного хранения вершин, не лежаїщн. на рассматриваемом пути.
Банное преимущество предлагаемого подхода заключается в том, что с целью повышения аффеїстивносїи процедуры поиска для управления процессом генерации расписания могут использоваться различные эвристические знания предметной области. В качестве примера в работе используются знания предметной области, представленные в форма правил приоритета и правил исключения неперспективных направлений.
Для построения модели лиспетчирования введено правило преобразования исходной сетевоЗ модели Мш, гозволящее интерпретировать переходы отдельными событиями. Определены механизмы разрешения и срабатывания переходов сети в соответствии с интерпретируемыми ими типами событий. Процесс диспетчирования заключается в имитационном моделировании поведения управляющей сети Петри в реальном масштабе времени.
Выделены и систематизированы наиболее характерные классы сбойных ситуаций в ГГО. Для кавдого класса определены правила корректировки сетевой модели производственного процесса.
Глава 3. В третьей главе рассмотрены вопросы разработки программных инструментальных средств (ИС) для исследования СОУ ГПС.
Для эффективного решения задач автоматизации исследований СОУ ГПС МО должны обеспечивать:
поддеркку формирования/модификации модели ОУ;
поддеркку формировашя/модифнкации алгоритмов решения задач назначения и планированияі визуализацию и интерактивный контроль процессов их решения;
формирование спецификации и прототипировашіе программного обеспечения СОУ ГПС:
интерфейс с имитационной моделью ОУ;
визуализацию значений основных параметров функционирования ОУ в,ходе имитационного эксперимента;
сбор статистической информации и отображение результатов эксперимента.
В качестве средств спецификации програшного обеспечения СОУ ГПС использован язык Пролог, который, благодаря декларативной семантике и недетерминизму, предоставляет возможность эффективного и гибкого описания представленных в главе 2 сетевых моделей и процедур решения задач. Разработано представление сетевой модели ОУ, назначения деталеопераций и расписания с помощь» фактов Пролога. Средствами стандартного Пролога получены спецификации процедур решения типовых задач оперативного управления ГПС, которые могут быть реализованы с помощью большинства версий языка для различных типов ЭВМ. Преимущества декларативной семантики и недетерминизма Пролога особенно хорошо видны на примере фрагмента спецификации процедуры поиска на дереве достижимости:
tree_searchCi?iEie) :-end_search(Tlme).
tree_search(CurrentJFlme): -
priorlty_list generate_step(Time,[candidate(Shop, Operation) ІІЛ):~ possible(Shop,Operation),asstgn(Tlme,Shop,Operation), generate_step(Time,I). generate_step(T:une, [_f L) ):~generate_step(Tlme,L). assign (Time .Shop.Operation):- asslgnjnade (T lme, Shop, Operation). assign(Time,Shop,Operation):- asslgn_baclmp (Time, Shop .Operation), Tail. next_state(Current_Tlme«Duration):- state_change (CurrentJTime .Duration). next_state(CurrentJTime.Duration) :- state_backup (CurrentJTime .Duration) .Tail. Конкретная реализация ИС осуществлена на ПЗВМ IBM PC Аї с использованием средств языка Turbo-Prolog 2.0. Структура ИС включает следующие основные элементы: сетевой редактор модели ОУ; проблемно-ориентированную библиотеку программных модулей; диалоговые средства управления ИС. Визуализация решений задачи назначения деталеодаравдй организована на основе гистограмм загрузки оборудования, а.процесса генерации расписания - на основе многомерных диаграмм Ганта (МДГ). Визуализация имитационного эксперимента осуществляется посрздством наложения МДГ реального процесса на ЩГ эталонного процесса, в качестве которого выступает расписание. Глава 4. В четвертой главе представлены примеры практического использования разраОогашшх моделей, методов и инструментальных. средств в решении задач исследования систем оперативного управления, опера гивного-калевдарного планирования и проектирования ГІІС. Приведен пример использования разработанных моделей и инструментальных средств в исследовании система управления робототехни-ческим комплексом (СУ РТК) изготовления печатных плат. Проанализированы этапы и построены процедуры исследования. Результатом исследования явилась разработка СУ РТК изготовления печами? плат, обеспечивающая повышение эффективности производственного процесса по сравнению с существующей СУ РТК, основанной на использовании статических правил приоритета. Продемонстрированы возможности применения разработанных моделей в решении задач оперативно-календарного планирования дискретных производств, где традиционные модели исследования операций оказываются малоэффективными. В качестве призера рассмотрена система поддержи принятия решений в оперативно-календарном планировании сборочно-сварочішх участков судокорпусного производства верфи, основанная на процедуро эвристического поиска в пространстве состояний. Продемонстрированы возможности применения разработанных подходов в решении задач проектирования технологических комплексов. В качестве примера рассмотрена система поддержки принятия решений при перепрофилировании промышленных предприятий, при разработке которой использованы методы решения задач назначешія деталеспера-ций на основе анализа t-инвариантов сети и поиска на дереве дости-гамости. Модель решения задачи назначения служит для оценки качественного состава основного технологического оборудования и является основой для определения его количествешюго состава. Модель оперативно-календарного планирования является основой для оценки проектного решения ТК с точки зрения возможности обеспечения задашшх критериев эффективности функционирования производственной системи. Опыт практического использования результатов диссертационной работа при решении задач исследования систем управления, проектирования, оперативно-календарного планировашія различных по структуре и динаміте производственных систем подтвердил эффективность разработанных моделей, методов и программных средств.Похожие диссертации на Разработка сетевых моделей и инструментальных средств для исследования систем оперативного управления ГПС
