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

?ГЗ 0.1

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

ИВАНОВ Николай Николаевич

УДК 519.711.3

МЕТОДОЛОГИЯ АНАЛИЗА ВРЕМЕННЫХ СТОХАСТИЧЕСКИХ СЕТЕЙ ПЕТРИ И ЕЕ ИСПОЛЬЗОВАНИЕ ПРИ ИССЛЕДОВАНИИ И МОДЕЛИРОВАНИИ ДИСКРЕТНЫХ СИСТЕМ

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора технических наук

МОСКВА - 1997 г.

Работа выполнена в Институте проблем управления РАН

Научный консультант д.т.н., проф. Бочаров П.И.

* Официальные оппоненты:

доктор технических наук, профессор Овчаров Л.А.

доктор физико-математических наук, профессор Печинккн A.B.

доктор технических наук, профессор Литвин В.П.

Ведущая организация - Институт проблем передачи информации РАН, г.Москва

Зашита состоится -Зо" 4tfc>kd 1997 г. в часов на заседании диссертационного совета № S (Д002.68.03) Института проблем управления РАН по адресу: Москва, 117806, Профсоюзная ул. 65.

Телефон совета: 334-93-29.

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

Автореферат разослан J997 г.

Ученый секретарь диссертационного совета k.tji.. с.н.с.

С. А. Власов

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

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

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

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

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

кого исследования, и разработка методики этого исследования, обеспечивавшего наименьшие стоимостные и временные затраты на моделирование.

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

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

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

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

Яг'.^ггтл-л ?!ов»'вга диссертации заключается в разработке и математическом обоснсзг.нии коютлекса нозых методов аналитического исследования ВССП с произвольными закопают распределения случайного оремони срабатывания переходов.

Прчгттггэсзсзя цеяпсст?. раСэти. Методы, представленные а диссертации, позволяет научно обоснованно, с высокой точностью и с минимальными затратами решать задачи исследования и анализа моделей процессов, построенных на базе ВССП, что особенно важно для начальных этапов проектирования дискрет-1глх оСектов. Эти методы, являясь инструментом аналитического исследования ВССП обгаего вида, призваны также служить математической поддерткой имитационного подхода к исследовании ВССП, поскольку только развитый теоретический фундамент позволяет избегать методические ошибки в имитационном эксперименте и построить для такового обоснованную стратегия. Для ряда валгыгх практических задач моделирования дис-кретних процессов показано, как может быть применена методология анализа ВССП, предложенная в работе, для получения характеристик этих процессов.

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

р&йу.гчтптеэ рпЗети. Методы анализа ВССП, разработанные в диссертац!31, нашли применение в ряде практических разработок, проведенных под руководством автора:

- в ЛО "Москвич" на зтапе разработки технического задания на проектирование подсистемы оперативного управления цехом сварки автомобильных кузовов;

- в НПО "Казсельхозмеханизация" при разработке подсистем АСУ сельскохозяйственного предприятия в части создания моделей, методов планирования и оперативного управления грузовыми перевозками сельскохозяйственной продукции на типовом с/х предприятии, а также при моделировании процессов переработки сельскохозяйственной продукции, поступатеей на крупные перерабатьгаапвие предприятия.

АппроЗсцил рвботи. Основные положения и результаты работы докладывались на следующих семинарах, школах и сиьшозиумах:

- Международный семинар ученых стран-членов СЭВ "Разработка общей теории автоматов" (Суздаль, 1985 г.);

- 10-й Международный Симпозиум по вычислительной технике и информатике (13013 X, Турция, 1995 г.);

- XXXV Школа-сей&ар по теории релейных устройств и конечных автоматов иы. М.А.Гаврилова (Москва, 1Э96 г.);

- Общемосковский семинар по логическому моделированию (Носква, 1996 г.);

- IV Международная Конференция "Проблемы управления в чрезвычайных ситуациях (Косква, 1997 г.);

- Научный семинар кафедры теории вероятностей и математической статистики Российского Университета Дружбы Народов (Москва, 1996, 1997 г.г.),

а также на ряде других семинаров и совещаний.

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

Структура и обоек работы. Диссертация состоит из введения, семи глав, заключения и списка литературы. Общий объем работы составляет 241 стр. машинописного текста, 41 рисунок, 9 таблиц. Список литературы содержит 126 работ.

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

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

В главе 1 приводятся некоторые примеры применения ВССП при моделировании дискретных процессов, на которых можно судить об универсальности этого инструментального средства и его изобразительных возможностях. Здесь же проводится обзор различных типов ВССП и аналитических методов их исследования.

В классической интерпретации механизма функционирования сети Петри при существовании в некоторой достижимой разметке нескольких возбужденных переходов выбор (единс-

тройного) перехода, когорт в данной разметке должен сработать, никак не регламентируется. Таким образом, поведение сети Петри в обаем случае имеет недетерминированный характер, в котором отражаются лишь причинно-следственные связи между СС0Ч1ИЯНИ, моделируемыми срабатыванием отдельных пер-зходоп.

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

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

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

Расширение моделирукдих возможностей ВССП было достигнуто допущением в ВССП мгновенных переходов с временем срабатывания, равным нулю. Соответствующий класс ВССП был назван классом сбоценных ВССП (generalized stochastic Petri nets, GSPN). В GSPN в случае одновременного возбуждения мгновенных и временных переходов в первую очередь срабатывают мгновенные переходы, при этом, если таковых больше одного, то порядок срабатывания определяется в соответствии с заданными вероятностями. Временные переходи в таких ВССП имеют экспоненциально распределенное время срабатывания, параметры которых, вообще говоря, могут зависеть от числа комплектов меток, гающихся в позициях-предшественниках и необходимых лля срабатывания этих переходов. Однако, в вычислительном апано эти сети не отличаются от экспоиенциаль-

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

Следующим шагом в развитии аппарата ВССП явилось введение так называемых расширенных ВССП (extended stochaatic Petri nets, ES PN или semi-Markov SPN's - SM-SPK's). В этих сетях допустимо было вводить временные переходы с временем срабатывания с произвольной функцией распределения в двух возможных в этом классе ВССП случаях: 1) при возбуждении такого перехода ни один другой переход не может быть возбужден, .2) если одновременно возбуждено несколько таких переходов, то срабатывание одного из них влечет за собой исчезновение условий возбуждения остальных. При анализе ESPN случайный процесс смен разметок можно было моделировать полумарковским процессом с фазовым пространством, представляющим собой множество достижимых разметок.

Рассматривались сети, имеющие переходы с экспоненциальным и детерминированным законами распределения времени срабатывания переходов (deterministic and stochastic Petri nets - DSPN). В ВССП этого класса е каждой достижимой раз- . метке допускается не более одного возбужденного перехода с постоянным временем срабатывания. Случайный процесс, моделирующий смену разметок в ВССП этого класса, может бить отнесен х типу однородных цепей Маркова с .полумарковским" вмешательством случая.

. Сравнительно недавно класс 0SPN был расширен (extended DSPN's). В сетях этого класса в отличие от сетей DSPN неэкспоненциальный переход может иметь любое распределение времени срабатывания (в том числе и детерминированное). Ограничения на дисциплину возбуждения неэкспоненциальных переходов переносятся полностью из класса DSPN. Случайный процесс в сетях этого класса TaLioce может быть отнесен к типу однородных цепей Маркова с полумарковским вмешательством случая.

Одновременно с классом расширенных DSPIJ был введен класс марковских регенерируюеих-ВССП (class of Markov regenerative SfN's, MR-J>PN's), который оказался эквивалентным классу расширенных DSPN.

\ Таким . o6p*:«cid, : вопрос о возможности анализа ВССП с произвольны»;'! распределениями времени срабатывания переходов без каких-либо ограничений на дисциплину возбуждения и

6 . V;'

срабатывания переходов в больной степени оставался открытым.

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

Наряду с основной, возникали также попутные проблем« (имегсдее, вообще говоря, и самостоятельное значение), связанные в первую очередь с методам! обнаружения достижимых тупиковых раз!?еток, которые в случайном процессе смен разметок могли играть роль поглощагзяих состояний. Выявление тупиксаых разметок может быть проведено путем построения графа разметок, однако для сетей Петри с запрещающими дугами алгоритмически неразрешима проблема ограниченности сети.• Тагам образом для произвольно заданной сети с запрещагииыи дугами алгоритм обнаружения тупиковых разметок не должен быть ориентирован на граф' разметок. Кроме того обнаружение таких рагкоток является желательным до проведения анализа случайного процесса в ВССП, а также в тех случаях, когда таковой становится невоэмо~т.ннм (например, при неограниченности г.срсздалздей ВССП сети Петри) и возникает необходимость проведения имитационных экспериментов с целью выявления предельных распределений вероятностей достижимых разметок. Известны некоторые алгебраические методы обнаружении тупиковых разметок липь для сетей Петри без запрещали« дуг. Тлхнм образом весьма актуальна задача выявления конструктивно проверяемых достаточных условий существования тупиковых разметок для сетей Петри с запретами.

Кроме того, для неограниченных ВССП, анализ которых невозможен из-за счетности фазового пространства иоделмру-

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

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

. Лишь в начале 90-х годов в научной литературе появились первые публикации по актуальной проблематике анализа произвйльных ВССП, в которых предлагалось решение поставленной задачи находить Средствами теории регенерирующих случайных процессов. Было введено понятие полурегенерирующих ВССП (semi-regenerative SPN's - SR-SPN's).. Эволюция ■ процесса смен разметок в сетях, этого класса между моментами регенерации не может быть описана случайным марковским процессом с непрерывным временем, как это было возможно для сетей классов MR-SPN и расширенных DSPN.

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

: Функционирование ВССП описывается ступенчатым случайным процессом tj { х ) с дискретным фазовым пространством К.

■ Необходимой компонентой состояния процесса J1 е X является разметка сети М, которая, вообще говоря, меняется при скачкообразном изменении состояния процесса.

В случае, если послё попадания ВССП в момент х в разметку М1 в последней сохранил состояние возбуждения . переход tj с неэкспоненциальной функцией распределения времени срабатывания, возбудившийся в момент времен*! Xj < х, то марковское свойство для процесса ц {х ) не выполняется, поскольку переходные вероятности процесса г/ ( х ) в этом случае будут зависеть по крайней мере от того, сколько времени ВССП находилась в разметке Мк, из которой £>н<1 перешла в разметку Ni в результате скачка, вызванного срабатыванием некоторого перехода t: * tj.

Основная идея, лежащая в основе подхода автора и пол-fcofla, применяемого при анализе SR-SPN, предполагав1; наличие

е . -

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

При анализе БИ-БРИ предполагается, что между моментами регенерации в ВССП находится в состоянии возбуждения один переход, который назван регенерирующим. По определению, регенерирующим называется неэкспоненциальный переход t, если для остальных нсэкспоненциальных переходов выполняются следующие условия: 1) для всех переходов, возбужденных одновременно с переходом Ь, в момент появления условий возбу-. ждения перехода t начинается отсчет времени их срабатывания, 2) в момент срабатывания или потери условий возбуждения перехода t все возбужденные с ним одновременно переходи теряют условия возбуждения.

