Типы систем массового обслуживания

Модели многих технологических, производственных и бизнес-систем сводятся к дискретным стохастическим системам. В настоящее время имеются развитые пакеты программ для имитационного моделирования дискретных стохастических систем (ARENA, Bpsim, GPSS, с которыми выполняются лабораторные работы). Они позволяют разрабатывать достаточно детальные модели реальных систем. Проблемами при имитационном моделировании являются:

- распространение результатов моделирования на заранее неизвестное изменение исходных данных;

- не идеальность датчиков псевдослучайных последовательностей.

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

Важное место среди дискретных стохастических систем занимают системы массового обслуживания³⁴ (СМО). Существующие СМО можно разделить по ряду показателей. Так различают системы с потерями, с ожиданием и комбинированные системы.

В системах с потерями требования,которые при поступлении не находят ни одного свободногоустройства, теряются.

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

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

СМО можно разделить по дисциплинам обслуживания, которые бывают приоритетными и бесприоритетными. Важными бесприоритетными дисциплинами обслуживания являются:

- FIFO (First In – First Out) – требования обслуживаются в порядке их поступления;

- LIFO (Last In – First Out) – каждый раз преимущество имеет требование, поступившее последним;

- SIRO (Service In Random Order) – очередное требование выбирается из очереди случайно.

При приоритетных дисциплинах обслуживания поступающие требования имеют различные приоритеты. Если поступившее требование обладает высоким приоритетом, а все приборы обслуживания заняты, то оно либо занимает одно из первых мест в очереди, либо временно прекращает обслуживание требования низкого приоритета, либо вообще прекращает его обслуживание. Эти различные возможности определяются приоритетными правилами. Различают два важных приоритетных правила.

1. Абсолютный (прерывающий) приоритет:при поступлении требования высокогоприоритета прерывается обслуживание требования низкого приоритета, если такое имеется. Рассматривают случаи абсолютного приоритета с дообслуживанием и абсолютного приоритета с обслуживанием заново.

³⁴ Из литературы для углубленного изучения теории массового обслуживания можно рекомендовать [8].

2. Относительный приоритет:требование высокого приоритета занимает первое место в

очереди и не происходит никаких прерываний.

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

Известна символика Кендалла для краткой характеристики СМО. Система обслуживания характеризуется пятью показателями: A/B/S/m/K. Здесь S означает количество обслуживающих устройств, m –это количество мест ожидания.Значениеm=0характеризует систему с потерями,значение 0<m<+∞ - комбинированную систему с ожиданием и с потерями, а m=∞ чистую систему с ожиданием, т.е. с бесконечным числом мест для ожидания. В последнем случае ∞ обычно опускается, так что A/B/S и A/B/S/∞ означают одно и то же. Если присутствует параметр K, то число источников нагрузки конечно и равно K. Буква A характеризует поток требований: A=GI или A=G – рекуррентный поток, А=М – пуассоновский поток, а А=Е_k – рекуррентный поток с распределением Эрланга порядка K; k, A=D – поток с постоянными интервалами между требованиями.

Буква В характеризует случайные последовательности длительностей обслуживания на отдельных приборах: В=G – независимые одинаково распределенные длительности обслуживания; В=М

– независимые экспоненциально распределенные длительности обслуживания. Символы

G и M

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

Случайные процессы

Для мат. описания изменения случайным образом состояний, принимаемых СМО с течением времени, необходимо ввести понятие случайного процесса.

Под случайным процессом (ξ_t)_t∈T понимается семейство случайных переменных, определенных на общем вероятностном пространстве (E, Σ, P). Случайная величина ξ_t характеризует состояние системы в момент времени t и принимает значения из заданного пространства элементарных событий E. Множество T значений параметра t может быть дискретным или непрерывным. Здесь Σ- некоторая σ-

алгебра подмножеств (событий) множества Е,на которых определена вероятностная мера Р.

Для ТМО особое значение имеет один класс случайных процессов – марковские процессы. В то же время существуют специальные методы, которые позволяют «марковизировать» общие случайные процессы.

Случайный процесс (ξ_t)_t∈T называется марковским, если для всех t>t₁>…>t_n и τ>0 для любых элементарных событий (состояний) x, x₁, …,x_n∈E и любого множества событий A∈Σ справедливо:

т.е. условная вероятность события А в момент t+τ при условии, что в момент времени t было состояние x, в момент времени t₁ было состояние x₁ и т.д ., равна условной вероятности события А в момент t+τ при условии только состояния x в момент t (такую условную вероятность называют еще функцией перехода).

Марковский процесс называется однородным, если функция перехода P(ξ_t+τ∈A|ξ_t=x) зависит только от τ, x и А, но не зависит от t.

Смотря по тому, дискретно ли множество T значений параметра или непрерывно, говорят о дискретном или непрерывном марковском процессе.Если дискретный или непрерывный марковскийпроцесс имеет не более чем счетное число состояний, то его называют дискретной или непрерывной цепью Маркова соответственно.Ниже мы будем рассматривать только цепи Маркова.В случаемарковских цепей вместо функции перехода достаточно рассмотреть вероятности перехода P_ij(τ)=P(ξ_t+τ

=j|ξ_t=i), τ>0, i, j ∈E.

Поведение системы, описываемой однородной цепью Маркова, полностью определяется двумя характеристиками:

- начальным распределением P_j(0), j∈E;

- вероятностями перехода вида P_ij(τ)=P(ξ_t+τ =j|ξ_t=i), τ>0.

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

i

Для однородных цепей с непрерывным временем вместо (2) можно также записать:

P_j (t + t)=∑P_ij ( t)P_i (t), j =0,1,... (3)

i

Предполагая P_ij(t) дифференцируемыми функциями, получим P_ij( t)=q_ij t+o( t), i≠j, P_ii( t)=1-q_i t+o( t).

Подставив это в (3) и выполнив предельный переход мы получим систему дифференциальных уравнений:

с начальными условиями P_j(0), j=0,1,…

Здесь параметры q называются интенсивностями перехода:

q_i =

q_ij =

Эти пределы имеют следующую интерпретацию. Если в момент времени t система находилась в

интенсивность, с которой процесс уходит из состояния i при условии,что он находился в этом

образом, величину q_ij можно интерпретировать как интенсивность, с которой процесс переходит из состояния i в состояние j.

Для всех i∈E имеет место соотношение

При конечном Е это свойство всегда имеет место.

Не нашли, что искали? Воспользуйтесь поиском по сайту: