автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Разработка и исследование продукционных графов операции как инструмента моделирования гибких производственных комплексов

ЁЯ' 0 ^ 9'?'

ОРДЕНА ЛЕНИНА ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ

На правах рукописи

ПОКАЛЕВ Станислав Сергеевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ПРОДУКЦИОННЫХ ГРАФОВ ОПЕРАЦИИ КАК ИНСТРУМЕНТА МОДЕЛИРОВАНИЯ ГИБКИХ . ПРОИЗВОДСТВЕННЫХ КОМПЛЕКСОВ.

Специальность 05.13.16

05.13.12

- Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях. Системы автоматизированного проектирования.

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата тех лческих наук .

¡ос к по - 1йп2г'.

Работа выполнена в Ордена Ленина Институте проблем управления

Научный руководитель: доктор технических наук

Юдицкий С.А.

Официальные оппоненты: доктор технических наук

Кульба В.В. кандидат технических наук Евсеев О.В.

Ведущее предприятие:

Московский инженерно- физический институт

Защита состоится с1 1992г. в , час,

на заседании специализированного совета.Д'002.68.оз Института проблем управления по адресу: 117^6.. Москва, Профсоюзная ул., 65.

С Диссертацией можно ознэкрмктся в библиотеке Института проблем управления.

Автореферат раскопан "25' 19Э2г,

Учений секретарь специализированного'совета, кандидат технических наук , ■ • '. "

Рласои С,А.: ' У/,

'Л '. - 3 -

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

• ■ Актуальность темы диссертации.

Рост эффективности современного автоматизированного производства достигается кап путем повышения его производительности, так и гибкости, включающей в себя возможность перестройки в кратчайшие сроки автоматизированного производства, п том числе его системы управления, при коренном изменении выпускаемой продукции.

Ядром управляющей системы любого дискретного автоматизированного производственного комплекса (единицы оборудования, модуля, линии, участка, цеха, завода) является система логического управления, функция которой состоит в обеспечении координации и •согласованного функционирования компонентов комплекса.

В условиях перехода'к рыночной экономике, связанного с неизбежным постоянным обновлением выпускаемой продукции и, как следствие , с повышением гибкости и степени автоматизации производства нессмяенка высокая актуальность создания научно-методических основ построения систем логического управления (СЛУ) гибкими производственными комплексами (ГПК). ;

В настоящее время в решении этой проблемы существует два направления. Первое из них заключается в привлечении для построе-

V.'

ния СЛУ проектировщиков-программистов и описании функционирования СЛУ на языках программирования высокого урогнз.

Эффективность этого способа построения СЛУ резко надает с ростом сложности СЛУ, т.к. при больших объема;: программирования существенно возрастает трудоемкость отладки и проверки правильности всего комплгкса программ гз целом, методы структурного программирования не гарантируют от ошибок, а методы доказательства правильности программ не учитывают специфики логического управления. Кроме того, созданное программное обеспечение, обраг.чо говоря, становится "секретом автора" и не доступно к-'арограммнрующнм пользователям, а его тиражирование с учетом возможных модификаций функционирования затруднено.

Второе направление спирается на формальные модели и методы, позволяющие строить наглядные и понятные пользователю »/.одели, адг-'.- ,л:чяо описывающие Функционирование СЛУ, $ориулигорпть сройст-вз э'Г!« моделей, отражающие правильное (корректное) повеление СЛУ, проводить анализ этих свойстз (анализ корректности) и выполнять реддизацк» моделей. при этом укзгзннуз иор.етм допеки Г'еть для отражений параллелизма и лерарху.к протекздаьи'л в ГПК

процессов, времени выполнения операций, а модели СЛУ ГПК уровня участка и выше, кроме того, должны иметь возможность описания зависимости уп^вления от материальных и информационных потоков, распределенногд характера СЛУ.

В рамках второго направления имеют место два подхода к построению распределенных СЛУ. В одном из них предусматривается раздельное описание компонент СЛУ и протоколов их взаимодействия, а также раздельный анализ как функционирования отдельных компонент СЛУ, так и их взаимодействий. Другой подход предусматривает описание и анализ Функционирования всей СЛУ в целом с последующей декомпозицией 'Этого описания в совокупность описаний функционирования отдельных компонент СЛУ в соответствии с их пространственным распределением и описаний пр токолов их взаимодействия.