Если ввести понятие Эь - множества достижимых разметок, в которых возбужден некоторый переход Ь, то ВССП в соответствии с определением называется полурегенерирующей, если существует множество регенерирующих переходов Тк, такое что { ] 1 е Тя] и множество разметок 5г, в которых возбуждены только экспоненциальные переходы, образуют разбиение 5 - множества всех достижимых в ВССП разметок.

В настоящей работе рассматривается более общий класс ВССП, обладакетх свойством регенерации, отличающийся тем, что не требуется выделение множества регенерирующих переходов с целью проверки выполнения определения БЯ-ЗР!*. Рассматривается так называемые ВССП с ограниченной предысторией, харак'.'еризучмие тем, что во всех возможных траекториях через конечное число скачков (смен разметок) с необходимостью появляются разметки, в которых>либо возбуждены только экспоненциальные переходы, либо у всех неэкспоненциальных переходов начинается отсчет времени их - срабатывания. Моменты появления таких разметок представляют собой моменты регенерат:», при наступлении которых ВССП полностью забывает свое прошлое, и ее будущие траектории определяются лишь ее разметкой в момент регенерации.

Проверка принадлежности ВССП классу ВССП с ограниченной предысторией.осуществляется конструктивно путем постро-

ения некоторого множества в двоичном алфавите (0, 1} и его описания на специальном языке, известном под названием языка эквивалентных преобразований (ЯЭП).

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

Отталкиваясь от графа достижимых разметок 6 •ограниченной ВССП, построим для нее вспомогательный ^раф G' по следующему правилу: разметки регенерации соединим мевду собой непересекающимися путями, на которых разместим только обыкновенные разметки, при этом, возможно, размножая их в необходимых случаях и присваивая им некоторые дополнительные индексы (предполагается, что на таких путях нет циклов) . Каждый такой путь назовем обыкновенным. Таким образом, если из некоторой разметки регенерации iJj на графе С ведет обыкновенный путь L в разметку М j, то ни в одну обыкновенную разметку . М, имеющуюся на этом пути, не ведет какое-либо начало обыкновенного пути, начинаюсегося из другой разметки регенерации Мк. Однако при этоы возможны ситуации, когда некоторые обыкновенные пути имеют общее начало.

Множество S' всех разметок графа G' будем рассматривать в качестве пространства состояний случайного процесса (^(х),/'(х)), в котором компонента у (х) имеет фазовое пространство И, состоящее из всех разметок регенерации, а компонента £ ( х) имеет таковым множество S' всех разметок графа G'. Пока компонента у ( х ) сохраняет свое состояние неизменным, компонента £ ( *) меж-т пробегать некоторое множество промежуточных состоянии (размоток) до переключения компоненты у {х ) в следующеее состояние регенерации. При этом компонента у (х) представляет собой полумарковский процесс, поскольку вероятности переключения у (х) из одного состояния о другое, а также время "сидения" в состоянии регенерации на зависят от предудукей эволюции и определяются лишь текущим состоянием регенерации.

Рассмотрим теперь случайный процесс с полуыарковскими ' переключениями (СППМП) tf(x) = ({(x),y(x),{(x)). Б нем первые две компоненты имеют прежний смысл, а третья (сопровождающая) - С (х) - представляет собой время, проведшее с момента последнего скачка компоненты у ( х ): ( { х ) = х -

" г1-(х) ' ГП = Х1 + ... + -Хп , л = О , 1 ,..., у ( X ) = гоах ( п : т„ £ <, х), где xi г 1 = 0, 1,..., - время "сидения" ПМП у{х) в некотором состоянии между (1-1)-м и 1-й скачками. Таким образом, СППКП 7} (х) принимает значения из множества Б' х я х [ 0, ю), в котором 5' представляет собой (конечное) множество достизимых разметок 5, в общем случае содержащее некоториа разметки вместе со своими "дубликатами".

Для СПЯМП 7 ( х ) марковское свойство выполняется только п моменты регенерации (т.е. в моменты тл) и поэтому в общем случае !]{>:) не является марковским, однако двумерный случайный ^процесс ( у (х ), С ( х)) представляет собой однородный марковский процесс. Нахождение переходных вероятностей этого процесса (выражающихся в явном виде с помощью уравнений восстановления через полумаркозское ядро 0(х) = 1,3 г Я, ПМП у(х)) в рассматриваемом

случае связано с больппши вычислительными трудностями. Однако, для ретления задач, связанных с нахождением предельного распределения «сролтностей доститзялых разметок мозаю обойтись достаточно прост>.з.с1 средствами.

Выделяя на графе G' только состояния регенерации (множество состояний Я), можно построить вложенную в ПМП у (х) цепь Маркова, переходные вероятности которой определяются без привлечения полумарковского ядра. Эти вероятности могут £:ггь определены на основе вероятностного анализа функций рзопределения времени срабатывания переходов и рассмотрения функции распределения разностей случайных величин времени срабатывания одновременно возбужденных переходов.

Рассмотрим некоторое состояние регенерации э е Н . Оно является также состоянием основной компонеты £ ( х ): з е 5'. Время преСывания основной компоненты в состоя'ши э мс.г^т быть определено как математическое ожидание случайного Еремени /л { з), распределенного по закону минимума случайных времен срабатывания всех возбужденных в состоянии з переходов. Uoyr.no определить также вероятности р ( я , б' ), р ( э , е" ),..., с которыми основная компонента £ (х) переключается из состояния з в состояния з' , з", ... за один шаг.

Рассмотрим теперь состояние з' е Э', в которое основная компонента за один шаг попадает из состояния з. В этом состоянии существуют неэкспоненциальные переходы, у которых

отсчет случайного времени их срабатывания начался в состоянии s. Закон распределения системы случайных величин этого времени в состоянии s' зависит от того, какое время (г) основная компонента провела в состоянии s, и, следовательно, это распределение является условным и может быть записано как F ( xlf х2, ...|г). Соответственно с этим время пребывания основной компоненты в состоянии s' также будет представлять собой условное математическое ожидание относительно г минимума системы случайных величин остаточного времени срабатывания возбужденных в состоянии s' переходов; fjfls') = M ( fi ( s' ) | г ). Если переход из состояния s в состояние s' произошел в результате срабатывания некоторого перехода t с функцией распределения времени срабатывания Ft (х), порождающей вероятностную меру vt (х), то среднее

по процессу значение /j(s' ) может быть определено как 00

Mis') = Jm {fi (s')| T) yt (cfr). 0

Аналогичным образом могут быть определены средние по процессу переходные вероятности из состояния s' в некоторое состояние s" за один шаг. Продолжая эти рассуждения, можно таким образом для каждого состояния регенерации s построить переходные вероятности и средние времена пребывания для всех простых состояний основной компоненты, находящихся на простых путях, связывающих s с другими состояниями регенерации. Это, с одной стороны, дает возможность вычислить переходные вероятности вложенной в ПМП у ( х ) цепи Маркова J , и, с другой стороны, позволяет воспользоваться известными из теории СППМП эргодическими теоремами в среднем для процессов накопления с полумарковскими переключениями (ПНПМП). В нашем случ'ае под ПНПМП аА (х, 17 ( ■ ) ) понимается доля времени, проведенная случайны:«! процессом г] ( х ) в состоянии А € S' х Ц х [ 0, œ ) в промежутке времени [ О, х ] :

х

a A U, »7 ('•■)) = J JT аС »7 ( У ) ) cfy , xâO,

•; . •'-- о ' •

где »7 (у)) - характеристическая функция состояния А.

К*к известно,

. Мад( х )

lim -— = лг ( А ), •

Я ю . - X

где я ( А) - стационарное распределение случайного процесса т\ ( х ) . Вычисление л ( А ) з случае эргодичности цепи Маркова J производится в соответствии с равенством

(1)

■Т ( А ) ~ £ Як тк{ А ) Як тк >

в котором як , к е J - стационарное распределение цепи Маркова J , тк - среднее время "сидения" ПМП у (х) в состоянии к е Н , а тк( А } определяется равенством

и*( А ) = М | | * А< ( £ ( х ), к, у)) ду | «70 = *

где <70 - начальное состояние цепи Маркова J.

Располагая переходными вероятностями р ( з', з" ) для любой пары состояний в' я в" основной компоненты процесса ( £ ( х )), можно вычислить переходные вероятности вложенной в ПМП у (х) цепи Маркова J. Знание переходных вероятностей цепи Маркова J даот возможность вычислить стационарной распределение Як г к б J. Непосредственное вычисление гг.к сопряжено с большими трудностями, однако в силу топологии переходов по состояниям основной компоненты эти вычисления могут быть значительно облегчены. Действительно, тк ио-х&г бить Еыражено через величины шк( А ):

(2) =

Таким образом, с использованием (2) выражения (1) могут Сыть прздставлены в следующем виде:

(3) я1й)=Як Л)/

Л Як 2 лк< 3) •

\ к 1 /

Далек, введем в рассмотрение ПИП ?(х) с фазовым пространством, совпадающим с фазовым пространством в' основной компоненты £ ( х) процесса г] ( х ), с переходными вероятностями ру ,1, 3 6 й' вложенной в него цепи Маркова 3 , определенными выие, и со средними временами "сидения" в состояниях ак{j ). Стационарное распределение ¡г Ij ) ПМП у (х ) будет определяться равенствами

(4)

я а) =

Як! Л-

£ £ 'V ^ ) '

к $

в котором д^ - стационарная вероятность состояния j е связанного простым путем с состоянием регенерации к ё Э'. В силу топологии вложенных цепей <7 и 3 име»т Нбсто следующие соотношения:

(5) — = С, к е а ,

Як

в которых константа С пе завися г от к. Из сравно<1Ил (4) и (5) вытекает, что в силу соотношений (5) и равенств = Ркз Я к] - Чкк Рк] имеет иасто равенство

я (j) = я^j). Это позволяет считать ГОШ у (х) эквивалентный процессу ц (х) по стационарному распределению.

Таким образом, задача пахо:;деиия стационарного распределения процесса ц ( х ) может быть сведена, к задаче ьычис-локия стационарного распределения осредняодего ШШ (ОПИЛ) у (х). В работе предлагается методика определения переходных вероятностей вложенной в ОПНП у (X') цепи Маркова 3 и средних величин времени "сидения" в состояниях ОШШ у ( х ), основанная на привлечении функций (плотностей) распределения разностей случайных величин, как в простейшей случае двух случайных величин, так и в многомерном случае, что с вичислительной точки зрения не представляет значительных трудностей. При этом не требуется вычисление 0^(;<), 1, ^ 6 5' - полумарковского ядра ОПМП у ( х ).

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

Определенно 1. Если ■ на графе размэток ВССП, для некоторой рагмзтки Н суцествует раьметка Я', непосредственно' достижимая из И, в разметке М' имается не более одного «^экспоненциального парохода, сохранившего возбужденное состояние, имевшее место в М, то такую пару разметок (И, М') назовем простой.

Определенна 2. ВССП назоьем простой, если все возможные в ее графе разметок пары (К, М'), составленные из до-стизлких разметок, в которое: Ы' непосредственно дости>хима из Н, являются простыми.

Описанный в главе 1 подход к изучению случайных процессов смен разыеток в ВССП с помощью ОПМП основан на представлении о состоянии ВССП N в момент срабатывания некоторого перехода ^ в виде пары, состоящей, во-первых, из

той разметки, е которую попадает сеть в результате этого срабатывания, и, по-втсрых, вектора Ф, составленного из функций (плотностей) распределяют (остаточного) времени срабатыва!1ия всех возбужденных в данной разметке переходов.

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

В этой связи интерес представляют достаточные условия, при выполнении которга ОПМП, построенный по ВССП в определенном вьпгз смысле, обладал бы конечным множеством состояний гл имел единственный положительный возвратный класс. Каждая из этих двух задач репается в работе самостоятельно. Наиболее важная из них - первая - решается сужением всего класса ограниченных ВССП (ограниченность - необходимое условие конечности числа состояний ОПМП) до класса ВССП с ограниченной предысторией [7-9].

При формализованном подходе к этой проблеме целесообразно построить некоторый специальный граф ё. Состояниями этого гргфа являются пары "разметка И + множество неэкспо- , иенцкальных переходов, отсчет времени срабатывания которых начался до попадания в О". Заметим, что число различных состояний с одинаковой первой компонентой М не превзойдет числа разметок-предшествснников М на графе разметок б.

Также как и для графа разметок й дуги графа ё нагружаются символами переходов, а также двумя различные символами (например, 0 и 1). Правило, по которому некоторой дуге присваивается 0 или 1 следующее: пусть данная дуга исходит из состояния с непустой второй компонентой, тогда на графе 5 эта дуга нагружается символом 0, в противном случае - 1. Нагружая подобным образом все дуги графа ё и игнорируя символы переходов, приходим к некоторому инициальному источнику 5, представляющему всеми своими состояни-я:.!и некоторое регулярное множество /3(5) в алфавите (0,1).

Определение 3. ВССП является сетью с'ограниченной предысторией, если в множестве /3(5] не существует слова а, такого, что а/7 б/2(5), где р - 0* (/7 является итерацией 0).

Для проверки выполнимости определения 3 можно воспользоваться аппаратом анализа поведения произвольного источника, рассмотрении в [1, 2, 4). Определение 3 Судет выполняться тогда и только тогда, когди в формальной система (ФС) < , К >1( построенной по укороченному дереву [4¡ источника G, для любого соотношения vHi v1(i vKi в слове vKi существует по крайней мере одно вхождение символа 1.

Основной результат для ВССП с ограниченной предысторией формулируется в виде следующего утверждения.

Утверждение 2. ОПМП на множестве пар (М, F) а ВССП с ограниченной предысторией имеет конечное множество состояний.

Обозначим класс простых ВССП с ограниченной предысторией символом N. Подкласс этого класса, состоящий из ВССП, в которых возбуждено одновременно не Солее двух переходов, обозначим символом N , N <z N .

Рассмотрим зависимости, необходимые для нахождения функций (плотностей) распределения остаточного времени срабатывания возбужденных переходов для ВССП из подкласса N .

Пусть в состоянии ОПМП s возбуждены неэкспоненциальные переходы t^ и tÍ2 и только они. Им соответствуют функции распределения (остаточного) времени срабатывания: Fx (х) и Fz (х). Тогда функция распределения случайной величины 4 = rain ( > 4г Ь где » £2 ~ независимые случайные величины, равные (остаточным) временам срабатывания переходов и ti2 соответственно, имеет вид

F ( х ) = 1 - f] [ 1 " fi < * ' 1 • • i-i

Отсюда плотность распределения случайной величины 4 при условии, что существуют плотности распределения случайных величин , равна

(6) / (х ) = fj (х ) [ 1 - Fz (х) ] + f2 (х ) [ 1 - F, ( X ) ].

Среднее время пребывания ОПМЛ в состоянии s определится из следующего равенства:

30 St

("( i Mí = J х { ( х ) dx = f [ 1 - Fj (-x ) j [ 1 - F, ( x .1 ] d.\ .

o o

Для случайной величины с - 4i ~ 4: с помощью формул свертки можно вывести следующие равенства:

(P) F. ( х ) г. J Fi ( x + y ) dF2 ( y ) = 1 - j F2 (y - x ) dF1 ( y ) ,

0 *

« as

(9) f. ( X ) =■ | f5 ( X + y) f2 { y ) dy = J /2 ( y - x ) ( y ) dy .

О л

Тогда вероятность p ( s , s') перехода во вложенной цепи Маркова из состояния s в состояние s' при срабатывании перехода tj мозга о вычислить как вероятность pis, s' ) =

= Р ( Îi < Î2 >'••

ce

(10) Pis , s' ) = F. ( 0 ) = J Fl ( y ) df*2 ( y ) =

0

0 я>

= J J fj ( x + y ) f2 ( y ) dy dx .

' -со 0

Условная плотность распределения остаточного Бремени срабатывания перехода t., при условии, что из состояния s ОПМП после срабатывания перехода tj, перешел з некоторое состояние s", вычисляется исходя из (9) следующим образом:

Ш) f- ( х | > ¿2 > =

0 при х < О ,

<п

[ 1 - г < я . s" ) ] J fj ( x + у ) /2 ( у ) dy при X 5 0 .

о

Функция распределения Fe ( x | > ) может быть после ■этого вычислена интегрированием:

П- « * | il > Î2 > =

J 0 rip'i x < 0 ,

1 [ 1 р ( s , s" ) Г1 j [ F, ( x i- у ) - Fj ( у ) j df2 ( у ) при X > 0 . 1 3

Для ВССП из класса N получение расчетных соотношений! в сучуственнсй мере опирается на представление полу-маргсвской матрицы 0(х) через условные вероятности в виде

С,, ( х ) -- P{/„=s,, вп _ ! < х | Я п „ ! = Sj } =

= J Р { ^ n = | - 1 = t ' }dPit

о .

где Як - состояние ОПМП на Jc-м шаге, - время пре-

5иванмя ОПМП в j-м состоянии на (п - 1)-м шаге эволюции,

Pi (х) - функция распределения времени пребывания в i-м состоянии.

Если в i-м состоянии ОПМП Л( t) возбуждены переходы tj1 ,..., tik и им соответствуют (условные) функции распределения (остаточного) времени срабатыва!шя переходов Fl{x),..., Fk{x), то для случайной величины 0„-i ~ = min { | г = 1, к }, где 4i > ••• / ~ независимые случайные величины, равные временам срабатывания переходов t^ ,..., tijr соответственно,' имеет место следующая функция распределения:

(12) Fi (х) = 1 - П [ 1- Fr (х ) ].

г » 1

Среди переходов t^ ,..., tik могут быть и переходы с экспоненциальным распределением времени срабатывания.

Среднее время пребывания Л(С) в «i-м состоянии равно

ОО «С Jt

М0„ _! = fxdPj (х) = I fl [ 1 - Fr ( л-} ] dx . о О г = 1

Для вычисления переходных вероятностей pi} во вложенной цепи Маркова требуется предварительно вычислить функции

(13) <?ij (*) = Р л - 1 = si }

по всем состояниям sJf в которые может перейти ОПМП из состояния Sj (здесь qij (х) - условная вероятность того, что ОПМП попадает в состояние sj, пробыв ц состянии st время, равное х, при этом имеет место равенство ¿qjj(X) = l). )

Знание функций распределения Fj(.x ),..., l'k ( >;) или со-ответствуюких плотностей делает эту задачу разрешимой. Так, например, если все функции распределения времени срабатывания переходов абсолютно непрерывны и переход из состояния si в состояние s: произошел в результате срабатывания перехода t^, то вероятность (х t может быть вычисле-

на следующим образом:

г - 1

r * 3

■/,, <v>

ir

(X ) fl[ 1 - F, (X ) ]

v * г 1

У /г { X ) П [ 1 - FP (* > j - 1 p « 1 рог

Теперь вероятности pi;) могут быть вычислены в соответствии с равенством

(14) Pü - lim ßj-j ! х )= f ( х ) dPi ( х ) .

* X J J

О

С учетом (12) и выражения для qi;j{x) из (14) имеем:

х jt

Pii = J П [ 1 - pr <* ) ]dF5 (X ).

О г » 1

Г * S

Плотность распределения остаточного времени срабатывания перехода , сохрэнинхего возбужденное состояние в состоянии r,j после срабатывания перехода tis, имеет вид

(15) <рх ( -х ) ■= р'1'! f, ( х + у ) 5ij' ( У ) dy .

о

В этсм выражении - нормирующий множитель, опреде-

ляемый при условии, что интеграл в правой части (15) не равен тождественно нулю, в соответствии с равенством

0Г. £

ц = | | ¡у ( X + у ) о^ ( у ) dy dx .

о о

Если же интеграл в правой части (15) тождественно ра-еен нулю, то это свидетельствует о тем, что переход t^ не может сработать раньше . В (15) в случае абсолютно не-

прерывных распределений времени срабатывания всех переходов имеем следующие выражения:

? Л г 1

о и < х > = [ П [1 ~ рг <с> ] <с>'

о г =2 Г # 5

( -X ) = ¿Г1/ ^ ( X +- у ) £а ( у ) П [ 1 - ^г ( У ) ] , О г » 2

Г * 5

аз сс ^

Я = I | ^ ( X + у ) 1а ( у ) П [ 1 - Гг ( у ) ] ¿у ¿X .

г - 2 Г * S

о о

Вопрос о числе пол.оаздтслыцйс Еоэорагкик классов во сложенной цепи Маркова может Сыть ролей с шжсздю следующего утверждения.

Утверждение 3. Пусть в графе рарм'еток ВССП I' с N имеете«, равно один максимальный сильно связный подграф, любая разметка которого достижима из лзэбай ро-чьтки графа размоток. Если плотности распределения времени срабатывания всех переходов ВССП И" либо (1) непрерывны на [О, а] при любых положительных а и положительны при к > О в некоторой окрестности нуля, либо (2) непрерывны и положите лыщ на полубесконечных промежутках ьида (а, при. лэ~ бых неотрицательных а, то в любом из этих случаев вложенная в ОПМП цепь Маркова имеет единственный полозительиий воз-иратный класс.

Если ни одно из условий, регламентируемых е'утверждении 3, не выполняется, то для каждой конкретной ВССП пред-г варитсльно нужно построить ОПМП в полном объеме и убедиться в существовании во вложенной цепи Маркова ровно одного положительного' возвратного класса.

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

Р} га, • ' '

(16) Р) » '

■ . т Р* **

.Л«?' : ' . .

где 5'- множество состояний вложенной- цепи Маркова, р -= (р1, - ее стационарное распределе«(ие, вк - сред-

нее время пребывания ОПМП в Состоянии

Суммируя левые части . соотношения (16) по всем з}, имеющим одинаковую первую компоненту - разметку Я, получим предельную вероятность"' нахождения ВССП в произвольный момент.времени в достйжимой разметке М.

В гладе . 3 рассмотренная вьо;е методика получает обобщение, что позволяет распространить ее на ограниченнее ВССП <: ограниченной предысторией," не являющиеся простыми. Суть этого обобщения заключается \в том, что вторая компонента состсяни* ОПМП понимается здесь не как совокупность плотность»"' распределения времени срабатывания, приписанных отде-

льна! возбужденным переколем, а как многомерная плотность распределения ял.1 ^со.ч переходов, возбужденных в разметке, являтчйся лэрвсЯ ко'люнентсД состояния ОПИП.

В качестве состояния процесса рассматривается пара Ш, К): "разметил - многоысрна «г функция (плотность) распределения времени срабатывания ¿сех возбужденных в М переходов".

Обозначим класс ВССП с ограниченной предысторией символом Л/р ; М с N с Д'0 ), Утвергдекие 2 справедливо так~о по стнопенио к ж-Дой ВССП из класса Л/0 .

Построение ОПМП, »юяалиругпаго случайный процесс з РССЛ, ведется последовательно. Начальное состояние ОПМП образуется парой {Я0, £0\, где Г0 - произведение исходных плотностей распределения времени срабатывания всех переходов, возбуждешшх в начальной разметке М0 . Пусть для состояния СПКП si = ( Я , £} известна многомерная плотность распределе.'дая £. Определим вероятности, с которым! во вло-:г«нной цепи Маркова осуществляются переходы з соседние со-СТОЯ1ГИЛ из состояния si. Будем полагать, что в разметке ЕССП N возбуждена переходы til ..., С1г . Многомерная плотность £ представляется с следупаем виде:

(17) / ..... Х1г ),

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

Определи!' вероятность р^, с которой осуществляется переход зо вло~зннсй пепи.Маркова из состояния з1 в некоторое состояние , например, в результате срабатывания перехода £:(1 , -¡^ - 1 , га . Эта героятность может Сыть определена как вероятность следукс.аго события: Рц--* | >$>,}>

где , - случайные величины (остаточного) времени

срабатывания переходов, возбужденных в разметке М. По известной плотности. £ находим

(18) р13 = I/йХд/...

■ - 0 *<:

Пусть из состояния si ={М , £ ) в результате срабатывания некоторого перехода tip, ¿р = 1, т, ОПМП переходит

в состояние SJ =( , £ ) (предполагается, что во вложенной цепи Маркова этот переход осущестаиы с некоторой положительной вероятностью). Пусть в ВССП в разметке Их после перехода из разметки М сохранили возбужденное'состояние первые Л переходов: Сд , ..., > Р * 1, а для переходов ..., появились условия возбуждения. Тогда для состояния Sj многомерная плотность распределения <р может быть представлена в виде произведения

(19) <р = Г (х^,..., х1к)£^ (х^,)... £и 1хх),

в котором £ - многомерная плотность распределения остаточного времени для переходов 1:^,..., а ¿у (х^),..., ~ исходные плотности распределения времени срабатывания. Это представление для плотности <р возможно в силу того, что случайные величины времени срабатывания переходов С^,..., ^ независимы, а также каждая из них не

зависит от случайных величин остаточного времени срабатывания переходов ^ ,..., С1к и наоборот. Таким образом, вычисление плотности <р сводится к вычислению плотности /.

С этой целью предварительно строится 1Х - многомерная плотность распределения для ^ »... , 4 - случайных величин остаточного времени срабатывания переходов из множества ..... \(С1р), где = ¿0,1*р:

(20) х1р + 1,..., х1т) =

= /<~1 (XV-, х^.,. х1г),

где

СО

о ' '

а нормирующий множитель р"1 определяется из равенства

ее X'

// = i ... i /1 йх!. ... сух! с(х', . ... с1х: .

и ?

проинтегрировать выражение для 11 по последним г переменным:

(21) f ..... *it> = i-jÄ dxJt + I ... dx^dx^ ... dxti.

о 0

Случайнре время пребывания в состоянии Sj определяется как 9 = min { f j ¡ i = 1 , г), где > ••• < ~ случайные величины, равные (остаточным) временам срабатывания переходов t,¡t..., Cir соответственно. Поскольку в общем случае не являются независимыми случайными величинами, определение Pj ( ) = Р ( 0 < х } может вестись в соответствии со следующими равенствами, в которых используются функция или плотность распределения остаточного времени срабатывания переходов:

(22) P¿ (х) = Ft ( х) + ... + Fr (х ) -

- £ yiJ < x ' x ) + ... + ( -1 )r F ( x , ... , x ),

i" i

где F, ( x )= F ( x ,«>,..., <ю ),.. ., Fr ( x ) = F ( so , ... , со , x ), Fu i x , x ) = F ( x , x , со , ... , M ),..., F,..^ r ( x , x ) = F ( a ,...

... , =0 , x , x ) и т. д.

dP * 00

(23) —- = |... J f ( x , x2 , ... , xr ) dx2 ... dxr + ...

X X

<C «3

... + J... J f ( Xj , ..., xr_1( x ) dXi ... dxr _ i .

x x

Утверждение 3 сохраняет свою силу такте и для ВССП из

класса Nn .

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

В глаза 4 рассматриваются примеры применения методики исследования ВССП для анализа технических устройств. К юс числу относятся модель взаимодействия процессоров и блока. памяти, описываемая как система массового обслуживания (СМО), и модель обслуживания в циклической локальной вычислительной сети (ЛВС) . Эти модели рассматриваются в виде ВССП с ограниченной предысторией, что позволяет привлечь аппарат, описанный в главе 2, поскольку в этих ВССП одновременно Еозбужлено не более одного неэкспоненциального перехода. На основе полученных для первой модели данных строится модель обслуживания запросов от действующих пр> конве-

Верному принципу процессорных элементов ь распределенную буферную память.

Первая модель рассматривается как СМО с п входными каналам;.', на каждый иэ которых поступает пуассоноиский поток заявок с, интенсивностью Л. Поступающие в СМО потоки заявок независимы. Если обслуживающий прибор занят, заявки накапливаются в параллельно-последовательном буфере, состоящем из л мест ожидания г, параллельной составлягцей (по одному месту не каждый входной канал) й г + 1 места в последовательной составляющей, .s которой одно место принадяе-згит обслуживающему прибору. Если последовательная часть буфера заполнена, то поступающая по любому иэ входных каналов заявка остается в месте ожидания, принадлежащем этому входному канал-/, в результате \16tf« данный канал блокируется и поступление заявок по нему прекращается. 0*лсй;/гяваш:е заявок производится по произвольному закону, зависящему от длины очереди и сохраняпвег.'уся до окончания обслуживания. Если в результате ухода обслужпыой заявки d последовательной части буфера освобождается последнее место для отдания, а в нескольких маета:: параллельной части находятся заявки, то освободивиееся место бесприоритетно занимается любой из них с равной вероятностью. Обслу^гиваний заявок производится при их наличии б цсслеповательной части буфера по дисциплине FIFO ("первым прииел - первым обслужен").

Если за.состояние СКО принять число находящихся з ней заявок, то задача анализа будет заключаться в нахождении предельного распределения вероятностей состояний.; В терминологии ВССП это эквшзалейтно введению обобщенной разметки, которая является множеством'достгазо&эс рааметск с одинаковым суммарным (по всем позициям сети! числом меток, и нахождению предельного распределения вероятностей достижимых обобщенных разметок.

Состояния ОПМП, описывающего эволюцию системы, рассматриваются в виде трехкомпонентного вектора. Пераая компонента - суммарное число меток в сети (обобценная разметка!* вторая - плотность распределения.врсыени срабатывания какого-либо входного экспоненциального перехода в том случае, когда:одновременно возбуждено* (AS л) входных переходов, третья - функция распределения остаточного времени срабатывания выходного перехода, ыоделируппего обслуживающий прибор. Такой подход к построению состояний ОПМП возможен в

силу полной идентичности псек эхоянь'ч пс-ра^одов и регулярности структуры ВССП.

Рсгениа за^т-гчи нагоотеншг предельного распределения вероятностей оОобтзжап: разжато;: сзодиюл к решению системы из (л + гт1цп,+ г ь 2 ) / 2 линейных злгесраических уравнений. Для наиболее 'интересного с практической точки зрения слуг а я детзр1Е-пи:ровакного обслужи п экая (np;t постоянной аре-t.'íliH обслуживания г, вел: гч-ичу р « пАг назовем коэффициентом загрузки системы) репени« осуществлялось на ЭВМ. Чнс-лзнный анализ тгроподился для п, г и р, принииазпик слйдуюкле значения: л » 2, 4, 3, 15, г - 0, 1, 2, 4, 8 и р = 0,5/ 0,75; 1; 1,5; 2.

Наряду с определенной тег'» мо^но рассгатривать тлкае двойственную CMÓ, а которой движение siesos происходит следует?»« сбразс<и: имеется л одинаковы* обслужи:? агдих приборе а с пуассоновсккм законен еСслугизашм, на которые со ~>хоца системы поступают ?ал;:кн (при наличии нгсяольких сао-бодюк приборов поступление на каадъЛ из intx оасновероят-ное) . На е.чод системы поступает поток с произвольным законом распределения промэлут^оэ пресеки калеку соседними заяв-уаии, выбор которого для каждой заявки зависит от оОаего количества имеющиеся. в систег'э заязок на •га.'-'-эн1.' поступления прег.'.'.пуией заявки. Перед обслужизгЕгзсЛ! приборами имеется обзий наггегштеяь.чый. буфер с г-f 1 кастам ояидания, при заполнении которого зхоп oMCTf-b3J Олокт-.руется и поступление заявок прекращается (при этом потерь заявок на происходит).

Граф оиУЛ! двойственной ыолелл аналогичен при одниако-zur. для обеих моделей . величин.^: л * и г с той лишь разницей, что первые составляете состояний ОПМП к и -суммарные количества меток в- ЕССП - будут в соотаетствую-

состояниях связаны равенством £ = л + + Отсюда для анализа двойственной модели имеется система уравнений глобального равновесия, идентичная системе, описанной зымо.

Полученное решение 'прямой задачи привело к возможности провести приближенный анализ модели, в которой п источников заявок обслуживаются т однотипными устройствами, перед каждым из которых имеется свой накопительный буфер. Заявки от источников равновероятно распределяются по обслуживаетим устройствам независимо от степени их. загруженности. В случае, если заявка, направляемая По i-му каналу на#обслуживание в некоторое устройство, Застает накопитель этогоустро--.'

йства полностью занят™, она остается в песте ожидания, принадлежащей данному каналу, в результате чего последний блокируется. Такая модель использовалась (Ю.М. Сокол) с анализе интерфейса лсфаллельной общей памяти для многопроцессорных вычислительных систем в предположении, что обслуживание запросов в памяти происходит по экспоненциальному закону. Анализ экспоненциальной сети массового обслуживания (СеМО) давал точное решение приближенной модели, что позволяло получить нижнюю оценку производительности системы.

Б работе данная модель рассматривается при постоянном времени обслуживании, что позволяет считать ее моделью, наиболее близкой к реальной действительности.

Когда накопители всех обслуживающих устройств имеют свободные места, работа каждой обслу-кивагщей системы протекает независимо от других. Взаимное влияние' одной обслуживающей системы на другие происходит только тогда, когда блокируется какой-либо входной канал, и уменьшается нагрузка на все остальные обслужиьааэщие устройства.

Данную открытую СеМО могло представить в виде совокупности ;п одинаковых СМО с п входными каналами, имеющих' интенсивность поступления заявок по каждому каналу, равную Л/т, и постоянную длительность.обслуживания г. При этом, если в одной из СМО произошло блокирование л-го канала, то блокируются все каналы с номером л на всех остальных СМО. Приближенно это можно интерпретировать, как уменьшение параметра .Л пуассоновского потока на всех СМО до величины Л. ( 1-е), где е > 0 может быть описано как условная вероятность такого состояния системы, когда некоторый канал не блокирован рассматриваемой СМО, но блокирован хотя бы одной из остальных (и - 1) СМО. В предположении о независимости всех СМО эта условная вероятность приравнивается к безусловной и, следовательно, может Сыть вычислена в соответствии с равенством

е = 1 - { 1 - ре,, )и'1.

Рассматривая это равенство совместно с равенством, определяющим вероятность блокирования одного канала,

приходим к следующему уравнению, решение которого может быть получено итеративным путем:

Я ( £ ) П

! _ е = -

Я л

Тогда коэффициент изменения производительности системы с распределенным обслуживанием в сравнении с производительностью системы с одним обслуживающим устройством ( т = 1), вычисляется для сбалансированных систем {р = 1) по формуле

т

Я ( £■ ) ( 1 - 3)

ii 1 - я-о

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

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

3 результате опроса отдельного абонента выявляется его состояние, которое может Сыть одним из двух: ожидание обслуживания (запрос) или отсутствие такового. При обнаружении в процессе циклического опроса i-ro абонента, находящегося з состоянии запроса, данный абонент обслуживается за время, являющееся случайной величиной с плотностью распределения it ( х). После окончания обелуга!пакия через некоторое посто-

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

Из описания данной физической модели вытекает ее представление в виде ВССП с ограниченной предысторией.

В данной модели интерес представляют стационарные вероятности того, что 1-й абонент находится в,состоянии запроса | р,^), обслуживания ( р0, , ) и в свободном состоянии,

при котором в кем происходит генерация очередного запроса ( рс, д ) . Для приближенной, оценки характеристик одного абонента все остальные абоненты можно объединить в один.

При построении ОПМП будем использовать упрощающее предположение о том, что за время г = + г, не может сработать более одного из переходов, иоделиружядих генерацию запроса, в случае их одновременного возбуждения. Основанием для такого предположения слузлт то, что в реальных системах 1/г много больше а сравнении с параметрами и Л2.

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

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

Составляя и решая систему уравнений равновесия для рассматриваемой модели, можно получить значения вероятностей Ро,х и рс,1» -1 = 1» 2. В качестве примера приведем решение системы при следующих значениях параметров системы: Лх = 0,1 мс"1, Лг = 0,5 мс"1, ¿"1=2 мс"1, ц2 - 1 мс"1, г = 0,1 мс :

р,;1 = 0,0376, рС;1 = 0,9181, рС(1 = 0,0443,

р,,2 = 0,0410, рс,2 = 0, 6423, р0_ г =0,3167.

Отметим, что рассмотренные модели системы обслуживания с параллельно-последователь,ным буфером при постоянном времени обслуживания использовалась при анализе производства на стадии предпроектного обследования, имеющего цель» создание технического задания па разработку подсистемы оперативного управления цехом сварки кузовов АО "Москвич", а также при моделировании процессов переработт сельскохозяйственной продукции, поступающей на крупные перерабатывающие предприятия. Двойственная задача использовалась при создании модели и методов планирования. и оперативного управления грузовыми перевозками сельскохозяйственной продукции на типовом с/у, предприятии. Модель циклической ЛВС использовалась на стадии предпроектного обследования, имеющего целью создание технического задания на разработку подсистемы оперативного управления цехом сварки кузовов АО "Москвич".

В глаза 5 рассматривается условия существования предельного распределения вероятностей разметок вЕССП, на основе которых могут строиться алгоритмы экспресс-анализа ВССП. Дальнейщий анализ ВССП, связанней с вычислением предельного распределения «ероятностей разметок, целесообразен только при выполнении этих условий.

Из экспоненциалы:!»! ЗССП рассматриваются ВССП типа I, переходы которых обладает положительнымп конечными параметрами пуассоновских распределений времени срабатывания, и ВССП типа II, ь которых срабатывание пэреходоз может быть кратным (например, по числу комплектов меток, необходимых для срабатывания, п' позицилх—предлественниках). На ВССП типа II наложено также условие существования конечной верхней грани для уратностей возбуздення переходов.

При таких ограничениях на зкепонециальные ВССП марковские процессы, протекающие з них, будут локально регулярными и регулярными. Это дает основание считать, что тогда ве* роятности р1 (с ) нахождения ВССП N в произвольный момент времени с в ее достижимых разметках М± е Я ( И, И 0J удовлетворяют второй (прямой) системе дифференциальных уравнений Колмогорова. Из этой системы может быть получена система линейных алгебраических уравнений, которой должны удовлетворить предельные верочтности разметок . Последняя получается из системы уравнений Колмогорова путем подстановки в нее неизвестных стационарных вероятностей Р = { р1( рг, ... ). Если эта система уравне1!ий с присоединенным к ней уравнением £ р1 = 1 не имеет ненулевых репе-ний, то у ВССП не существует предельного распределения вероятностей разметок.

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

Введем в расмотрение для каждого перехода с Т, 1 ~ 1, т, ВССП типа I неотрицател;.ную величину

~ £ р ( М*), 1 = 1 , га.

Мк £ Л(Л1>

Здесь р[Мк) - предельная вероятность разметки () = ( Ь11( ..., Ь^) вектор, компонента которого

Ь^ = ^ ) равна кратности дуги, ведущей из р^ е Р в

^ е У, Р - множество позиций ВССП N. Вероятностный смысл я^ заключается в том, что эта величина равна предельной вероятности нахождения ВССП в разметках, в которых переход ^ возбужден.

Для ВССП типа II для каждого ^ е Г, а = 1, т , рассмотрим величину Мг1, представляющую собой' математическое ожидание. кратности возбуждения перехода 11 в установившемся режиме:

МгЛ = £ гкр[Мк)

г* )]5М* <{гк +1)1* Г 11

в случае естественной ограниченности кратностей возбуждения переходов;

Мг, = X гкр{Мк) +

г * < К 1

+ ^ 2 Р ( ) ' я* Гг И

если кратность возбуждения каждого перехода в случае ее искусственной ограниченности имеет точную верхнюю грань Ях.

Для ВССП типа II, удовлетворяющей этим ограничениям и имеющей предельное распределение вероятностей р ( М }, для всякого е Т выполняется неравенство 0 £ Мг^ < со .

Объединяя обозначения обеих величин 1! Мг^ в одно яг^, можно считать, что величина будет определять ин-

тенсивность вероятностного ординарного установившегося (при С -> оо) потока меток через переход ti .

Поскольку в установившемся режиме в каждой позиции р^ имеет место равенство входящих и Екжодяаих вероятностных потоков меток, может быть составлена система уравнений баланса этих потоков, строящаяся с использованием матрицы О, задающей отношения инцидентности Г и функции кратности дуг И, и вектора-строки я = (Я1я'1— Лт/гга): (24) яй - О,

где 0 - нулевой вектор-строка размерности 1хл.

Система ураннеш'п [2Л) может Сыть дополнена рядом со-отнозеннК между величинами .тi, если учесть условия срабатывания переходов ВССП. Пусть сущестэурт пара переходов ti и С], для которых множества Ыц = { к | е?^ > 0 } и .Vj = { 1 | > 0 ), определяемые по д'-й и j-íi строчкам матрицы 0~, либо связаны отнесением включения, либо совпадают. Тогда в случае искусственной ограниченности кратностей позбу^дания переходов ВССП типа II имоют изсто следующие импликации:

(25) ( V ( £< ) 5 *£• ( ^ ) ) А ( ^ а ) => .-Гд г

(25') ( *Г (Сл ) = 'Р )) Л ( Рч = П} ) => = к3,

Для ЕССП типа I могло принять д = 1, га , а для

ВССП типа II' с естественней ограниченностью кратностей возбуждения переходов чеегдз справедлива импликация (если полагать, что - /11 - верхняя грань кратности иозбуз-дения перехода t1):

) £ ) /11 >. /ij <» Яд 2 Л.,,

что позволяет считать справедливой ¡¡ишиашо (25) для всех рассматриваемых в главе 5 разновидностей ЕССП.

Систему уравнений (24), дополненную соотношения;эт правой части (25) или (25') (в случае их наличия), 'будем называть расширенной системой уравнений < баланса. При этом в случае наличия в ВССП переходов-источников она будет неоднородней, поскольку для каждого такого л^рзхода соответствующая величина я^ = 1 .

Очевидно, что мотет существовать не более т - 1 соотношений типа правой части (25) или (25'), и тогда о&зее число соотношений п расширенной системе (24) не будет пре-вьппать г + га - 1, где г - ранг матрицы О.

Утверждение 4. Если лизая ВССП II -- ( Р, Г, Г, М3, Л) имеет предельное распределений .вероятностей достижимых'разметок, то ее расширенная система уравнений баланса иыэёт положительные решения ( , ..., ят ), ( Уд ) ( 0 < 5 1).

Так::м образом, если для некоторой живой ВССП N = ( Р, Т, Г, И, М0, Л) ее расширенная система уравнений баланса не имеет пологзгеольных решений пт),

( VI ) ( 0 < я I <. 1) , ~о ВССП N = ( Р, Г, Г, М0, Л), у которой М0 - произвольная начальная разметка, обеспечивающая ее

живость, не имеет предельного распределения вероятностей достижимых разметок.

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

Утверждение 5. Если ВССП N = (Р, Т, Г, И, М0, Л), свободная от достижимых тупиковых разметок, имеет предельное распределение вероятностей достижимых разметок, то ее расширенная система уравнений баланса имеет ненулевое неотрицательное решение ( л^ ,..., ят ), ( VI ) ( 0 < ж ¡_< 1 ) .

Следовательно, если для некоторой ВССП N = ( Р, Т, Р, Я, М0, Л), свободной от достижимых тупиковых разметок, ее расширенная система уравнений баланса не имеет ненулевых неотрицательных решений ( лг ,.. ., л т), < 1), то

ВССП лГ = ( Р, Т, Р, Я, Й0, Л), у которой Ы 0 - произвольная начальная разметка, обеспечивающая отсутствие у нее достижимых тупиковых разметок, не . имеет предельного распределения вероятностей достижимых разметок.

Утверждение 6. Если ВССП N = ( Р, Г, Р, IV, М0, А ) имеет предельное распределение вероятностей достижимых разметок, то ее расширенная система уравнений баланса имеет неотрицательное решение ( я х , ..., л'п), ( Ч/л ) ( 0 < л 1 <. 1).

Отсюда, если для ВССП Ы = ( Р, Т, Р, М, Я0, Л ) ее

а) однородная расширенная система уравнений баланса.в качестве неотрицательного имеет только нулевое решение, то для ВССП N = ( Р, Т, Р, К,. Й0, Л), у которой Й0 - произвольная начальная разметка, либо не существует предельного распределения вероятностей достижимых разметок, либо, если .оно существует, то положительные вероятности имеют только достижимые тупиковые разметки,

б) неоднородная расширенная система уравнений баланса не имеет неотрицательных решений (яг1(..., ,ти), ( Ул ) ( 0 <;

то ВССП N = ( Р, Г, Р, V, Мв, Л), у которой М0 ,-произвольная начальная разметка, не имеет предельного распределения вероятностей достижимых разметок.

Для ограниченных ВССП все сформулированные утверждения также справедливы. Однако, поскольку в ограниченной ВССП

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

Утверждение 4*. Если ограниченная СП N = ( Р, Г, Г, И, М0 ) является живой, то при любом А: т /?+ однородная расширенная система уравнений тлеет положительное решение 1*1 ,..., лг,„ ), > 0) .

Отсюда слР^ует, что если для некоторой ограниченной ВССП N = ( Р, Т, £", И, М0, А ) ее однородная расширенная система уравнений не имеет положительных решений, то СП N = ( Р, Т, Р, м0 ) с произвольной начальной разметкой М0, обеспечивающей ее ограниченность, не является живой.

Таким обр^иом, утверждение 4* дает возможность доказывать отсутствие живости сети без построения дерева достижимости или графа разметок, задаваясь произвольными (например, 'рапными 1; параметрами пуассоновских распределений всех переходов сети.

Утверждение 5*. Если ограниченная СП N - ( Р, Т, Е, М, М0 ) свободна от достижимых тупиковых разметок, то при любом Л: Г однородная расширенная система уравнений имеет ненулевое неотрицательное решение (/г1,..., лгт), (\уд)(/г1 й "0 ) .

Таким образом, если у некоторой ограниченной ВССП N - ( Р, Т, Г, М, М0, А ) однородная расширенная система уравнений баланса имеет в качестве неотрицательного только нулевое решение, то у ВССП N = ( Р, Т, Г, Я, М0, Л ) с произвольным Л: Т-» и с любой начальной разметкой М0, при которой она ограничена, в предельном распределении положительные вероятности имеют только достижимые тупиковые разметки.

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

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

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

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

Динамика СП может быть описана следующим матричным уравнением:

(26) М = М„ + 5(<т)'0,

в котором М0 - начальная разметка, Н - разметка СП на ¿-м паге, ¿1а) - вектор счета срабатываний переходов СП, О -матрица, определяемая функциями входа и выхода СП. Матрица 0 является разностью матриц. С+ и размерности т х л,

где т - число переходов, п - число позиций СП, при этом 0+= ||с/уI! определяется функцией выхода, т.е. с1у равно кратности дуги, исходящей из 1-го перекода в _7~ю позицию, а

1М7)|| определяется фунм^игй входа, т.е. с^ равно кратности дуги, исходящей из j-й позиции в 1-й переход. Вектор счета срабатываний Б (а) - вектор-строка размерности 1 х а, в котором 1-я компонента е1 равна числу срабатываний 2-го перехода в допустимой в данной СП последовательности срабатываний переходов а, переводящей сеть из начальной разметки М0 в разметку М. Наличие в СП ингкбиторных дуг никак не отражается на матрицах и О", а лищь накладывает .соответствующие ограничения на множество допустимых в СП векторов счета срабатываний.

Целочисленный вектор-столбец X называется р-инвариантом, если он является решением уравнения

(27) ОХ- 0.

Если X - матрица, построенная из всех базисных решений уравнения (27) и имеющая размерность л х 1, где 1 = л -- г > 0, г - ранг матрицы О, то имеет место соотношение

(28) МХ = М0Х,

описызавдеа инвариантные свойства досяьа'йт« V--'*—СП. Таким образом, произвольная разметка И, не удовлетворяющая соотноиению (2S), не язляется достигииой в анализируемой СП. Поскольку множество дости-гимыя разметок в СП с ингиби-торнчми дугами погружено в множество достижимых размзток СП, получаемой из исходной исключением из сети ингиСчторных дуг, становится очевидным, что разметка, не удовлетворяющая уравнению (20), не является дости-змсй и в СП с ингкбитср-ными дугами.

Логическим условием отсутствия возбуждения некоторого перехода tj является равенство 1 дизтюнкции ;

(29) F, = 3fi)2 v ... v xlkl v yhj v ... v Уjqii

состоящей из следующих функций:

1) xrJ= 1, если количество меток а позишги рг не менее кратности дуги, ведущей из рг в t¡, в противной случач xri = 0;

