Методология анализа временных стохастических сетей Петри и ее использование при исследовании и моделировании дискретных систем тема диссертации и автореферата по ВАК РФ 05.13.16, доктор технических наук Иванов, Николай Николаевич

• Иванов, Николай Николаевич
• доктор технических наук
• 1997

Оглавление диссертации доктор технических наук Иванов, Николай Николаевич

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

случай)

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

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

3.3. Пример

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

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

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

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

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

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

4.1.2. Случай г = 0

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

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

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

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

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

сети

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

4.2.2. Вычисление предельного распределения

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

5.1. Введение

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

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

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

5.5. Примеры

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

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

6.1. Введение

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

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

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

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

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

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

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

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

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

Заключение

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

Введение диссертации (часть автореферата) на тему «Методология анализа временных стохастических сетей Петри и ее использование при исследовании и моделировании дискретных систем»

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Иванов, Николай Николаевич

Заключение

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

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

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

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

О, 1}, генерируемого графом разметок сети Петри, с помощью аппарата языков эквивалентных преобразований (ЯЭП).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования доктор технических наук Иванов, Николай Николаевич, 1997 год

СПИСОК ЛИТЕРАТУРЫ

1. Авен О.И., Турин H.H., Коган Я.А. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982.

2. Андронов A.M., Редько В.А. Анализ модели детерминированного циклического обслуживания абонентов при ординарных запросах // АВТ. 1984. № 4. С. 54-63.

3. Артамонов Г.Т., Брехов О.М. Аналитические вероятностные модели функционирования ЭВМ. М.: Энергия, 1978.

4. Артамонов Г.Т. Анализ производительности ЦВМ методами теории массового обслуживания. М.: Энергия, 1972.

5. Баруча-Рид А.Т. Элементы теории марковских процессов и их приложения. М.: Наука, 1969.

6. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. М.: Наука, 1989.

7. Бестужева И.И., Руднев В.В. Временные сети Петри. Классификация и сравнительный анализ (обзор проблемы) // АиТ. 1990. № 9. С. 3-21.

8. Бочаров П.П. Анализ бесприоритетной однолинейной системы с ограниченной очередью и заявками нескольких типов // Изв. АН СССР. Техническая Кибернетика. 1970. № 6. С. 101-105.

9. Бочаров П.П. О некоторых приближенных формулах для системы М | Gl | 1 | г < оо / В кн. "Модели информационных систем". М. : Наука. 1984. С.83-91.

10. Бочаров П.П., Печинкин A.B. Теория массового обслуживания. М.: Изд. РУДН, 1995.

11. Броди С.М., Погосян И.А. Вложенные стохастические процессы в теории массового обслуживания. Киев: Наукова думка, 1973.

12. Будинас Б.Л. Разрешимость проблемы достижимости для сетей Петри (обзор проблемы) // АиТ. 1988. № 11. С. 3-39.

13. Вентцель Е.С., Овчаров JI.A. Теория случайных процессов и ее инженерные приложения. М.: Наука, 1991.

14. Гаврилов А.Ф., Красильников Ю.П. Циклическое обслуживание с прямой информационной связью // АиТ. 1976. № 10. С. 17-22.

15. Гихман И.И., Скороход A.B. Теория случайных процессов. Т.Н. М.: Наука, 1973.

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

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

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

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

20. Иванов H.H. Алгебраический метод решения проблемы отсутствия тупиковых разметок в сетях Петри // АиТ. 1991. № 7. С. 125130.

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

22. Иванов H.H. Полумарковские процессы во временных стохастических сетях Петри // АиТ. 1994. № 3. С. 117-127.

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

24. Иванов H.H. Неэкспоненциальные временные стохастические сети Петри с ограниченной предысторией // АиТ. 1995. № 4. С. 145156.

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

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

27. Ильин В.П., Смирнов М.И. Модели процессов управления в вычислительных сетях на базе ингибиторных сетей Петри // АВТ. 1989. № 5. С. 66-69.

28. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение, 1979.

29. Королюк B.C., Турбин А.Ф. Полумарковские процессы и их приложения. Киев: Наукова думка, 197 6.

30. Котов В.Е. Сети Петри. М.: Наука, 1984.

31. Кратко М.И. Формальные исчисления Поста и конечные автоматы / В кн. Проблемы кибернетики, вып. 17. М.: Наука, 1966.

32. Мамиконов А.Г., Деметрович Я., Кульба В.В. и др. Использование сетей Петри при проектировании систем обработки данных. М. : Наука, 1988.

33. Мамиконов А.Г., Кульба В.В., Швецов А.Р. Модифицированные сети Петри. Препринт ИПУ АН СССР, Москва, 1991.

34. Минский М. Вычисления и автоматы. М.: Мир, 1971.

35. Питерсон Дж. Теория сетей Петри и моделирование систем. М. : Мир, 1984.

36. Райзер М. Оценка характеристик систем передачи данных // ТИИЭР. Вып. 70. № 2. 1982. С. 28-59.

37. Сильвестров Д.С. Полумарковские процессы с дискретным множеством состояний. М.: Советское радио, 1980.

38. Слепцов А.И., Юрасов A.A. Автоматизация проектирования управляющих систем гибких автоматизированных производств.

т/ч-т — г, • ФЛ-О-Т.1 пор

39. Сокол Ю.М. Оптимизация интерфейса параллельной общей памяти для многопроцессорных вычислительных систем // АиТ. 1993.

№ 5. С. 180-189.

40. Такач Л. Некоторые вероятностные задачи в телефонии. Сб. переводов "Математика". 4:6, 1960. С. 93-144.

41. Тербер К.Дж. Архитектура высокопроизводительных вычислительных систем. М.: Наука, 1985.

42. Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы: поведение и синтез. М.: Наука. 1970.

43. Черникова Н.В. Алгоритм для нахождения общей формулы неотрицательных решений системы линейных уравнений // Журн. вычисл. математики и мат. физики. 1964. Т.4. № 4. С. 733-738.

44. Черникова Н.В. Алгоритм для нахождения общей формулы неотрицательных решений системы линейных неравенств // Журн. вычисл. математики и мат. физики. 1965. Т.5. № 2. С. 334-337.

45. Чжун-Кай-Лай. Однородные цепи Маркова. М.: Мир, 1964.

46. Ширяев А.Н. Вероятность. М. : Наука, 1989.

47. Юдицкий С.А., Кутанов А.Т. Технология проектирования архитектуры информационно-управляющих систем. Препринт ИПУ РАН, Москва, 1993.

48. Юдицкий С.А., Покалев С.С. Логическое управление гибким интегрированным производством. Препринт ИПУ РАН, Москва, 1989.

49. Якубайтис Э.А. Архитектура локальных вычислительных сетей. Препринт ИЭВТ Р17. Рига: ИЭВТ АН ЛатвССР, 1981.

50. Ajmone Marsan М., Balbo M.G., Conte G., and Gregoretti F., Modeling bus contention and memory interference in a multiprocessor system 11 IEEE Trans, on Computers. V. C-32, No. 1, Jan. 1983, pp. 60-72.

51. Ajmone Marsan M., Balbo M.G., and Conte G., A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems // ACM Transactions on Computer Systems. V.2, No.l, May 1984, pp. 93-122.

52. Ajmone Marsan M., Balbo M.G., Bobbio A., Chiola G., Conte G., and Cumani A., On Petri nets with stochastic timing // Proc. Int. Workshop on timed Petri nets, Torino, Italy, 1985, pp. 80-87.

53. Ajmone Marsan M., Balbo M.G., Chiola G., and Conte G., Generalized stochastic Petri nets revisited: Random switches and priorities // Proc. Int. Workshop on Petri nets and Performance Models (PNPM'87), 1987, pp. 44-53.

54. Ajmone Marsan M., Balbo M.G., Chiola G., and Conte G., Modeling the software architecture of a prototype parallel rrta-