Определить какой из двух подходов лучше сегодня но представляется возможным. Оба подхода имеют свои достоинства и недостатки. Сложность раздельного описания и, особенно, анализа функционирования компонент СЛУ существенно меньше сложности описания и анализа их совместного Функционирования. Однако, многие ошибки, выявляемое на этапе анализа взаимодействия компонент СЛУ, являются следствием неправильного функционирования отдельных компонент, что влече^ за собой повторные итерации анализа этих компонент и взаимодействий между компонентами всей системы. I! случае яе анализа описания'функционирования распределенной СЛУ в целом, последующая декомпозиция этого описания в совокупность описаний Функционирования отдельных компонент СЛУ гарантирует корректность цу. взаимодействия.

Известные в настоящее время модели: параллельппо гра^-ехгаш гпгорптяов, системы взаимосвязанных графов, продукционна спсхо-и.1, графн операций, сети Петри и их расширения недостаточно аКи-кчкикн дг.- реаеиья задачи построения СЛУ ГПК у>>о:;>и. уч<кн::л ; .

В ¡-•¿."•эте предлагаете, модель в ранках втою» .> к - •• /.• .: V; ¡г.илродолсшншс СЛУ, построенная на ох<: . . .•

• :•. к.-одукциошшх систем и названная • '

: . данная модель является разышюм п:»;/." . . . •. "■.

Цеььч? работы является сояданг.е формлимео .• ! • ••,>:•

ров;.нил СЛУ гпк уровня уч: -гка и цеха, оц.ои !•..•> >:.:• :. .• ; зоя-пилд нгирогр&ммкета, и целостной мою;г;,;п ......"

реализации моделей СЛУ ка основе единого формального аппарата, направленной на сокращение трудоемкости и сроков проектирования.

В соответствии с поставленой цель» в работе решаются следующие задачи:

1. Определение тапсг.-сй структурной организации ГПК, как иерархической с::сте>ш "•.т.ъъчпых" один в другой комплексов различного уробн:: .

2. Гсзрабстка 1ог!!'сльного аппарата продукционных графов операций для списгнпя Функционирования СЛУ ГПК, имеющего средства для адекватного отображения структурной организации ГПК, материальных и информационных производственной потеков, логической взаимосвязи и параллелизма операций, протекающих в ГПК, и их времени выполнения.

3. Исследовании продукционного графа операций и наиболее близких к нему моделзй среди расширений сетей Петри и продукционных систем.

1. Анализ ггзойств корректных дискретных производственных процессов и систем логического управления такими процессами, и разработка методов анализа продукционных ¡Трафов операций' на корректность .

5. Разработка методики декомпозиции продукционного графа операций с целью его последующей реализации в компонентах распределенной СЛУ ГПК.

Методы исследования базируются на применении аппарата теории множеств, сетей Петри, теории графов, математической логики, элементов теории алгоритмов и формальных систем.

Научная ноеизнз состоит в

- разработке формальной модели систем логического управления дискретными производственным!, системами - продукционного графа операций на основе обобщения известных.'моделей граф операций и продукционная система;

- исследовании двух классов моделей -модифицированных инги-биторннх сетей Петри и продукционных систем, эквй шентных классу продукционных графов операций, и создании алгоритмов построения из модели одного класса моделирующей ее повеление модели другого класса;

- определении свойств кор£ ктносги систем логического управления на оскспе свойств корректных производственных процессов,

урму'иг-ованм" этих свойств в терминах продукционных графов спо-

-г,

рация и разработке способов их анализа;

- разработке метода декомпозиции продукционного графа опера ций в систему взаимодействующих продукционных графов операций.

Практическая ценность работы заключается в создании комплек сной методики описания, анализа и реализации систем логического управления гибкими производственными комплексами уровня участков цехов на основе единого формального аппарата продукционных графо: операций.

Реализация результатов работы осуществлена при создании сис тем логического управления в СКБ точного литья (г. Тирасполь) и во ВНИИГидропривод (г. Харьков).

Апробация работы. Основные результаты работы докладывались 1 обсуждались на viii и х Всесоюзных семинарах "Параллельное программирование и высокопроизводительные системы" (Алушта, 1988 и Уфа, 19Э0), на vii Московской городской конференции молодых ученых и специалистов по проблемам кибернетики и вычислительной техники (Москва, 1939), на xxxv конференции молодых у">ных и специалистов ИПУ (Москва, 1989), на Международном семинаре ИФАК/ИМАКС "Автоматизация проектирования систем управления" (Алма-Ата, 1989), на xi Всесоюзном совещании по проблемам управления, (Ташкент, 1989).