2) yrJ= 0, если а позиции рс/ связанной ингибиторной дугой с переходом tx, отсутствую? ыэтки, в противно»; случае yrJ= 1.

Равенство (29) определяет гсга^остяо разметок U{Fi), п которых переход tx не iniaer условий ¡гозбутгдения. FaccuaT-ривая пересечение

п А .4 ( F, ) ,

1---1

где га - ¡ Г |, по;гучаям icío~sctso зссх тупикодавг ДЛЯ данной СИ размоток. Отсгдз логически* условием отсутствия возСугдснн!« • переходов яо всей СП яг-ляется равенство 1

конъенкцки

(30) .4 = рг ... Fa.

Для выявления множества £1 асах туликосых рагметск ца-лесообразио' осуществить перевод в правой части равенства (30) от коиггякдии дизъянкцяй к дит-вакха^и г.ошлгнкщгй, прм котором появляется возгаганость использовать упрспагсле тождества алгебры логики, а та'а'о привадуа&п» me-; прлпштг

a) если x¡j и - ^ynKii'ct, описивзкс?»? условна roa-бурления дуг, оеяуар« из pj¡ з tj к С* ссответстзе(!Но, то конъюнкция хх , равна Хц, если < dj¡it равна Хц,,

если d'i > dti; если so dZ¡ " djj, то )ll} - х^, и коиггзя-кция xi3 х^ прибегаете!? равной явСой из эстж двух функций}

б) если у^ и уфункции, описывающие условия возбуждения ингибиторных дуг, ведущих из р1 в и соответственно, то конъюнкция у ^ у 1к может быть положена равной любой из этих двух функций;

в) если х1;) - функция, описывающая условия возбуждения дуги кратности в, ведущей из pi в ^ (с!^= а), а у 1к -функция, описывающая условия возбуждения ингибиторной дуги, ведущей из Р} ъ tk, то конъюнкция х1з у & тождественно равна 0, если в = 1, в противном случае эту конъюнкцию положим равной функции обращающейся в 1 для всех п^, удовлетворяющих неравенству 0 < т1 < э , и в 0 - в противном случае.

Используя правила преобразования а) и б), можно привести выражение для К к такому виду, когда в каждой элементарной конъюнкции каждой позиции, представленной в ней некоторыми функциями, будет соответствовать только одна функция х^ или Ухк• в случае, если после указанных действий в элементарной конъюнкции для некоторой позиции присутствуют обе функции хц и у1к, может быть применено правило в). Дополнительные возможности упрощения могут быть достигнуты, если в разных конъюнкциях отождествить функции х^ и х1к в случае равенства сЗ^ .

Обозначим множество разметок, определимых равенством К = 1, через М(К). Все преобразования выражения для К с помощью правил а) - в) и тождеств алгебры логики приводят к выражению, эквивалентному исходному, в том смысле, что И(К) = О.

