Модель обслуживания машинного парка представляет собой модель замкнутой системы массового обслуживания: интенсивность l входящего потока заявок зависит от состояния системы, причем источник требований является внутренним и генерирует ограниченный поток заявок.
Пусть машинный парк состоит из N машин и обслуживается бригадой R техников (N > R), причем каждая машина может обслуживаться только одним техником. Здесь машины являются источниками требований (заявок на обслуживание), а техники – обслуживающими каналами. Интенсивность зависит от того, сколько машин в данный момент находится в эксплуатации (N – k) и сколько машин обслуживается или стоит в очереди, ожидая обслуживания (k). Общий (суммарный) входящий поток имеет интенсивность (N – k)l.
Требование, поступившее в систему в момент, когда свободен хотя бы один канал, немедленно идет на обслуживание. Если требование застает все каналы занятыми обслуживанием других требований, то оно не покидает систему, а становится в очередь и ждет, пока один из каналов не станет свободным. Таким образом, в замкнутой системе массового обслуживания входящий поток требований формируется из выходящего.
Состояние Sk системы характеризуется общим числом требований, находящихся на обслуживании и в очереди, равным k. Для рассматриваемой замкнутой системы, очевидно, k = 0, 1, 2,..., N. При этом если система находится в состоянии Sk, то число объектов, находящихся в эксплуатации, равно (N – k).
Если l – интенсивность потока требований в расчете на одну машину, то:
;
.
Система алгебраических уравнений, описывающих работу замкнутой СМО в стационарном режиме, выглядит следующим образом (y = l/m):
,
Решая данную систему, находим вероятность k -гo состояния:
.
Величина P 0 определяется из условия нормирования 
полученных результатов по формулам для Pk, k = 0, 1, 2,..., N. Определим следующие вероятностные характеристики системы:
- среднее число требований в очереди на обслуживание:
;
- среднее число требований, находящихся в системе (на обслуживании и в очереди):
;
- среднее число техников (каналов), простаивающих из-за отсутствия работы:
;
- коэффициент простоя обслуживаемого объекта (машины) в очереди:
;
- коэффициент использования объектов (машин):
;
- коэффициент простоя обслуживающих каналов (техников):
;
- среднее время ожидания обслуживания (время ожидания обслуживания в очереди):
.
5. Сетевые модели (N -схемы). Сети Петри
5.1. Теоретические основы сетей Петри: принципы построения, алгоритмы поведения
Сети Петри были разработаны и используются для моделирования систем, которые содержат взаимодействующие параллельные компоненты, например аппаратное и программное обеспечение ЭВМ, гибкие производственные системы, а также социальные и биологические системы.
Введение в теорию комплектов
Математическим аппаратом сетей Петри является теория комплектов (естественное расширение теории множеств). Как и множество, комплект является набором элементов из некоторой области. В отличие от множества, где элемент либо является элементом множества, либо нет, в комплект элемент может входить заданное число раз.
Основным понятием теории комплектов является функция числа экземпляров: #(x, B) – число x в B, т.е. число экземпляров элемента x в B.
Элемент х является членом комплекта B, если #(x, B) > 0. Аналогично, если #(x, B) = 0, то х не принадлежит B. Æ – пустой комплект, не имеющий членов (для всех х: #(x, 0) = 0). Если ограничить число элементов в комплекте так, что 0 £ #(x, B) £ 1, то получим теорию множеств.
Под мощностью | B | комплекта B понимается общее число экземпляров в комплекте | B | = S x #(x, B).
Комплект A является подкомплектом комплекта B, если каждый элемент A является элементом B, по крайней мере, не большее число раз, т.е. A Í B тогда и только тогда, когда #(x, A) £ #(x, B) для всех х.
Два комплекта равны (А = В), если #(x, A) = #(x, B).
Комплект A строго включен в комплект B (A Ì B), если A Í B и A ¹ B. Над комплектами определены 4 операции:
- объединение A È B: #(x, A È B) = max(#(x, A), #(x, B));
- пересечение A Ç B: #(x, A Ç B) = min(#(x, A), #(x, B));
- сумма A + B: #(x, A + B) = #(x, A) + #(x, B);
- разность A – B: #(x, A – B) = #(x, A) – #(x, B).
Назовем множество элементов, из которых составляются комплекты, областью D. Пространство комплектов Dn есть множество всех таких комплектов, что элементы их принадлежат D и ни один из элементов не входит в комплект более n раз. Иначе говоря, для любого B Î Dn:
- из x Î B следует х Î D;
- для любого х #(x, B) £ n.
Множество D ¥ есть множество всех комплектов над областью D без какого-либо ограничения на число экземпляров элемента в комплекте.
Структура сети Петри
Сеть Петри состоит из 4 компонентов C = (P, T, I, O), которые и определяют ее структуру:
- конечное множество позиций P = { p 1, p 2,..., pn }, n ³ 0 – мощность множества P;
- конечное множество переходов T = { t 1, t 2,..., tm }, m ³ 0 – мощность множества T;
- входная функция I: T ® P ¥ – отображение из переходов в комплекты позиций;
- выходная функция O: T ® P ¥ – отображение из переходов в комплекты позиций.
Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход tj во множество позиций I (tj), называемых входными позициями перехода. Выходная функция O отображает переход tj во множество позиций O (tj), называемых выходными позициями перехода. Множества позиций и переходов не пересекаются.
Позиция pi является входной позицией перехода tj в том случае, если pi Î I (tj); pi является выходной позицией перехода, если pi Î O (tj).
Входы и выходы переходов представляют комплекты позиций. Кратность входной позиции для перехода tj есть число появлений позиции во входном комплекте перехода #(pi, I (tj)). Аналогично, кратность выходной позиции pi для перехода tj есть число появлений позиции в выходном комплекте перехода #(pi, O (tj)).
Переход tj есть выход позиции pi, если pi есть вход tj (рис. 5.1). Переход tj является входом позиции pi, если pi есть выход tj (рис. 5.2).
| 
|
| Рис. 5.1 | Рис. 5.2 |
Определим расширенную входную функцию I и выходную функцию O таким образом, что #(tj, I (pi)) = #(pi, O (tj)); #(tj, O (pi)) = #(pi, I (tj)).
Графы сетей Петри
Теоретико-графовым представлением сети Петри является двудольный ориентированный мультиграф G = (V, A), где
V = { v 1, v 2,..., vs } – множество вершин;
А = { a 1, a 2,..., ar } – комплект направленных дуг ai = { vj, vk }, где vj, vk Î V.
Множество V может быть разбито на два непересекающихся подмножества P и T (P Ç T = 0), и если ai = (vj, vk), тогда либо vj Î P и vk Î T, либо vj Î T и vk Î P.
Сеть Петри есть ориентированный мультиграф, т.к. он допускает существование направленных кратных дуг от одной вершины к другой. Граф является двудольным, т.к. он допускает существование вершин двух типов: позиций (кружок O) и переходов (планка |).
Ориентированные дуги соединяют позиции и переходы. Дуга, направленная от позиции pi к переходу tj, определяет позицию, которая является входом перехода tj. Кратные входы в переход указываются кратными дугами из входных позиций в переход. Выходная позиция указывается дугой от перехода к позиции. Кратные выходы также представлены кратными дугами.
Пример. Пусть задана следующая структура сети Петри: C = (P, T, I, O), n = 6, m = 5 (рис. 5.3).
Рис. 5.3
P = { p 1, p 2, p 3, p 4, p 5, p 6} T = { t 1, t 2, t 3, t 4, t 5}
I (t 1) = { p 1} O (t 1) = { p 2, p 3}
I (t 2) = { p 3} O (t 2) = { p 3, p 5, p 5}
I (t 3) = { p 2, p 3} O (t 3) = { p 2, p 4}
I (t 4) = { p 4, p 5, p 5, p 5} O (t 4) = { p 4}
I (t 5) = { p 2} O (t 5) = { p 6}
Расширенными входной и выходной функциями являются:
I (p 1) = {} O (p 1) = { t 1}
I (p 2) = { t 1, t 3} O (p 2) = { t 3, t 5}
I (p 3) = { t 1, t 2} O (p 3) = { t 2, t 3}
I (p 4) = { t 3, t 4} O (p 4) = { t 4}
I (p 5) = { t 2, t 2} O (p 5) = { t 4, t 4, t 4}
I (p 6) = { t 5} O (p 6) = {}
Оба представления сети Петри – в виде структуры и в виде графа – эквивалентны. Их можно преобразовать друг в друга.
Маркировка сетей Петри
Маркировка m есть присвоение фишек позициям сети Петри. Фишка – это одна из компонент сети Петри (подобно позициям и переходам). Фишки присваиваются позициям. Их количество при выполнении сети может изменяться. Фишки используются для отображения динамики системы.
Маркированная сеть Петри есть совокупность структуры сети Петри C = (P, T, I, O) и маркировки m и может быть записана в виде M = (P, T, I, O, m). На графе сети Петри фишки изображаются крупными точками в кружке, который представляет позицию сети Петри. Количество фишек (точек) для каждой позиции не ограничено и, следовательно, в целом для сети существует бесконечно много маркировок. Множество всех маркировок сети, имеющей n позиций, является множеством всех n векторов, т.е. Nn. Очевидно, что хотя это множество и бесконечно, но оно счетно. Когда маркировка превышает 4 или 5 фишек, то в кружках не рисуют фишки, а указывают их количество (рис. 5.4).
Структура сети Петри может оставаться неизменной, а маркировка сети может меняться.
Пример: Маркировка m = (12, 22, 8, 10), m¢ = (13, 22, 9, 10).
|
| Рис. 5.4 |
