|
|
Непрерывно-стохастические модели (Q-схемы)При непрерывно-стохастическом подходе в качестве типовых математических схем применяется система массового обслуживания (англ. queueing system), которые будем называть Q-схемами. Системы массового обслуживания представляют собой класс математических схем, разработанных в теории массового обслуживания и различных приложениях для формализации процессов функционирования систем, которые по своей сути являются процессами обслуживания. В качестве процесса обслуживания могут быть представлены различные по своей физической природе процессы функционирования экономических, производственных, технических и других систем, например потоки поставок продукции некоторому предприятию, потоки деталей и комплектующих изделий на сборочном конвейере цеха, заявки на обработку информации ЭВМ от удаленных терминалов и т. д. При этом характерным для работы таких объектов является случайное появление заявок (требований) на обслуживание и завершение обслуживания в случайные моменты времени, т. е. стохастический характер процесса их функционирования. Остановимся на основных понятиях массового обслуживания, необходимых для использования Q-схем, как при аналитическом, так и при имитационном. В любом элементарном акте обслуживания можно выделить две основные составляющие: 1. ожидание обслуживания заявки; 2. собственно обслуживание заявки. Это можно изобразить в виде некоторого i -гo прибора обслуживания Пi (рис. 2.), состоящего из накопителя заявок Нi, в котором может одновременно находиться
Рис. 2. На каждый элемент прибора обслуживания Пi, поступают потоки событий: в накопитель Hi — поток заявок wi на канал Ki — поток обслуживании ui. Потоком событий называется последовательность событий, происходящих одно за другим в какие-то случайные моменты времени. Различают потоки однородных и неоднородных событий. Поток событий называется однородным, если он характеризуется только моментами поступления этих событий (вызывающими моментами) и задается последовательностью Однородный поток событий также может быть задан в виде последовательности промежутков времени между n -м и (n—1) -м событиями { tn }, которая однозначно связана с последовательностью вызывающих моментов { tn }, где Потоком неоднородных событий называется последовательность поток, в котором события разделены интервалами времени t1, t2, …, которые вообще являются случайными величинами. Пусть интервалы t1, t2,.., независимы между собой. Тогда поток событий называется потоком сограниченным последействием. Пример потока событий приведен на рис. 3., где обозначено Тj — интервал между событиями (случайная величина); Тн — время наблюдения, Tс — момент совершения события.
рис. 3. Интенсивность потока можно рассчитать экспериментально по формуле
где N — число событий, произошедших за время наблюдения Тн. Если Тн =const или определено какой-либо формулой Случайные потоки бывают: 1. ординарными - когда вероятность одновременного появления 2-х и более событий равна нулю. Поток событий называется ординарным, если вероятность того, что на малый интервал времени Dt, примыкающий к моменту времени t, попадает больше одного события Р>1 (t, Dt), пренебрежительно мала по сравнению с вероятностью того, что на этот же интервал времени Dt попадает ровно одно событие P1 (t, Dt), т. е. P1 (t, Dt)» Р>1 (t, Dt). 2. стационарными - когда частота появления событий постоянная. Стационарным потоком событий называется поток, для которого вероятность появления того или иного числа событий на интервале времени t зависит лишь от длины этого участка и не зависит от того, где на оси времени взят этот участок. 3. без последействия - когда вероятность не зависит от момента совершения предыдущих событий. Обычно при моделировании различных систем применительно к элементарному каналу обслуживания Кi можно считать, что поток заявок Заявки, обслуженные каналом Кi и заявки, покинувшие прибор Пi, по различным причинам необслуженными (например, из-за переполнения накопителя Нi), образуют выходной поток В практике моделирования систем, имеющих более сложные структурные связи и алгоритмы поведения, для формализации используются не отдельные приборы обслуживания, а Q-схемы, образуемые композицией многих элементарных приборов обслуживания Пi ((сети массового обслуживания). Если каналы Кi различных приборов обслуживания соединены параллельно, то имеет место многоканальное обслуживание (многоканальная Q-схема), а если приборы Пi и их параллельные композиции соединены последовательно, то имеет место многофазное обслуживание (многофазная Q-схема). Таким образом, для задания Q-схемы необходимо использовать оператор сопряжения R, отражающий взаимосвязь элементов структуры (каналов и накопителей) между собой. Связи между элементами Q-схемы изображают в виде стрелок (линий потока, отражающих направление движения заявок). Различают разомкнутые и замкнутые Q-схемы. В разомкнутой Q-схеме выходной поток обслуженных заявок не может снова поступить на какой-либо элемент, т. е. обратная связь отсутствует. в замкнутых Q-схемах имеются обратные связи, по которым заявки двигаются в направлении, обратном движению вход-выход. Для задания Q-схемы также необходимо описать алгоритмы ее функционирования, которые определяют набор правил поведения заявок в системе в различных неоднозначных ситуациях. В зависимости от места возникновения таких ситуаций различают алгоритмы (дисциплины) ожидания заявок в накопителе Нi, и обслуживания заявок каналом Кi каждого элементарного обслуживающего прибора Пi Q-схемы. Неоднородность заявок, отражающая процесс в той или иной реальной системе, учитывается с помощью введения классов приоритетов. В зависимости от динамики приоритетов в Q-схемах различают статические и динамическиеприоритеты. Статические приоритеты назначаются заранее и не зависят от состояний Q-схемы, т. е. они являются фиксированными в пределах решения конкретной задачи моделирования. Динамические приоритеты возникают при моделировании в зависимости от возникающих ситуаций. Исходя из правил выбора заявок из накопителя Hi на обслуживание каналом Кi можно выделить относительные и абсолютныеприоритеты. Относительный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель Нi ожидает окончания обслуживания предшествующей заявки каналом Кi и только после этого занимает канал. Абсолютный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель Нi прерывает обслуживание каналом Кi заявки с более низким приоритетом и сама занимает канал (при этом вытесненная из Кi заявка может либо покинуть систему, либо может быть снова записана на какое-то место в Нi). При рассмотрении алгоритмов функционирования приборов обслуживания Пi (каналов Кi и накопителей Нi) необходимо также задать набор правил, по которым заявки покидают Нi и Кi, для Нi — либо правила переполнения, по которым заявки в зависимости от заполнения Нi, покидают систему, либо правила ухода, связанные с истечением времени ожидания заявки в Нi, для Кi — правила выбора маршрутов или направлений ухода. Кроме того, для заявок необходимо задать правила, по которым они остаются в канале Кi или не допускаются до обслуживания каналом Кi т. е. правила блокировок канала. При этом различают блокировки Кi по выходу и по входу. Весь набор возможных алгоритмов поведения заявок в Q-схеме можно представить в виде некоторого оператора алгоритмов поведения заявок А. Таким образом, Q-схема, описывающая процесс функционирования системы массового обслуживания любой сложности, однозначно задается в виде При ряде упрощающих предположений относително подмножеств входящих потоков W и потоков обслуживания U (выполнение условий стационарности, ординарности и ограниченного последействия) оператора сопряжения элементов структуры R (однофазное одноканальное обслуживание в разомкнутой системе), подмножества собственных параметров Н (обслуживание с бесконечной емкостью накопителя), оператора алгоритмов обслуживания заявок А (бесприоритетное обслуживание без прерываний и блокировок) для оценки вероятностно-временных характеристик можно использовать аналитический аппарат, разработанный в теории массового обслуживания.
Лекция № 7 «Сетевые и комбинированные модели» . Содержание
3. Сетевые модели (N-схемы) 4. Комбинированные модели (A-схемы) Сетевые модели (N-схемы) В практике моделирования объектов часто приходится решать задачи, связанные с формализованным описанием и анализом причинно-следственных связей в сложных системах, где одновременно параллельно протекает несколько процессов. Самым распространенным в настоящее время формализмом, описывающим структуру и взаимодействие параллельных систем и процессов, являются сети Петри (англ. Petri Nets), предложенные К. Петри. Теория сетей Петри развивается в нескольких направлениях: 1. разработка математических основ, 2. структурная теория сетей, 3. различные приложения (параллельное программирование, дискретные динамические системы и т. д.). Формально сеть Петри (N-схема) задается четверкой вида
где В — конечное множество символов, называемых позициями D — конечное множество символов, называемых переходами, I — входная функция (прямая функция инцидентности) О — выходная функция (обратная функция инцидентности), Таким образом, входная функция I отображает переход dj в множество входных позиций
Аналогично, для каждого перехода
Графически N -схема изображается в виде двудольного ориентированного мультиграфа, представляющего собой совокупность позиций и переходов (рис. 1).
Рис. 1. Графическое изображение N-схемы Как видно из этого рисунка, граф N-схемы имеет два типа узлов: позиции и переходы, изображаемые 0 и 1 соответственно. Ориентировочные дуги соединяют позиции и переходы, причем каждая дуга направлена от элемента одного множества (позиции или перехода) к элементу другого множества (переходу или позиции). Граф N-схемы является мультиграфом, так как он допускает существование кратных дуг от одной вершины к другой. Приведенное представление N-схемы может использоваться только для отражения статики моделируемой системы (взаимосвязи событий и условий), но не позволяет отразить в модели динамику функционирования моделируемой системы. Для представления динамических свойств объекта вводится функция маркировки (разметки) Маркировка М есть присвоение неких абстрактных объектов, называемых метками (фишками), позициям N-схемы, причем количество меток, соответствующее каждой позиции, может меняться. При графическом задании N-схемы разметка отображается помещением внутри вершин-позиций соответствующего числа точек (когда количество точек велико, ставят цифры). Маркированная (размеченная) N-схема может быть описана в виде пятерки Функционирование N-схемы отражается путем перехода от разметки к разметке. Начальная разметка обозначается как Срабатывание перехода изменяет разметку сети М(b) = (М(b1), М(b2),..., M(bn))2 на разметку М¢(b) по следующему правилу: M'(b) = M(b)-I(dj) + O(dj) т. е. переход dj изымает по одной метке из каждой своей входной позиции и добавляет по одной метке в каждую из выходных позиций.
Рис. 2. Пример функционирования размеченной N-схемы Важной особенностью моделей процесса функционирования систем с использованием типовых N-схем является простота построения иерархических конструкций модели. С одной стороны, каждая N-схема может рассматриваться как макропереход или макропозиция модели более высокого уровня. С другой стороны, переход, или позиция N-схемы, может детализироваться в форме отдельной подсети для более углубленного исследования процессов в моделируемой системе S. Типовые N-схемы на основе обычных размеченных сетей Петри пригодны для описания в моделируемой системе S событий произвольной длительности. В этом случае модель, построенная с использованием таких N-схем, отражает только порядок наступления событий в исследуемой системе S. Для отражения временных параметров процесса функционирования моделируемой системы S на базе N-схем используется расширение аппарата сетей Петри: временные сети, E -сети.   ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...  ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...  Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...  Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
заявок, где 
—емкость i -го накопителя, и канала обслуживания заявок (или просто канала) Ki
, где tn — момент наступления n -го события — неотрицательное вещественное число.
, 
, to = 0, т. е. t1 = t1
, где tn — вызывающие моменты; fn — набор признаков события. Например, применительно к процессу обслуживания для неоднородного потока заявок могут быть заданы принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала и т. п.
, то поток называется детерминированным. Иначе поток называется случайным.
, т. е. интервалы времени между моментами появления заявок (вызывающие моменты) на входе Ki образует подмножество неуправляемых переменных, а поток обслуживания 
, т. е. интервалы времени между началом и окончанием обслуживания заявки, образует подмножество управляемых переменных.
, т. е. интервалы времени между моментами выхода заявок образуют подмножество выходных переменных.
.
,
,
, 
;
;
.
, а выходная функция О отображает переход dj в множество выходных позиций 
. Для каждого перехода 
можно определить множество входных позиций перехода I(dj) и выходных позиций перехода О(dj) как
вводятся определения множества входных переходов позиции I(bi) и множества выходных переходов позиции O(bi):
.
.
и является совокупностью сети Петри и маркировки М.
. Смена разметок происходит в результате срабатывания одного из переходов 
, где 
, - разметка позиции bi. Переход dj для которого выполняется указанное условие, определяется как находящийся в состоянии готовности к срабатыванию или как возбужденный переход.
