Введение к работе
Актуальность темы диссертации. За последнее десятилетие во многих областях науки и техники временные'сети Петри, в которых переходы сети ыогут срабатывать по прошествии определенного времени после возникновения условий срабатывания, нашли широкое применение как инструмент моделирования дискретных процессов. С помощью таких сетей проводится исследование и моделирование элементов и узлов вычислительных машин и систем, процессов управления и сетевых протоколов в локальных вычислительных сетях, систем резервирования, различного реда параллельных процессов в технических устройствах, производственных' системах, экологии, микробиологии, сельскохозяйственном производстве и др.
Особую роль в этом мощном аппарате играют временные стохастические сати Петри (ВССГІ), применение которых целесообразно при моделировании объектов, в которых временные параметру непредсказуемы и являются в общем случае случайными величинами с известными законами распределения. Как правило, в существующих разновидностях ВССП принимается экспоненциальный закон расределения времени срабатывания переходов, что связано в первую очередь с простотой анализа таких ВССП. Поділена истинных законов распределения экспоненциальным может приводить к недопустимым погрешностям моделїфования, а в ряде случаев - к качественно несостоятельным моделям, траектории которых не соответствуют реальным процессам в моделируемых объектах. Существуют также подходы, позволящие применять ВССП с неэкспоненциальными временными переходами, однако, при этом вынуждено накладываются существенные ограничения на структурные свойства сетей с целью облегчения задач их анализа.
Потребности практики моделирования дискретных систем делают весьма актуальной разработку достаточно общей теории ВССП, которая охватывает широкий круг вопросов, связанных как с аналитическим так и с имитационным исследованием случайных процессов а ВССП с произвольными законами распределения времени срабатывания переходов.
Наиболее важным из них является выявление класса ВССП, характеризуемого минимальными ограничениями на структурные свойства сетей, при которых возможно проведение аналитичес-
кого исследования, и раэраСотка методики этого исследования, обеспечивающего наименьшие стоимостные и временные затраты на моделирование.
Потребности как аналитического так и имитационного подходов к исследованию ВССП определили актуальность выявления методов экспресс-анализа сетей на отсутствие достижимых тупиковых разметок, которые в случайном процессе смен разметок могут играть роль поглощающих состояний. Эти методы актуальны также и в общем комплексе проблем, связанных с верификацией моделей, построенных на основе сетей Петри.
В случае неограниченности моделирующей ВССП ее аналитическое исследование, как правило, невозможно. Однако, ь случае существования предельного распределения вероятностей достижимых разметок может Сыть применен имитационный подход. В этой связи актуальны методы экспресс-анализа, предшествующие имитационному моделированию, 'ставящие задачей определение необходимых условий существования такого распределения.
Целью диссертационной работы является разработка методологии анализа ВССП, охватывающей следующий круг вопросов: во-первых, выявление максимально широкого класса ВССП, для которого было бы возможно проведение аналитического исследования при произвольных законах распределения времени срабатывания переходов, и разработка методики аналитического" исследования ВССП этого класса, во-вторых, разработка алгоритмов экспресс-анализа (без построения графа разметок) сетей Петри, с целью получения ответа на вопрос о существовании достижимых тупиковых разметок и, в-третьих, раэраСотка простого метода доказательства отсутствия предельного распределения вероятностей достижимых разметок в ВССП произвольного вида.
Методи исследования. Основными методами решения поставленных в диссертации задач являются методы теории вероятностей, теории случайных процессов и теории сетей Петри. При выявлении свойств регенерируемости ВССП использован аппарат теории конечных автоматов, при разработке методов обнаружения тупиков в сетях Петри - помимо теории сетей Петри, методы булевой и линейной алгебры,.при исследовании сетевых моделей конкретных технических объектов, кроме перечисленных выше - методы теории систем массового обслуживания и комбинаторного анализа.
Пкут^хя тіорї-вт диссертации заключается в разработке и математическом обсснсзгли-.и коютлекса нозых методов аналитического исследования ВССП с произвольными закопают распределения случайного времени срабатывания переходов.
Пріптгазсхал ц«япвет% раСэти. Методы, представленные в диссертации, позволяет научно обоснованно, с высокой точностью и с минимальными затратами решать задачи исследования и анализа моделей процессов, построенных на базе ВССП, что особенно важно для начальных этапов проектирования дискретних ооектов. Эти методи, являясь инструментом аналитического исследования ВССП обгаего вида, призваны также служить математической поддерткои имитационного подхода к исследование ВССП, поскольку только развитый теоретический фундамент позволяет избегать методические ошибки в имитационном эксперименте и построить для такового обоснованную стратегия. Дл.т ряда вязких практических задач моделирования дискретних процессов показано, как может быть применена методология анализа ВССП, предложенная в работе, для получения характеристик этих процессов.
Лостсаоряотаь іїауави пеяояакий, зыволоа и практичве-пхж рї»угвякїдт«5«й подтверждается корректным обоснованием, строгими математическіазі доказательствами формулируемых утверждений, результата;::! расчетов характеристик конкретных моделей и сраянением их с результатами имитационного моделирования, а также п некоторых частных случаях с результатами, получас'лляї при расчете аналогичных характеристик другими известными методами.
Рпа?г«31?я р&й7.гчтптоз рпЗсти. Методы анализа ВССП, разработанные в диссерташяі, нашли применение в ряде практических разработок, проведенных под руководством автора:
в ЛО "Москвич" на зтапе разработки технического задания на проектирование подсистемы оперативного управления цехом сварки автомобильных кузовов;
в НПО "Казсельхозмеханизация" при разработке подсистем АСУ сельскохозяйственного предприятия в части создания моделей, методов планирования и оперативного утгравлєігия грузовыми перевозками сельскохозяйственной продукции на типовом с/х предприятии, а также при моделировании процессов переработки сельскохозяйственной продукции, поступатаей на крупные перерабатывающие предприятия.
Аппробсцил работи. Основные положения и результаты работы докладывались на следующих семинарах, школах и симпозиумах:
Международный семинар ученых стран-членов СЭВ "Разработка общей теории автоматов" (Суздаль, 1985 г.);
10-й Международный Симпозиум по вычислительной технике и информатике (ISGIS X, Турция, 199S г.);
XXXV Школа-сеЬй'шар по теории релейных устройств и конечных автоматов им. М.А.Гаврилова (Москва, 1Э96 г.);
Общемосковский семинар по логическому моделированию (Москва, 1996 г.);
IV Международная Конференция "Проблемы управления в чрезвычайных ситуациях (Косква, 1997 г.);
Научный семинар кафедры теории вероятностей и математической статистики Российского Университета Дружбы Народов (Москва, 1996, 1997 г.г.),
а также на ряде других семинаров и совещаний.
Публикации. В изданиях, рекомендуемых ВАК для опубликования научных результатов докторских диссертаций, непосредственно по теме диссертации опубликовано 12 печатных работ, в том числе одна монография.
Структура и объем работы. Диссертация состоит из введения, семи глав, заключения и списка литературы. Общий объем работы составляет 241 стр. машинописного текста, 41 рисунок, 9 таблиц. Список литературы содержит 128 работ.