Пусть ранг матрицы С удовлетворяет неравенству г < п.

Утверждение 7. Если на множестве М(К) уравнение (28) не имеет решений, то СП не имеет достижимых тупиковых разметок.

В случае наличия в множество М(К) решений уравнения (28) может быть проведено дополнительное исследование этих решений с.помощью уравнения (31), получаемого из уравнения (26), и базирующееся на приводимом ниже утверждении .8. (31) ЭО -И' - М0 . . ..

Утверждение 8. Если для каждого М'е. М(К), яьляюще-гося решением уравнения (28), уравнение (31) не имеет поло-

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

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

Отметим, что в случае отсутствия р-инвариантов у СП анализ может изначально базироваться на утверждении 8, если его сформулировать следующим образом.

Утверждение 8*. Если для катдого М' е М(К) уравнение (31) не имеет Еоложительных целочисленных решений, то СП не имеет достижимых тупиковых разметок.

Замечание, сделанное вьгае о справедливости утверждения 8 по отношению к СП с ингибиторными дугами, сохраняет свою силу и в случае утверждения 6*.

Глава 7 посвящена вопросам конструктивного описания регулярных множеств с помо:яыо языков эквивалентных преобразований (ЯЭП). Рассматриваются симметричные чистые правые регулярные формальные системы (ФС). Тот факт, что множество слов, выводимых в произвольной ФС, регулярно, является очевидным частным случаем соответствующего результата Р.Бюхи. Обратный результат, а именно: произвольное регулярное множество состоит из слов, выводимых !з некоторой ФС (как показано а работе, даже а так называемой правильной нормализованной ФС), доказан азтором [1, 2, 4].

Пусть X - фиксированный непустой конечный алфавит V = ( л', , х? , ..., >:п ) . Под ФС < К0 , К > , будем понимать совокупность коночного множества слов в алфавите X, обоз--тчаемого К«,, и конечного множества соотношений (^-набора) К вида

(32) у1! V 4-у у12 V , 1 еГ- 1, т,

^де , V¡2 - -фиксированные слова а Л'", V - синтаксическая переменная (ниже эта переменная опускается).

В, ФС < Кц , К > слово ' ы2 получается из слова ь^ г/тем левого зквивалоктного преобразования, если в К суще-:твует соотношение vLl <-» vl2 такое, что = v Ц и', а

'•'г - • Если же \)2 = V и', а ьг1. = у', то в этом