Публикации. По теме диссертации опубликовано 7 печатных работ.

Структура и объем диссертации. Работа состоит из введения, пяти глав, заключения, списка литературы из 122 наименований, и приложения, содержащих доказательства утверждений, синтаксис языка Форком, пример описания на Ооркоме Функционирования СЛУ гибкой автоматизированной липли, полученную для него систему операторных формул и материалы, подтверждающие внедрение работы.

Объем диссертации: 169 стр. текста, 27 стр. рисунков и таблиц, список литературы на 13 стр„ и приложения на 41 стр.

- 7 -СОДЕРЖАНИЕ РАБОТЫ

Во введение обосновывается актуальность работы, формулируется ее цель и решаемые в ней задачи, характеризуется научная новизна и практическая ценность работы, дается краткое изложение по главам.

Первая глава представляет собой обзор логико - математических моделей дискретных производственных процессов.

Здесь рассмотрены пять групп моделей: системы массового обслуживания, параллельные граф-схемы алгоритмов, системы взаимосвязанных графов, продукционные системы, сети Петри и их расширения. Каждая группа состоит1 из нескольких классов моделей, отличающихся друг от друга теми или иными модификациями. При описании каждой группы моделей дается определение одного из классов, модели которого наиболее просты, но обладают основными характерными чертами моделей всей группы, рассматриваются основные понятия моделей, правила их функционирования, цели и методы проведения их анализа. Описываются особенности моделей остальных классов группы. Обсуждаются достоинства и недостатки каждого класса и группы моделей в целом с точки зрения их пригодности для построения СЛУ ГПК.

к.*

Системы массового обслуживания используются при проектировании ГПК на этапе эскизного предварительного,моделирования. Этот этап предшествует разработке СЛУ и предназначается для расчета производительности комплекса, объемов незавершенного производства, сбалансированности загрузки оборудования и т.п.

Результаты, полученные на этом этапе, являются исходными данными для этапа детального, алгоритмического моделирования, целью которого является построение алгоритмов функционирования моделируемых процессов. Для такого моделирования применяют модели остальных четырех групп, рассматриваемых в данной главе.

Моделирование с помощью систем взаимодействующих графов (СВГ) предполагает использование метода "снизу вверх", т.е. сначала выполняют описание отдельных процессов, а затем описание их вгаймодействий. Достоинствами СВГ являются их модульность и наличие автоматного подхода.

СВГ хороши для разработки СЛУ отдельными агрегатами или единицами оборудования. Но описание функционирования сложных систем, таких как СЛУ ГПК, предподчтительнее проводить методом "сверху

вниз", т.е. сначала в терминах наиболее крупных операций с последующей их детализацией на нижестоящих уровнях.

Параллельные граф-схемы алгоритмов (ПГСА) наглядны и просты в понимании. Они позволяют проводить описание сложных процессов методом "сверху вниз". Однако, ПГСА не отражают поведения систем в явной форме и не дают представление о внутренней логике функционирования СЛУ. Их существенным недостатком является и отсутствие методов анализа корректности моделей непосредственно по ПГСА и необходимость перехода для этого к сетям Петри.

Язык продукционных систем близок и естественен для пользователя. Метод организации вычислительных процессов с помощью продукционных систем выразителен и универсален, а модульный характер продукций обеспечивает простоту модификации моделей.

Однако, СЛУ сложными объектами, построенные на базе продукционных систем, обладают низким для реальных систем быстродействием вследствие медленного механизма выбора применимых продукций. Описание моделей сложных объектов-на языке продукции шых систем громоздко и ненаглядно, а методы анализа описаний с целью проверки их корректности отсутствуют.

Сети Петри удобны и выразительны при моделировании СЛУ. С их помощью просто представляются такие важные свойства, как логические взаимосвязи событий в системе, параллелизм, последовательность, альтернативность операций.

Классические сети Петри имеют развитый аппарат анализа. Однако, их моделирующие возможности недостаточны для описания реальных производственных систем, у них отсутствуют сродства для отрааения времени и иерархии процессов. А многочисленные расширения сетей Петри, обладающие достаточной моделирующей мощностью, имеют слабые разрешающие возможности (возможности аналитического исследования).