schine // Proc. SIGMETRICS'87 Conf., Banf, Alberta, Canada, May 1987.

55. Ajmone Marsan M., Balbo M.G., Chiola G., and Conte G., Generalised stochastic Petri nets: A definition at the net level and its implications // IEEE Trans. Software Eng. V. 19,

No. 2, 1993, pp. 89-107.

56. Ajmone Marsan M., Balbo M.G., and Conte G., Performance models of multiprocessor systems. Cambridge, MA: MIT Press, 1986.

57. Ajmone Marsan M. and Chiola G., On Petri Nets with Deterministic and Exponentially distributed firing times. In: Adv. in Petri Nets. Lecture Notes on Computer Science. V. 2 66, N.Y.: Springer Verlag, 1987, pp. 132-145.

58. Ajmone Marsan M., Donatelli S., and Neri F., GSPN models of Markovian multiserver multiqueue systems // Performance Evaluation, Elsevier, The Netherlands. V. 11, No. 4, 1990, pp. 227-240.

59. Ammar H., Huang Y.F., and Liu R., Analysis by Aggregation of the Generalized Stochastic Petri Nets with Application to Reliability/Maintainability and Fault Diagnosis // Proc. of the International Symposium on Circuits and Systems

(ISCAS'85), Kyoto, Japan, June 1985.

60. Ammar H., Islam M.R., and Deng S., Performability analysis of parallel and distributed algorithms // Proc. 3rd Int. Workshop on Petri Nets and Performance Models, Kyoto, Japan, Dec. 1989.

61. Ammar H. and Liu R., Hierarchical Models for Parallel Processings Systems using the Generalized Stochastic Petri Nets // Proc. of the 1984 International Conference on Parallel Processings, IEEE, 1984.

62. Attieh A., Brady M., Knottenbelt W., Kritzinger P.S., Functional and Temporal Analysis of Concurrent Systems // 16th Int. Conf. on Theory and Application of Petri nets, Turin, June 1995.

63. Balbo G., Chiola G., Franceschinis G., and Molinar Roet G., Generalized stochastic Petri nets for the performance evaluation of FMS // Proc. 1987 Int. Conf. Robotics Automat., Raleigh, NC, April 1987, pp. 1013-1018.

64. Balbo G., Chiola G., Bruell S.C., and Chen P., An example of modeling and evaluation of a concurrent program using coloured stochastic Petri nets: Lamport's fast mutual exclusion algorithm // IEEE Trans. Parallel Distributed Syst. V. 3,

No. 2, 1992, pp. 221-240.

65. Bause F., Queueing Petri Nets - A formalism for the combined qualitative and quantitative analysis of Systems // Proc. 5th Int. Workshop of Petri Nets and Performance Models, Toulouse, France, Oct. 1993.

66. Bause F., Kemper P., QPN-Tool for qualitative and quantitative analysis of Queueing Petri Nets, Lecture Notes on Computer Science. V. 794, Springer Verlag, 1994.

67. Beyaert B., Florin G., Lone P., Natkin S., Evaluation of computer systems dependability using stochastic Petri nets // Proc. of FTCS-11, Portland, Maine, 1981, pp. 85-94.

68. Bruno G. and Biglia P., Performance evaluation and validation of tool hadling in flexible manufactoring systems using Petri nets // Proc. Int. Workshop on Timed Petri Nets, Torino, Italy, 1985.

69. Buehi I. R., Regular canonical systems // Archiv fuer mathematische Logik und Grundlagenforschung. B. 6, H. 3-4, 1964.

70. Bux W., Truong H.L., Mean-delay approximation for ciclic-service queueing systems // Performance Evaluation, Elsevier, The Netherlands. V. 3, 1983.

71. Chiola G., Dutheillet C., Franceschinis G., and Haddad S., Stochastic well-formed coloured nets and multiprocessor modeling applications / In K. Jensen and G. Rozenberg, Eds., "High-Level Petri Nets. Theory and Application." N. Y.: Springer Verlag, 1991.

72. Chiola G., Dutheillet C., Franceschinis G., and Haddad S., Stochastic Well-Formed Coloured Nets and Symmetric Modeling Applications // IEEE Transactions on Computers. V. 42,

No. 11, 1993.

73. Chiola G., GreatSPN 1.5 Software Architecture // Proc. 5th Int. Conf. on Modeling Techniques and Tools for Computer Performance Evaluation, Torino, Italy, Feb. 1991, pp.117-132.

74. Chiola G., Simulation Framework for Timed and Stochasic Petri Nets // International Journal in Computer Simulation. V. 2, No. 2, 1991.

75. Choi H., Kulkarni V.G., and Trivedi K. S., Markov regenerative stochastic Petri nets // In: Performance'93. G. Iazeolla

and S.S. Lavenberg, Editors. Amsterdam: North-Holland, Sept.

1993.

76. Choi H., Kulkarni V. G., and Trivedi K. S., Markov Regenerative Stochastic Petri Nets // Performance Evaluation. V. 20,

1994, pp.337-357.

77. Choi H., Kulkarni V.G., and Trivedi K. S., Transient analysis of deterministic and stochastic Petri nets // In: Application and Theory of Petri nets, Lecture Notes in Computer Science. V. 691. Springer Verlag, 1993, pp. 166-185.

78. Ciardo G., Analysis of large stochastic Petri net models. Ph.D. thesis, Duke Univ., Durham, NC, 1989.

79. Ciardo G., Blakemore A., Chimento P.F.Jr., Muppala J., and Trivedi K. S. Automated generation and analysis of Markov reward models using stochastic rewards nets // In: "Linear Algebra, Markov Chains and Queueing Models", C. Meyer and R.J. Plemmons, Eds, V. 48 of IMA Volumes in Mathematics and its Applications. N.Y.: Springer Verlag, 1993, pp. 145-191.

80. Ciardo G., German R., and Lindemann C., A characterization of the stochastic process underlying a stochastic Petri net // IEEE Trans. Software Eng. V. 20, No. 7, 1994, pp. 506-515.

81. Ciardo G., Trivedi K. S., Muppala J., SPNP: stochastic Petri net package // Proc. 3rd Int. Workshop on Petri Nets and Performance Models (PNPM'89), IEEE Computer Society Press, 1989, pp. 142-151.

82. Cumani A., ESP - A Package for the Evaluation of Stochastic Petri Nets with Phase-Type Distributed Transition Times //

Proc. Int. Workshop on Timed Petri Nets, Torino, Italy, July 1985, pp. 144-151.

83. Diaz M., Modeling and Analysis of Communication and Cooperation Protocols using Petri Net based Models /'/' Computer Networks. V. 6, No. 6, 1982, pp. 419-441.

84. Dugan J.B. and Ciardo G., Stochastic Petri net analysis of a replicated file system // IEEE Trans. Software Eng. V. 15, No. 4, 1989, pp. 394-401.

85. Dugan J.B., Trivedi K.S., Geist R.M., and Nicola V.F., Extended stochastic Petri nets: applications and analysis // Performance'84, Elsevier Science Publishers B.V., North-Holland, 1984, pp.507-519.

86. Dutheillet C. and Haddad S., Aggregation and disaggregation of states in colored stochastic Petri nets: Application to a multiprocessor architectire //' Proc. 3rd Int. Workshop on Petri Nets and Performance Models (PNPM'89), Kyoto, Japan, Dec. 1989.

87. Florin G., Natkin S., Evaluation based upon stochastic Petri nets of the maximum throughput of a full duplex protocol / In: "Applications and Theory of Petri Nets" , Lecture Notes on Computer Science. V. 52. Springer Verlag, 1982, pp. 280288.

88. Garbe W., Kantelberg A., SimNet - ein Werkzeug fuer Modellierung und Simulation auf Basis stochastischer Petri-Netze, EMISA-Forum 1/1994.

89. German R., Kelling C., Zimmermann A., Hommel G., TimeNET - A toolkit for evaluating stochastic Petri nets with nonexponen-

tial firing times // Performance Evaluation, Elsevier, The Netherlands, V. 24, 1995, pp. 69-87.

90. German R., Lindemann C., Analysis of Stochastic Petri Nets by the Method of Supplementary Variables // Performance Evaluation, Elsevier, The Netherlands. V. 20, 1994, pp. 317335.

91. Ghanta S., On the Integration of Queueing Networks and Generalized Stochastic Petri Nets for the Performance Evaluation of Computer Sistems. Ph.D. Thesis, University of Minnesota, Dec. 1984.

92. Ghezzi C., Mandrioli D., Morasca S., Pezzi M., A unified High-Level Petri Net formalism for time-critical systems // IEEE Transactions on Software Engineering, February 1991.

93. Gouda M.M., Molloy M.K., Modeling and analysis of LAN protocols using labeled Petri nets // 6th European Workchop on Application and Theory of Petri Nets. Finland, June 1985.

94. Gressier E., A stochastic Petri net model for ethernet // Proc. Int. Workshop on Timed Petri Nets, Torino, Italy, Juli

1985.

95. Haas P.J., Shedler G.S., Regenerative stochastic Petri nets // Performance Evaluation, Elsevier, The Netherlands. V. 6,

1986, pp. 189-204.

96. Haas P.J., Shedler G.S., Stochastic Petri net representation of discretr event simulations // IEEE Trans. Software Eng. V. 15, No. 4, April 1989, pp. 381-393.

97. Ibe O.C. and Trivedi K. S., Stochastic Petri nets models of polling systems // IEEE J. Select. Areas Communic. V. 8, No. 9, Dec. 1990.

98. Ivanov N.N., Nonexponential Timed Stochastic Petri Nets // Proc. of the 10th International Symposium on Computer and Information Science (ISCIS X) , Turkey. V. I, Oct.-Nov. 1995, pp. 43-50.

99. Keller R., Shen X., Bochmann G. V., Macronet - A simple, yet expressive and flexible formalism for Business Modeling // Workshop, Proc. 15th Int. Conf. on Application and Theory of Petri Nets, Zaragoza, June 1994.

100. Keller R. K., Bochmann G., Petri Net based business modeling and simulation with the Macrotec environment // Handout at tool presentation at the 15th International Conference on Application and Theory of Petri Nets, Zaragoza, Spain, June 1994.

101. Keller R. K., Lajoie R., Ozkan M., Saba F., Shen X., Tao Tao, Bochmann G., The Macrotec toolset for CASE-based business modeling // Proc. of the 6th International Workshop on Computer-Aided Software engineering, Singapore, July 1993.

102. Kelling C., TimeNET-SIM - a parallel Simulator for Stochastic Petri Nets // Proc. 28th Annual Simulation Symp., Phoenix, Arizona, USA, 1995.

103. Klas G., Lepold R., TOMSPIN, a Tool for Modeling with Stochastic Petri Nets // Proc. of the 6th Annual European Computer Conference, Le Hague, Netherlands, 1992, pp. 618-623.

104. Lindemann C., DSPNexpress: A Software package for the efficient solution of deterministic and stochastic Petri Nets // Proc. 6th International Conf. on Modeling Techniques and Tools for Computer Performance Evaluation, Edinburgh, Great Britain, 1992.

105. Lindemann C., Performance Modeling using DSPNExpress // Lecture Notes on Computer Science. V. 72 9, Springer Verlag, 1993.

106. Lindemann C., An Improved Numerical Algorithm for Calculating Steady-State Solutions of Deterministic and Stochastic Petri Net Models // Performance Evaluation, Elsevier, The Netherlands. V. 18, 1993, pp. 79-95.

107. Lindemann C., Stochastic Modeling using DSPNexpress, Oldenbourg Verlag, 1994.

108. Lindemann C., Ciardo G., German R., and Hommel G., Perfor-mability Modeling of an Automated Manufacturing System with Deterministic and Stochastic Petri Nets // Proc. IEEE Int. Conf. on Robotics and Automation, Atlanta, Georgia, USA, 1993, pp. 576-581.

109. Lin C., Marinescu D. C., Stochastic High-Level Petri Nets and Applications / In: K. Jensen, G. Rozenberg (eds) "HighLevel Petri Nets. Theory and Application", 1991.

110. Meyer J.F., Movaghar A., and Sanders W. H. Stochastic activity networks: structure, behavior and application // Proc. Int. Workshop on Timed Petri Nets, Torino, Italy, July 1985.

111. MASI Laboratory: MAPS. Modeling, Analysis and Prototyping of parallel Systems // XIII Int. Conf. on Theory and Application of Petri Nets, Sheffield, U.K., June 1992.

112. Molloy M.K., Performance analysis using stochastic Petri nets // IEEE Transactions on Computers. V. C-31, No.9, Sept. 1982, pp. 913-917.

113. Molloy M.K., Discrete time stochastic Petri nets // IEEE Transactions on Software Engineering. V. SE-11, No.4, April 1985, pp.417-423.

114. Molloy M. K., A CAD Tool for Stochastic Petri Nets // Proc. 1986 Fall Joint Computer Conf., 1986.

115. Murata T., State Equations, Controllability and Maximal Matching of Petri Nets // IEEE Trans. Automat. Control. V.AC-22. No.3, 1977, pp. 412-416.

116. Natkin S., Les Reseaux de Petri Stochastiques et leur Application a l'Evaluatin des Systèmes Informatiques. Doctoral dissertation, Conservatoire National des Arts et Metiers, Paris, 1980.

117. Petri C., Kommunikation mit Automaten, Ph. D. dissertation, University of Bonn, Bonn, West Germany, 1962.

118. Petri C., Fundamentals of a Theory of Asynchronous Information Flow, Information Processing 62 // Proceedings of the 1962 Congress, Amsterdam: Nort-Holland, August 1962, pp. 386390.

119. Ramamoorthy C.V. and Ho G.S., Performance evaluation of asynchronous concurrent systems using Petri nets. // IEEE Trans. Software Eng. V. SE-6, Sept. 1980, pp. 440-449.

120. Ramchandani C., Analysis of asynchronous concurrent systems by timed Petri nets. Project MAC-TR-120, Massachussets Institute of Technology, Cambridge MA, 1974.

121. Shapiro S.D., A stochastic Petri net with application to modeling occupancy times for concurrent task systems // Networks. V.9, 1979, pp. 375-379.

122. Sifakis J., Use of Petri nets for performance evaluation / In: "Measuring, modeling and evaluation computer systems". Nort-Hoiland, 1977, pp. 75-93.

123. Varpaaniemi K., Efficient Detection of Deadlocks of Petri Nets, Helsinki University of Technology, Digital Systems

j-jaJw^jL ci Lwi) adpul L u , uuluijci ± y y .

124. Wong C.Y., Dillon T.S., and Forward K.E., Timed places Petri nets with stochastic representation of place time // Proc. Int. Workshop on Timed Petri Nets, Torino, Italy, 1985, pp. 96-103.

125. Zenie A., Colored Stochastic Petri Nets // Proc. Int. Workshop on Timed Petri Nets, Torino, Italy, 1985, pp. 262-271.

126. Zijal R., German R., A New Approach to Discrete Time Stochastic Petri Nets // Proc. 11th Int. Conf. on Analysis and Optimization of Systems, Sophia-Antipolis, France, 1994, pp. 198-204.

127. Zuberek W.M., Timed Petri nets and preliminary performance evaluation // Proc. IEEE 7th Ann. Symp. Comput. Arch., 1980, pp. 89-96.

128. Zuberek W.M., Performance evaluation using extended timed Petri nets // Proc. Int. Workshop on Timed Petri Nets, Torino, Italy, 1985, pp. 272-278.