:лучае слово . получается иэ слова путем правого

• кгншаленткого хтрео£5разования.

Выводом слова н2 из слова ,в ФС < К0 , К > назовем цепочку слов н^! , ы12,..., где = угц = ы2, а + получается из слова ьг^ путем некоторого эквивалентного преобразования.

Множество соотношений Кб ФС < К0 , К > на множестве X порождает отношение эквивалентности Ек, а именно, два слова и иг эквивалентны в Ек (ыхЕки2), если суще-

ствует конечный вывод слова и2 из слова .

Введем множество слов, выводимых в ФС < А'0 , К > :

£ ( К0 , К ) ^ | и | ( 3-ы' б К0 ) ( УЕкн') | .

Известно (по работам Вехи и Кратко), что класс множеств, выводимых с помощью рассмотренных ФС, в точности совпадает с классом регулярных множеств и что для описаник произвольного регулярного множества достаточно использовать ФС с соотношениями вида VI Однако эти ФС не рас-

сматривались как средство описания регулярных множеств, а исследовались лишь их возможности как частного (и притом весьма простого) вида исчисле!Шй Поста. Отметим, что ФС в том виде, в каком они рассматривались в работах Бюхи и Кратко, не могли служить удобными языками для описания поведения автоматов в связи с тем, что в общем случае эти ФС не давали простого (в интуитивны смысле) алгоритма установления эквивалентности произвольной пары слов и, как следствие, простых алгоритмов синтеза автомата, реализующего некоторое заданное Ь ( К0 , К ).

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

Определение 4. К-набор Судам называть правильным, если соотношения (32) удовлетворяют следусаим условиям:

(») для любого леХ д ( Y11 ) £ д ( у12 ), иными словами, правая часть каждого соотношения из (32) не короче левой при выбранном -порядке раэмзщзния слов и у12 по обеим

сторонам символа 4-», не принадлежащего алфавиту XI

(♦») не существует 1, je I таких, что у12

является исчалем слова

Спределеннч 5. Будем называть /с-набор К нормализовании:-:, если в н:'м не существует тдгогс ссотнсе^нил, что зкзивалентность левой и правой частей этого соотнопгкия может быть установлена с помольп остальных соотношений, входящих в к-Н&бср К.

Определение б. Слово ы е X' называется простим в отношении Ек, если в ¿-наборе К нет соотношения, правая часть которого является.началом слова ы.

ФС < К0 , К > будем называть нормализованной, если к-набор К - правильный и нормализований, а Кя состоит лишь кз простых в Ек слов.

Нормализованные ФС < К0 , К > будем назизать языками эквивалентных преобразований (ЯЭП) .

Назовем ФС < К0 , К > ЯЗП 1, если Есе соотношения набора К имеют вид о у0и где 1 * А (Л -

пустой 'симзол) . Для ФС такого аила Судей пргагокять обозначение < :(0 , К- >г.

Очевидно, что правильный /с-нзбср п СС < К0 , -К >х является нормализованным, поскольку всякий правый вывод в нем является укорачивающим и, следовательно, единственным.

В работе приводятся алгоритмы построения СС < К0 , К > по произвольному источнику, представляющему некоторое множество I.

В глазах 2 и 3 для анализа ЕССП с цель» выявления ее принадлежности классу ВССП с ограниченной предысторией, используется алгоритм построения ЯЭП 1, описывающего множество ЦА), представляемое финальными состояниями с 5 некоторого источника А, многество начальных состояний которого Я,, Э {Э - множество состояний источника А).

Представим множество всех.слов из X*, допустимых из макросостояния 5Н источника, в виде дерева.

Назовем х, б X допустимой в макросостоянии Б] = {я^, е.} ,..., з]1: ), если существует по ' крайней мере одно состояние с , из которого исходит, ребро, помеченное символом х1 ) . .

Дерево источника А - это ориентированный мультиграф, каждая Еершинз которого помечена некоторым макросостоянием с Я источника Л (в дальнейшем для обозначения яершкны будет использоваться обозначение соответствующего ей макросостояния а ребро, ведущее из некоторой вераины

в вершину , нагружено буквой хх,. допустимой в 5,. При этом Зк ~ макросостояние, в которое ведет буква xi из макросостоя1!Ил Sj. Начальной серятиной (аарилной ранга 0) дерева является начальное ыакросостояние 5а источника. Из каждой вершины ранга I в верпзгны ранга 1+1 ведут ребро, помеченные всеми допустимы,.« в рассматриваемой' вершине ранга л буквами.

Каждому слову V, ьедуиему в источнике А из начального ыакросостояния 5Ц в ыакросостояшю Яу, на дереве соответствует петвь, ведуыая из" начальной вермны а в^явину Б] и имеизая длину (длина ьетви - количество образующих ее ребер), равную д (ь'). В обиэх случае дерево источника Л может иметь ветви бесконечной длины. ,

Для источника Л построим так называемое укороченное дерево, обрезая, когда это возможно, ветви дерева по следу-тли правилам:

1) какдая укороченная ветвь Ь1 = переводит источник из множества 5Н а множество состояний , в которое тагсее ведет и некоторое собственное начало этой ветви;

2) никакую ветвь укороченного дерева нельзя более укоротить с соблюдением правила 1).

Если п - число состояний источника А, то длина укороченного дерева не прегосяодит 2"-1 -1. Если А - инициальна детермишфованный автомат, то эта оценка может быть понижена до п.

Обозначш£ через множество ветаей укороченного дерева, полученных в результате укорачивания (Я1 - {¿>¿1), а через Бг - множество остальных ватвей, т.е. ветвей, которые не подвергались укорачиванию. Услепимся, что концы ветвей укороченного дерева, получившиеся в результате укорачивания, будут на этом дереве подчеркиваться.

Построим ФС < К0 , К > по укороченному дереву источника Л. Множество К0 образуем из всех слов множества НА), являнцихся началами ветвей множества Вг и собственными началами ветвей множества Вх. Каждой ветви Ь^ е В! поставим в соответствие соотношение +■> Из построения следует нормализованкость ОС < К0 , К >х. В работе показано, что множество £ (К0 , К), получаемое в соответствии с описанным алгоритмом, совпадает с Ь ( Л).

ЗАКЛЮЧЕНИЕ

В циссертгпли ;:рсведено теоретическое обобщение и достигнуто резение крупной научной проблема - проблем разработки ко»: шекса но пых принципов, математических методов и средств аналитического исследования временных стохастических сетей Петри, лгзллкзихся эф£ективнгм инструментом моделирования и расчета характеристик элементов л узлое вычислительной техники, локальных вычислительные сетей, сетей сстзи, гибких .'ооизссдстаенних систем и друг;::' сложных дис-гр1тных объектов, характеризуемых параллелизмом и взаимной синхронизацией протекаяних в них процессов во времени, п техника, в сельском хозяйстве, при моделирования чрезвычайных ситуаций и пр. Класс ЗССП, дог.ускакгих анализ с помодью этих мзтодос, перекрывает .все классы БССП, доступные для анализа иными методами и известные по публикациям в отечественной и зарубегшой научно-технической литэрзтуре.

В диссертации получены следуггз-ге основные теоретические и практические результаты.

I. Для ЗССП с произвольными распределениями Ереыени срабатывания переходов разработаны теоретические основы анализа с целью нахождения предельного-распределения вероятностей достижимых разметок, вклачлжие в себя:

1. Конструктивный алгоритм установления принадлежности ВССП классу ВССП с ограниченной предьгстсрисй, основызапциЛ-ся на анализе специального множества последовательностей 9 алфавите ¡0,1), генерируемого графем разметок сити Петри, с поморю аппарата языков эквивалентных преобразований (ЯЭП) .

2. Для произвольной ЕССП с ограниченной предысторией рачраСотаны вычислительные процедуры нахождения предельного распределения вероятностей достижимых разметок, базируици-еся на применении методов гнализа случайных процессов с полумарковскими переключениями (СППНП). Эти алгоритм особенно простую ферму приобретают в случае, когда в ВССП в каа-дой разметке сохраняет возбужденное состояние не более одного незкепоненциального перехода. Для ВССП, в которых это условие не выполняется, разработаны алгоритмы анализа, базирующиеся на технике кратных интегралов и интегралов, з»-висябик от юигих параметров.

3. Для ВССП с ограниченной предысторией и с единственной сильно связной компонентой в графе разметок, достижимой Из всех разметок графа разметок, установлены достаточные

41

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

II. Выведены достаточные условия отсутствия предельного распределения вероятностей достижимых разматок в экспоненциальных .и неэкспоненциальньк ЕССП с различными ограничениями: аиьых ВССП, ВССП без достшзаэых тупиковых разма-ток, а также в ВССП, на которые не наложены какие-либо ограничения . Эти алгебраические условия и методы их проверки

** • \

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

III. Выведены достаточные условия отсутствия тупиковых достижимых разиаток в сетях Петри, что низе* важное значение как в вопросах анализа ВССП, в которых тупиковые размз-ткл ыогут являться поглоцаюЕЦИмя состояниями в случайном процессе сиен разметок, так и в задачах верификации моделей дискретных процессов, основании на применении сетей Петри. Нетоды проверю: этих алгебраических услошЛ отсутствия дос-тиззагих тупиковых разкетех также иогут служить в качестве инструмента экспресс-анализа ВССП, предшествующего ее уми-тационному моделированию и мнеадзго целью иьбежать методические оииЗкл при моделировании.

IV. В рамках теорил языков эквивалентных преобразований разработаны алгоритмы анализа ¡конечных источников, являем гхся обоОсгниек понятия конечного автомата, позволяяцие получать по произвольному источнику его описание в виде формальной системы, состоядзй из конечного множество слов (аксиом) и конечного множества соотноаекиЛ (правил вывода) - ^-набора. Эти алгоритмы использованы прл анализе графа достижимых разметок БССП для установления принадлежности их классу ВССП с ограниченной предысторией.

V. Пр:а:скителыю к техническим устройствам. на основе предложенных методов и. алгоритмов анализа рассмотрены и решены следующие задачи:

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

2. Задача о параллельно-последовательном буфере, являвшаяся обобщением предыдущей задачи, в случае наличия г (г < мест ожидания в последовательном накопительном буфере перед обслуживающим устройством.

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

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

4. Задача анализа кольцевой системы обслуживания, служащей моделью циклической локальной сети ЭВМ.

VI. Рассмотренные в диссертации методы анализа ВССП были применены:

1) при рассмотрении конкретных моделей, методов планирования и оперативного управления грузовыми перевозками сельскохозяйственной продукции на типовом с/х предприятии, а также при моделировании процессов переработки сельскохозяйственной продукции, поступающей на крупные перерабатывающие предприятия;