Т.о. сети Петри и СВГ, имея развитый аппарат анализа, предназначены в оснознсм для моделирования ГПК низшего уровня - единиц оборудования, роботизированных технологических комплексов, гибких производственных модулей. Для моделирования ГПК болоо высокого уровня '- участков, цехов их выразительнее возможности на-достаточны, получаемые при'этом модели имеют большую размерность, не наглядны и не адекватны, а трудоемкость их анализа, экспоненциально зависящая от размерности, велика. С другой стороны, у продукционны;; систем, ПГСА и расширений сстсй Петри, имеющих раз-

витые выразительные возможности для описания ГПК уровня участка и цеха, недостаточная разрешающая мощность, и основным методом для принятия решения на уровне моделей является имитационное' моделирование , весьма трудоемкое и не гарантирующее выявление всех "некорректностей" и узких мест. Отсутствие моделей с требуемыми качествами определило необходимость разработки нового формального аппарата.

В последнем параграфе первой главы подробно описываются сложные АП-сети Петри [Таль A.A., Юдицкий С.А. АиТ №7,9 1982], которые являются составной частью исследуемой в работе модели - продукционный граф операций.

Во второй главе рассматриваются структура и функционирование ■ гибких производственных комплексов (ГПК), дается формальное определение разработанной модели функционирования ГПК - продукционного графа операций (ПГО), приводится пример описания работы гибкой автоматизированной линии с помощью ПГО и излагаются общие рекомендации для построения модели функционирования ГПК.

Рассмотрим иерархию ГПК. Первый (низший) уровень составляют единицы автоматизированного оборудования - гибкие производственные модули (ГПМ) и роботизированные технологические комплексы (РТК). Второй уровень - группы взаимосвязанного автоматизирован-ного оборудования: гибкие автоматизированные линии (ГАЛ) и участки (ГАУ). Третий уровень составляют гибкие д^томатизированние цеха (ГАЦ). Введенное разбиение на уровни иерархии достаточно условно и в каждом конкретном случае один или несколько уровней могут быть разбиты на дополнительные подуровни, либо отсутствовать .

Структурная организация комплекса j-ro уровня (ГПК1) показана на рис.1. Комплекс состоит из объекта логического управления (ОЛУ3) и системы логического управления (СЛУ-1 ).

Объект управления представляет собой набор 'аналогичных комплексов, но более низкого j-1 -ого уровня (ГПК1"1). Для комплексов первого уровня "вложенными" в ОЛУ1 комплексами нулевого уровня являются отдельные рабочие органы ГПМ и РТК.

Систему логического управления составляют база дашшх (БД1 ) й бЪои. операций (B0J ).

База данных определяется конечными множестиями целочисленных неотрицательных переменных: временных vJ, ключей Gj , предметных ej , входных xJ и выходных zJ.

Входы от объекта управления х комплекса j-ro уровня являют-

ся внешними выходами комплексов j-i -го уровня z

■, 1 ■, и

выходы на объект управления представляют собой рнешние входы

. .х1"1. Кроме того, БД1 имеет

I , z

комплексов j-i -го уровня xJ~l!

В | 1 в , п

вход внешнего дискретного времени г.

Моделью Б01 является сеть Петри, позиции которой интерпретируются как выполняемые блоком операции, а переходы - как условия смены операций.

система логического объект логического

управления (СЛУ1). управления (ОЛУ1)

Рис. 1

Взаимодействие БО1 с БД1 отражается с'помощью нагрузки (пЬ-метки) переходов сети Петри продукциями - парами "условие, действие", где условием является логическая функция из множества и1 (х1, у'.е1 ), действием - подмножество операторов из множества 'о-1 (г^.Е''). Продукции записываются в виде условных предложений: если <условме>, то <действие>.

Моделью всей СЛУ,) является продукционный граф операций, который с одной стороны можно считать сетью Петри, переходы которой нагружены продукциями, а с другой - продукционной системой, порядок выполнения продукций в которой задан сетью Петри.

Формально, П1 , описывающий функционирование ГПК1- (далее индекс обозначающий уровень иерархии комплекса, будем опус-, кать), это набор ®=<В.р.а.р>. где

51 - ординарная сеть Петри;

¡р - продукционная система; ,

а - Функция, приписывающая переходам сети Петри переменные;

р - функция, "нагружающая" переходы сети Петри продукциями.

Ординарная сеть Петри - это набор Я=<Р,т,я.Ца >. где

р,т - конечные множества позиция и переходов соответственно;

Я: r»TtjT«p-{o, 1) - Функция инцидентности;

ц : Р->(0,1J - начальная маркировка, "о

Продукционная система - это набор |)=<w,a",a* ,и,о,п>, где w=xUzUeUvUg - конечноеj<Ho*e£TBo_nepeMeHHUx соответственно входных, выходных, предметных, временных и ключей временных переменных ;

А* =(аЦиГГ{Х72 - множество входных алфавитов, где ал^чвит 1-го входа есть а* = {571^ }; 1

a" =(a*|i=T7JZ|2. 1 множество внходных_алфавитовл где алфавит i-ro выхода есть я'=(О,k*J; V-{0} G-{0,1)

<р : E-N - начальное состояние

z^lTSTb]), i^l^.ZjCZ r

переменных^ N - множество натуральных чисел (вклвчая ноль); и - множество условий, которые определим рекурсивно:

1) 1 есть условие;

2) если w (XIIVII К, w .;\IJVIIl'(IN, TO w <w , w >w , w .<w ,

w Jw , н =w , w iv - УСЛОВИЯ;

1*2 1 2 12 _

3) если u условие, то u - условие;

4) если u ,иг - условия, то ui «u? , ",ли2 - условия;

5) если hcHGXl.lvUE и u(h) - условие то Vh(u(h)), 3h(u(h)) - условия. Интерпретация этих выражений следующая:

Vh(u(h)> - для лпбой переменной h из подмножества ti условие u(h) - истинно; ,

2Ь(ч(Ы) - существует переменная Ьсн, такая что условие ч(Ы - истинно;

o=^oj_q2S'iiQ=?l,GUE}_-_HHo«ecTBo_onepaTopoB присваивания новых значений переменным, имеющих виц: ' у((0,1], если kg 1-у, где , если 1=2^2

1 yiNlJEU[e + e' ,е-е'}, если q( Е здесь e,e'(EUH;

е+е" - функция сложения значений переменных е. и е'; е-е' - неотрицательная функция вычитания переменных, при

', совпадающая с обычной функцией вычитания к равная нули при

е<е * ;

к - множество продукций, нагружающих переходы в соответствии с функцией т-я. Продукция, нагружающая переход гет, имеет

ВИД:

Р С й) = (если и, ТО (о(д4 ),о(ч4 )|...,о(ч1 ))), где и?и, {о^ )|п=Т7Е)со, |п=Т7Е}=аи). .

п п

а: т-2ч - введенная ранее функция, приписывающая переходам сети Петри переменные из множества ч=гис1)Е (2Ч - множество всех подмножеств множества ч, включающее пустое множество и само о).

Состоянием ПГО называется функщ..; о:

g-.tO.lJ

