Модель обслуживания машинного парка

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

Пусть машинный парк состоит из N машин и обслуживается бригадой R техников (N > R), причем каждая машина может обслуживаться только одним техником. Здесь машины являются источниками требований (заявок на обслуживание), а техники – обслуживающими каналами. Интенсивность зависит от того, сколько машин в данный момент находится в эксплуатации (N – k) и сколько машин обслуживается или стоит в очереди, ожидая обслуживания (k). Общий (суммарный) входящий поток имеет интенсивность (N – k)l.

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

Состояние S_k системы характеризуется общим числом требований, находящихся на обслуживании и в очереди, равным k. Для рассматриваемой замкнутой системы, очевидно, k = 0, 1, 2,..., N. При этом если система находится в состоянии S_k, то число объектов, находящихся в эксплуатации, равно (N – k).

Если l – интенсивность потока требований в расчете на одну машину, то:

;

.

Система алгебраических уравнений, описывающих работу замкнутой СМО в стационарном режиме, выглядит следующим образом (y = l/m):

,

Решая данную систему, находим вероятность k -гo состояния:

.

Величина P ₀ определяется из условия нормирования полученных результатов по формулам для P_k, 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. Пространство комплектов Dⁿ есть множество всех таких комплектов, что элементы их принадлежат D и ни один из элементов не входит в комплект более n раз. Иначе говоря, для любого B Î Dⁿ:

- из x Î B следует х Î D;

- для любого х #(x, B) £ n.

Множество D ^¥ есть множество всех комплектов над областью D без какого-либо ограничения на число экземпляров элемента в комплекте.

Структура сети Петри

Сеть Петри состоит из 4 компонентов C = (P, T, I, O), которые и определяют ее структуру:

- конечное множество позиций P = { p ₁, p ₂,..., p_n }, n ³ 0 – мощность множества P;

- конечное множество переходов T = { t ₁, t ₂,..., t_m }, m ³ 0 – мощность множества T;

- входная функция I: T ® P ^¥ – отображение из переходов в комплекты позиций;

- выходная функция O: T ® P ^¥ – отображение из переходов в комплекты позиций.

Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход t_j во множество позиций I (t_j), называемых входными позициями перехода. Выходная функция O отображает переход t_j во множество позиций O (t_j), называемых выходными позициями перехода. Множества позиций и переходов не пересекаются.

Позиция p_i является входной позицией перехода t_j в том случае, если p_i Î I (t_j); p_i является выходной позицией перехода, если p_i Î O (t_j).

Входы и выходы переходов представляют комплекты позиций. Кратность входной позиции для перехода t_j есть число появлений позиции во входном комплекте перехода #(p_i, I (t_j)). Аналогично, кратность выходной позиции p_i для перехода t_j есть число появлений позиции в выходном комплекте перехода #(p_i, O (t_j)).

Переход t_j есть выход позиции p_i, если p_i есть вход t_j (рис. 5.1). Переход t_j является входом позиции p_i, если p_i есть выход t_j (рис. 5.2).

Рис. 5.1	Рис. 5.2

Определим расширенную входную функцию I и выходную функцию O таким образом, что #(t_j, I (p_i)) = #(p_i, O (t_j)); #(t_j, O (p_i)) = #(p_i, I (t_j)).

Графы сетей Петри

Теоретико-графовым представлением сети Петри является двудольный ориентированный мультиграф G = (V, A), где

V = { v ₁, v ₂,..., v_s } – множество вершин;

А = { a ₁, a ₂,..., a_r } – комплект направленных дуг a_i = { v_j, v_k }, где v_j, v_k Î V.

Множество V может быть разбито на два непересекающихся подмножества P и T (P Ç T = 0), и если a_i = (v_j, v_k), тогда либо v_j Î P и v_k Î T, либо v_j Î T и v_k Î P.

Сеть Петри есть ориентированный мультиграф, т.к. он допускает существование направленных кратных дуг от одной вершины к другой. Граф является двудольным, т.к. он допускает существование вершин двух типов: позиций (кружок O) и переходов (планка |).

Ориентированные дуги соединяют позиции и переходы. Дуга, направленная от позиции p_i к переходу t_j, определяет позицию, которая является входом перехода t_j. Кратные входы в переход указываются кратными дугами из входных позиций в переход. Выходная позиция указывается дугой от перехода к позиции. Кратные выходы также представлены кратными дугами.

Пример. Пусть задана следующая структура сети Петри: C = (P, T, I, O), n = 6, m = 5 (рис. 5.3).

Рис. 5.3

P = { p ₁, p ₂, p ₃, p ₄, p ₅, p ₆} T = { t ₁, t ₂, t ₃, t ₄, t ₅}

I (t ₁) = { p ₁} O (t ₁) = { p ₂, p ₃}

I (t ₂) = { p ₃} O (t ₂) = { p ₃, p ₅, p ₅}

I (t ₃) = { p ₂, p ₃} O (t ₃) = { p ₂, p ₄}

I (t ₄) = { p ₄, p ₅, p ₅, p ₅} O (t ₄) = { p ₄}

I (t ₅) = { p ₂} O (t ₅) = { p ₆}

Расширенными входной и выходной функциями являются:

I (p ₁) = {} O (p ₁) = { t ₁}

I (p ₂) = { t ₁, t ₃} O (p ₂) = { t ₃, t ₅}

I (p ₃) = { t ₁, t ₂} O (p ₃) = { t ₂, t ₃}

I (p ₄) = { t ₃, t ₄} O (p ₄) = { t ₄}

I (p ₅) = { t ₂, t ₂} O (p ₅) = { t ₄, t ₄, t ₄}

I (p ₆) = { t ₅} O (p ₆) = {}

Оба представления сети Петри – в виде структуры и в виде графа – эквивалентны. Их можно преобразовать друг в друга.

Маркировка сетей Петри

Маркировка m есть присвоение фишек позициям сети Петри. Фишка – это одна из компонент сети Петри (подобно позициям и переходам). Фишки присваиваются позициям. Их количество при выполнении сети может изменяться. Фишки используются для отображения динамики системы.

Маркированная сеть Петри есть совокупность структуры сети Петри C = (P, T, I, O) и маркировки m и может быть записана в виде M = (P, T, I, O, m). На графе сети Петри фишки изображаются крупными точками в кружке, который представляет позицию сети Петри. Количество фишек (точек) для каждой позиции не ограничено и, следовательно, в целом для сети существует бесконечно много маркировок. Множество всех маркировок сети, имеющей n позиций, является множеством всех n векторов, т.е. Nⁿ. Очевидно, что хотя это множество и бесконечно, но оно счетно. Когда маркировка превышает 4 или 5 фишек, то в кружках не рисуют фишки, а указывают их количество (рис. 5.4).

Структура сети Петри может оставаться неизменной, а маркировка сети может меняться.

Пример: Маркировка m = (12, 22, 8, 10), m¢ = (13, 22, 9, 10).

Рис. 5.4