2) в приближенном анализе циклической ЛВС на этапе предпроектного обследования производства при разработке технического задания на проектирование подсистемы оперативного управления цехом сварки кузовов ОА "Москвич", а также при анализе образования очереди из сообщений, направляемых со стороны ЛВС отдельных технологических участков к центральной ЭВМ при случайном характере их генерации.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Иванов H.H., Михайлов Г.И., Руднев В.В., Таль A.A. Языки эквивалентных преобразований и регулярные множества. Препринт ИАТ, Москва, 1975.

2. Иванов H.H., Михайлов Г.И., Руднев В.В., Таль A.A. Языки эквивалентных преобразований обобщенного типа // АиТ. 1976. № 5. С. 140-150.

3. Иванов Н.Н; Система массового обслуживания с параллельным обслуживанием групповых заявок // АиТ. 1987. 9 10. С. 75-80.

4. Иванов H.H., Михайлов Г.И., Руднев В.В., Таль А.А. Конечные автоматы: эквивалентность и поведение. М.: Наука, 1984.

5. Иванов Н.Н. Алгебраический метод решения проблемы отсутствия тупиковых разметок в сетях Петри // АиТ. 1991. В» 7. С. 125-130.

6. Иванов Н.Н. Условия существования предельного распределения вероятностей разметок во временных стохастических сетях Петри// АиТ! 1992. Я 7. С. 149-155.

7. Иванов Н.Н. Полумарковские, процессы во временных стохастических сетях Петри'// АиТ. 1994. » 3. С. 117-127.

8. Иванов Н.Н. Временные стохастические сети Петри с неэкспоненциальными законами распределения времени срабатывания переходов // АиТ. 1994. » 9. С., 155-166.

9. Иванов Н.Н. Неэкспоненциальные временные стохастические сети Петри с ограниченной предысторией // АиТ. 1995. » 4. С. 145-156.

10. Ivanov N.N., Nonexponential Titaed Stochastic Pétri Nets // Proc. of the lOth. International Symposium on Computer and Information Science (ISCIS X), Turkey. V. I, Oct.-Hov. 19Ô5, pp. 43-50.

11. Иванов.H.H. Обобщенные временные стохастические сети Петри // АиТ, 1996. » 1.0. С, 156-167.

12. Иванов Н.Н. Временные стохастические сети Петри как средство моделирования процессов развития и ликвидации чрезвычайных ситуаций. В кн.: "Проблемы управления в чрезвычайных ситуациях. Четвертая международная конференция. Москва, 1997. Тезисы докладбв". С. 116-119.

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

В монографии [4] автору принадлежат следующие разделы: глава 2, параграфы 2-5, в которой излагаются оОшие результаты, относящиеся к формальным системам типа ЯЭП, свойства правильных нормализованных ФС, .алгоритмы анализа конечных источников с помощью ЯЭП, глава 3 и глава 6, параграфы 3-4. В работах- [1,- 2] автору принадлежит разработка принципов построения ЯЭП с произвольными подстановками, в начале слов и алгоритм анализа источников с помощью ЯЭП.

44

J**Jt. Л/. Л», или.

г '^иум ВАК России |

ж. нке от" Ж" 19^ г., № ^

1фисудил ученуюстшерь

гора!:

!

!'5

наук |{

/Йа^АЬник управдеин^ ВАК России

«

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

На правах рукописи УДК 519.711.3

ИВАНОВ Николай Николаевич

МЕТОДОЛОГИЯ АНАЛИЗА ВРЕМЕННЫХ СТОХАСТИЧЕСКИХ СЕТЕЙ ПЕТРИ И ЕЕ ИСПОЛЬЗОВАНИЕ ПРИ ИССЛЕДОВАНИИ И МОДЕЛИРОВАНИИ ДИСКРЕТНЫХ СИСТЕМ

Специальность 05.13.16: "Применение вычислительной техники,

математического моделирования и математических методов в научных исследованиях"

Диссертация на соискание ученой степени доктора технических наук

Научный консультант д.т.н., проф. Бочаров П.П.

¿Я

МОСКВА - 1997 г.

Оглавление

Введение ......................................................5

Глава 1. Общие понятия ...................................................................13

1.1. Обзор проблемы ..................................................................13

1.2. Моделирование дискретных систем

с помощью ВССП ...................................................22

1.3. Случайные процессы смен разметок в ВССП...........28

Глава 2. Простые временные стохастические сети Петри

с ограниченной предысторией ..................................................48

2.1. Основные понятия ..............................................................48

2.2. ВССП с ограниченной предысторией ..............................54

2.3. Закон распределения остаточного

времени срабатывания переходов ..................................59

2.4. Условия существования единственного положительного возвратного класса во

вложенной цепи Маркова ..................................................65

2.5. Предельное распределение вероятностей

достижимых разметок ........................................................71

2.5. Пример вычисления предельного распределения .... 72

2.6. Заключительные замечания ..............................................77

Глава 3. Неэкспоненциальные временные стохастические

сети Петри с ограниченной предысторией (общий

случай) ..........................................................................80

3.1. Постановка задачи ............................................................80

3.2. Расчетные зависимости ....................................................82

3.3. Пример ........................................................................96

3.4. Заключительные замечания ..............................................104

Глава 4. Примеры применения методики исследования

ВССП для анализа технических устройств ............. 106

4.1. Модель взаимодействия процессоров

и блока памяти ..................................................106

4.1.1. Постановка задачи ..............................................106

4.1.2. Случай г = 0 ......................................................109

4.1.3. Случай 0 < г < да..............................................118

4.1.4. Двойственная задача ..........................................128

4.1.5. Случай детерминированного обслуживания .. 130

4.1.6. Модель распределенного обслуживания ..........135

4.2. Модель обслуживания в циклической локальной

сети ......................................................................................141

4.2.1. Постановка задачи ..............................................141

4.2.2. Вычисление предельного распределения .... 145 Глава 5. Условия существования предельного

распределения вероятностей разметок в ВССП ....................155

5.1. Введение ..............................................................................155

5.2. Уравнения для стационарных вероятностей .........158

5.3. Необходимые условия существования предельных распределений ....................................................................161

5.4. Случай неэкспоненциальных ВССП ..................................169

5.5. Примеры................................................................................169

Глава 6. Алгебраические методы решения проблемы

отсутствия тупиковых разметок в сетях Петри ..................178

6.1. Введение ..............................................................................178

6.2. Методика исследования ....................................................182

6.3. Пример применения метода ..............................................190

6.4. Сводные результаты ..........................................................195

Глава 7. Языки эквивалентных преобразований ........................196

7.1. Формальные системы - аппарат описания

регулярных множеств ............................................196

7.2. Языки эквивалентных преобразований ..........................199

7.3. Отношение эквивалентности Ек ....................................207

7.4. Алгоритмы анализа источников (автоматов) ..............211

Заключение ......................................................221

Список литературы..................................................................................226

Введение

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

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

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

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

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

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

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

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

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

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

Научная новизна диссертации заключается в разработке и математическом обосновании комплекса новых методов

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

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

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

Реализация результатов работы. Методы анализа ВССП, разработанные в диссертации, нашли применение в ряде практических разработок, проведенных под руководством автора:

- в АО "Москвич" на этапе разработки технического задания на проектирование подсистемы оперативного управления цехом сварки автомобильных кузовов;

- в НПО "Казсельхозмеханизация" при разработке подсистем АСУ сельскохозяйственного предприятия в части создания моделей, методов планирования и оперативного управления грузовыми перевозками сельскохозяйственной продукции на типовом с/х предприятии, а также при моделировании процессов переработкх4 сельскохозяйственной продукции, поступающей на крупные перерабатывающие предприятия.

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

- Международный семинар ученых стран-членов СЭВ "Разработка общей теории автоматов" (Суздаль, 1985 г.);

- 10-й Международный Симпозиум по вычислительной технике и информатике (13С13 X, Турция, 1995 г.);

- XXXV Школа-семинар по теории релейных устройств и конечных автоматов им. М.А.Гаврилова (Москва, 1996 г.);

Общемосковский семинар по логическому моделированию (Москва, 1996 г.);

IV Международная Конференция "Проблемы управления в чрезвычайных ситуациях (Москва, 1997 г.);

Научный семинар кафедры теории вероятностей и математической статистики Российского Университета Дружбы Народов (Москва, 1996, 1997 г.г.), а также на ряде других семинаров и совещаний.

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

Структура и объем работы. Диссертация состоит из введения, семи глав, заключения и списка литературы. Общий объем работы составляет 241 стр. машинописного текста, 41 рисунок, 9 таблиц. Список литературы содержит 128 работ.

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

Как показывается в главе 2 диссертации, такой подход осуществим для некоторого класса ВССП, названных там ВССП с ограниченной предысторией. Разработана методика, позволяющая эффективно определить принадлежность произвольно заданной ВССП указанному классу. В основу методики легли результаты, полученные автором в 80-х г.г. при разработке алгоритмов анализа поведения конечных источников (обобщенное понятие конечного автомата) с помощью языков эквивалентных преобразований (ЯЭП). Эта методика позволяет с максимальной полнотой выявить регенерирущие свойства случайного процесса смен разметок в ВССП.

Для ВССП с ограниченной предысторией в случае существования единственного положительного возвратного класса во вложенной в моделирующий СППМП цепи Маркова представляется возможным с

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

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

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

В главе 4 методика анализа ВССП находит применение в примерах анализа некоторых технических устройств. На этих примерах удается показать особенности предлагаемого метода, провести сравнение получаемых результатов с результатами, получаемыми для аналогичных устройств другими методами (например, используемыми в теории массового обслуживания), а также с результатами, доставляемыми имитационным моделированием. Предлагается на примере анализа циклической локальной вычислительной сети методика приближенного анализа ВССП.

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

Глава 6 посвящена проблеме обнаружения достижимых тупиковых разметок в сетях Петри. Эта задача имеет существенное значение, выходящее за рамки проблематики теории ВССП. Однако, ее решение в данной работе было подчинено стремлению вооружить пользователей инструментом, обеспечивающим гарантию того, что исследуемые ими ВССП свободны от поглощающих состояний, что особенно важно при имитационных подходах к анализу предельных свойств поведения ВССП при t-> оо {Ь - время).

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

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

Глава 1. Общие понятия

1.1. Обзор проблемы

Сети Петри возникли в начале 60-х годов [117, 118] в связи с потребностями прежде всего вычислительной техники в таком аппарате моделирования дискретных систем, который позволял бы адекватно описывать причинно-следственные связи в этих системах, а также возможные в них параллельно протекающие асинхронные процессы и их взаимодействие. Вслед за появлением упомянутых публикаций началось бурное развитие теории сетей Петри, охватившее все самые важные математические аспекты их исследования и анализа. Усилиями многих авторов и исследователей была создана специальная дисциплина - теория сетей Петри в современном представлении, занявшае свое место в теории формальных языков, грамматик и автоматов [30, 35].

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