х4-{ОТЕ" } , 1=Т7РП",Х1

Переход ПГО может сработать в состоянии а, если во всех его . входных позициях присутствуют метки, и условие продукции, нагружающей переход, истинно.

Срабатывание перехода заключается в изъятии из каждой его входной позиции и внесении в каждую его выходную позиции по метке, и последовательном вычислении операторов продукции, нагру.сав-щей этот переход.

Поступление сигналов по входам и передача по выходам допускается только в устойчивых состояниях ПГО, т.е. когда ни один переход не могет сработать. При поступлнении сигнала по одному из входов, кроме временного, значение входной переменной, соответствующей этому входу, устанавливается равным значению поступиввего сигнала. При наступлении очередного такта внесшего дискретного времени (поступление сигнала по временному входа) увеличиваются на единицу сначения временных переменны. , ключи которых равны "'-'■, единице. При нулевых ключах значения соответствующих им временных неременных равны нуль. В ,стойчивых состояниях по ваходам переда -ьтся сигналы, равные значениям соответствующих им выходных пере-

ИЭШ'ЫУ..

Для описания иерархии процессов, протекающих в ГПК, используется представление базовой сети Петри ПГО в виде слоеной АЛ-сети Петря . При этой процесс в целом описывается в виде совокупности ПГО, находящихся в отношении иерархии в виде дерева, ниже-

стоящие ПГО представляют собой детализированное описание отдельных операций (позиций) ПГО, непосредственно предшествующих им по дереву иерархии, а взаимодействие различных ПГО осуществляется путем синхронизации срабатываний их переходов.

Использование сети Петри для описания логической взаимосвязи операций моделируемого процесса, а продукций - для описания сущности этих операций делает ПГО наглядным и выразительным. ПГО имеет средства для отражения времени протекания операций и их иерархии, материальных и информационных потоков. А описание сложных СЛУ с помощью ПГО предполагает использование свойственного человеку метода "Сверху вниз".

В третьей главе рассматриваются классы чисто сетевых и чисто продукционных моделей СЛУ ГПК в сравнении с классом ПГО. Все эти классы эквивалентны друг другу по моделирующим возможностям. Различия между ними состоят в удобстве моделирования (составлении описаний) и методах проведения анализа.

Здесь формулируются понятие моделируемости одной модели другой моделью, а также понятия моделируемости и эквивалентности различных классов моделей, дается формальное определение классов модифицированных ингибиторных сетей Петри (ИСП) и продукционных систем (ПС), эквивалентных классу ПГО. Для трех указанных классов рассматриваются алгоритмы построения моделей одного класса, моделирующих модели другого класса. Доказывается утверждение об эквивалентности классов ПГО, продукционных систем и модифицированных ингибиторных сетей Петри.

Отличия модифицированных ингибиторных сетей Петри от обычных ингибиторных сетей Петри полностью определяется необходимостью отражения входов и выходов СЛУ согласно структурной организации ГПК (рис.1).

Кроме обычных позиций здесь введены входные, выходные и временная позиции для отражения состояний входов и выходов СЛУ. Маркировка входных и временной позиций меняется как при срабатывании переходов так и при поступлении сигналов по входам. Поступление входнь-х и выдача выходных сигналов разрешается только в устойчи-шх состояниях, т.е. когда ни один переход сети не может сработать. При поступлении сигнала по одному из входов (кроме временного) маркировка входной позиц..л, соответствующей этому входу, устанавливается равной численному значению поступившего сигнала. При поступлении сигнала по временному входу (при наступлении оче-

редкого такта времени) маркировка временной позиции увеличивается на единицу. На выходы системы поступает сигналы,численно равные маркировке выходных позиций, соответствующих этим выходам.

Формальное определение продукционной системы было дано при формальном определении ПГО. ПС Функционирует подобно ПГО с учетом отсутствия дополнительного условия возбуждения для выполнения продукций - наличия меток во всех входных позициях перехода, соответствующего этой продукции.

Первичными понятиями при определении моделируемости и эквивалентности классов моделей СЛУ ГПК являются понятия: событие, элемент состояния и состояние модели.

События могут быть внешними (наблюдаемыми) - поступления сигналов по входам СЛУ, и внутренними. Внутренними событиями для ПГО и ИСП являются срабатывания переходов, а для ПС - выполнения продукций.

Состояние модели - это функция, отображающая множество элементов состояния во множество натуральных чисел, включая ноль. Элементами состояния для ИСП являются позиции, для ПС - переменные, а для ПГО - позиции и переменные.

Траектория моде/ - это последовательность пар (состояние, событие), начинающееся парой с начальным состоянием, в которой для любых двух соседних пар (с4с ), <0141с141) событие с4 может произойти в состоянии 01 , а при его наступлении модель из состояния о1 переходит в состояние •

Поведение модели - это множество всех ее траекторий.

Существенными событиями и элементами'состояния назовем инте-' ресующие нас события и элементы состояния.

Существенным состоянием модели назовем проекцию состояния модели на множество существенных элементов состояния.

Существенное поведение образуется кс поведения модели вычеркиванием в каждой траектории всех пар с несущественными событиями и заменой состояний соотв "сть.лщими существенными состояниями в оставшихся парах.

Модель к1 моделирует модель кг (обозначается к ¡»к ); если ногно взаимно однознано сопоставить элементы множестз существен-них событий и существенных элементов состояния модели к с элементами множеств событий и элементов состояния модели к2 соответственно , так что после замены в существенном поведении модели к ' событий и элементов состояния на сопоставленные им события и эле-

менты состояния модели кг получится поведение модели к2.

Класс моделей моделирует класс моделей К2 (записывается

К »К ), если Ук £К Вк £К : к »к .

12 2 2 1 1 1 2

Класс моделей К1 эквивалентен классу моделей (записывается к «к ), если (к »к )л(к »к ).

1 2 1 2 2 1

Для классов ПГО, ИСП и ПС разработаны алгоритмы построения моделей одного класса, моделирующих модели другого класса. В частности показано, как с помощью ИСП можно промоделировать вычисление условий ПГО, т.е. вычисление истинности предикатов со счетной областью значений переменных, и вычисление операторов ПГО - арифметических операций и операции присваивания. Доказано утверждение об эквивалентности'трех указанных классов чоделей, и рассмотрены возможные варианты использования полученных здесь результатов с целью анализа моделей и их реализации. Например, наличие эффективных средств реализации ПС может быть использовано для оеализации моделей, описания которых выполнены на языках ПГО и ИСП, после перевода их в ПС и т.п.

Четвертая глава посвящена анализу ПГО, целью проведения которого являьгся проверка правильности (корректности) функционирования моделируемых СЛУ. В этой главе вводится понятие корректный ПГО, формулируются свойства корректных ПГО, и рассматривается методика анализа корректности ПГО.

Свойства корректных производственных процессов определяют свойства СЛУ такими процессами.

Опишем свойства корректных дискретных производственных процессов :

1. Операции процесса не начинаются вновь до их завершения.

2. Параллельные процессы функционируют независимо друг от друга и связаны только своим началом и завершением. По другому это свойство можно сформулировать как отсутствие операцн , одновременно обращающихся к общему ресурсу.

3. Порядок выполнения операций, не являющихся параллельными, определен, в том смысле, что при наличии возможности запуска нескольких операций определен механизм выбора запускаемой операции.

4. Отсутствуют операции, которые никогда не выполняются.

5. Процессы обладают свойством повторяемости, другими словами исходное состояние процессов достижимо из любого состояния.

Сформулируем теперь свойства СЛУ, которые (кроме последнего) являются отражением свойств корректных процессов. Их номерация

совпадает с номерацией соответствующих им свойств процессов, за исключением свойств 5 и б, которые являются отражением свойства 5 процессов.

1. Безопасность сети Петри, лежащей в основе ЛГО (позиции сети Петри интерпретируются как операции процесса).

2. Непротиворечивость ПГО: ■■

- входные переменные, входящие в условие одного параллельного перехода, отсутствуют в условии другого параллельного перехода;

- переменные, значения которых изменяются операторами одного параллельного перехода, отсутствуют в продукции другого параллельного перехода.

3. Детерминированность (с точностью до параллелизма) - ортогональность условий альтернативных переходов.

4. Безызбыточность - отсутствие "мертвых" (никогда незапус-каемых) переходов. '

5. Восстанавливаемость - из-любого состояния, "*,остижимого из начального состояния, достижимо такое состояние, что проекция этого и начального состояний на множество всех позиций и переменных, кроме внешних входных и внешних выходных переменных, совпадают .

Заметим, что из восстанавливаемости ПГО не следует живость его сети Петри, так же как из живости сети Петри ПГО не следует восстанавливаемость этого ПГО. Но случаи, когда у восстанавливаемого ПГО сеть Петри не жива, не типичны. Поэтому потребуем, чтобы ПГО обладали следующим свойством.

6. Хивость сети Петри, лежащей в основе ПГО.

Кроме того, в СЛУ переходной процесс, наступающий после поступления входного сигнала, завершается за конечное число шагов. Отсюда следует свойство:

7. Устойчивость - достижимость устойчивого состояния из любого состояния, достижимого из начального состояния.

Модели СЛУ ГПК, обладающие семью указанными свойствами, будем считать корректными.

Опишем метомйку анализа корректности ПГО.

Анализ безопасности й живости сети Петри, лежащей в основе ПГО, выполняется путем нормализации (редукции) - выделения из сети корректных с точки зрения живости и безопасности подсетей -А- и П-блоков (автоматных блоков и блоков с параллелизмом) и за-

мены их позициями-дублерами. Анализ живости и безопасности сети, оставшейся после редукции, проводится по ее графу достижимых маркировок .

Анализ непротиворечивости ПГО состоит в поиске параллельных переходов и в проверке их непротиворечивости. При поиске параллельных переходов такле эффективна процедура нормализации.

Анализ детерминированности ПГО, т.е. ортогональности условий альтернативных переходов, проводится извеитным методом резолюций. При этом специфика условий ПГО - ограниченность переменных, связанных кванторами, позволила применить модифицированный метод резолюций с упроченной процедурой гывода, позбзляещий за конечное число изгов установить противоречиво выражение илч нет.

Анализ восстанавливаемости. бесизбнточности и устойчивости ПГО может быть проведен по графу состояний (ГС) ПГО. ГС представляет собой ориентированный граф, верпины которого взаимно сдпознано сопоставлены состояниям ПГО, достижимым из начального, а дуг* однозначно сопоставлены событиям, при наступлзшш которых происходит переход яз состояния в состояние.

В этой главе излагается методика построения ГС ПГО и рассматривается подкласс хорсло сформированных ПГО, для кого;;»:; ГС конечен, доказывается соответствующее утверждение.

Однако, сложность построенлл ГС зкспсне;щиаяи1з. ¡1 при боль-сой размерности модели, свойственной исдехг- .СХ/ реальны:: производственных объектов, проведение такого анализа представляет значительные трудности.

Б этих условиях, анализ указанных свойств целесообразно проводить методом редукции, состоящем в замене позициями коргектних с точки зрения вссстакавлизаемости, безызбыточности и устойчивости подграфов ПГО.

Если редукция проходит не до конца, то анализ восстанавливаемости, безызбыточности и устойчивости остатка - нереяуцирсемого более подграфа ПГО, проверится по его графу состояний.

При этой слогность анализа остатка редукции с/^г-ственно меньше сложности анализа исходного ПГО вследствие ченьагД р^'-мерности остатка, т.к. в нем отсутствуют пезиц!;;- и периоды редУчИ-роь?.|'пъ1Х подграфов и переменные, не входящие !> продукции остатка.

Разработанный метод редукции ПГО состоит в гау-ене погицийчк подграфов на основе А- и Л-блоков базовой сет;; Петри !!Г0 (автоматныхйтокоз и блоков с Параллелизме:;!) с определенны*1,: ограничь-

нияни на продукции их переходов,.гарантирующими отсутствие в эти подграфах некорректностей, ведущих к невосстанавливаемости и неустойчивости ПГО, и в корректировании операторов продукций выход] ных переходов этих позиций.

К неустойчивости ПГО может привести наличие в подграфах прс стых циклов и путей от источников до стоков этих подграфов, при выполнении которых не достигается устойчивое состояние (назовем их неустойчивыми путями и циклами), некорректности, ведущие к невосстанавливаемости начального состояния ПГО, можно разбить нг некорректности, ведущие к невосстанавливаемости начальной маркировки, (будем называть их тупиками) и некорректности, ведущие к невосстанавливаемости начальных значений переменных, кроме внешних входных и внешних выходных переменных.

Идея предлагаемого метода состоит в редукции подграфов, на! рузка которых гарантирует отсутствие в них неустойчивых путей и циклов, тупиков и возможность определения значений переменных,* изменяемых при функционировании этого подграфа, при достижении его начальной маркировки. При этом значения переменных, изменяв мых продукциями только данного подграфа, должны быть равны знач ниям этих переменных в начальном состоянии, а значения остальны: переменных присваиваются этим переменным операторами, доб~вленн ми в продукции стоков данного подграфа.

Такие подграфы называются редуцируемыми. Дается их формаль ное определение, излагаются ограничения на продукции и условия нагружения ими переходов подграфов, достаточные длл идентификац их редуцируемости, и приводится методика проведения редукции ПГ

В пятой главе рассматривается реализация СЛУ ГПК в виде ра пределенной системы, организованной по принципу локальной вычис лнтельной сети (ЛЕС), состоящей из ряда взаимосвязанных подсистем. Каждая подсистема СЛУ ГПК представляет собо вычислительна машину или ЛВС .более низкого уговня, в соответствии со структур ной организацией ГПК (см.рис.1). В своя очередь, рассматриваем СЛУ ГПК может быть подсистемой ЛВС более высокого уровня.

Алгоритм функционирования распределенной СЛУ определяется алгоритма1"- функционирования отдельных подсистем и протоколами информационных взаимодействий между ними.

В этой глэзе:

- олр?деляется модель распределенной СЛУ, организовакгг'П г принципу локальней вычислительной С'зти, - система озаимодейстБ:,