Алгоритм метода потенциалов. 3 страница

Если случайный процесс, происходящий в системе с дискретными состояниями является непрерывной марковской цепью, то для вероятностей p₁(t), р₂(t), …, p_n(t) можно составить систему линейных дифференциальных уравнений, называемых уравнениями Колмогорова. При составлении уравнений удобно пользоваться графом состояний системы. В левой части каждого из них стоит производная вероятности какого-то (j-го) состояния. В правой части – сумма произведений вероятностей всех состояний, из которых возможен переход в данное состояние, на интенсивности соответствующих потоков, минус суммарная интенсивность всех потоков, выводящих систему из данного (j-го) состояния, умноженная на вероятность данного (j-го) состояния.

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

Рисунок 2 – Граф состояний для процессов гибели и размножения

Здесь величины , , …, – интенсивности переходов системы из состояния в состояние слева направо, можно интерпретировать как интенсивности рождения (возникновения заявок) в системе. Аналогично, величины , , …, – интенсивности переходов системы из состояния в состояние справа налево, можно интерпретировать как интенсивности гибели (выполнения заявок) в системе.

Поскольку все состояния являются сообщающимися и существенными, существует (в силу теоремы 2) предельное (финальное) распределение вероятностей состояний. Получим формулы для финальных вероятностей состояний системы.

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

Для состояния S₀:

Следовательно:

Для состояния S₁:

Следовательно:

С учетом того, что :

Аналогично получаем уравнения для остальных состояний системы. В результате получим систему уравнений:

Решение этой системы будет иметь вид:

, , …,

Заявкой (или требованием) называется спрос на удовлетворение какой-либо потребности (далее потребности предполагаются однотипными). Выполнение заявки называется обслуживанием заявки.

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

Поступление заявки в СМО называется событием. Последовательность событий, заключающихся в поступлении заявок в СМО, называется входящим потоком заявок. Последовательность событий, заключающихся в выполнении заявок в СМО, называется выходящим потоком заявок.

Поток заявок называется простейшим, если он удовлетворяет следующим условиям:

1) отсутствие последействия, т.е. заявки поступают независимо друг от друга;

2) стационарность, т.е. вероятность поступления данного числа заявок на любом временном отрезке [t₁; t₂] зависит лишь от величины этого отрезка и не зависит от значения t₁, что позволяет говорить о среднем числе заявок за единицу времени, λ, называемом интенсивностью потока заявок;

3) ординарность, т.е. в любой момент времени в СМО поступает лишь одна заявка, а поступление одновременно двух и более заявок пренебрежимо мало.

Для простейшего потока вероятность p_i(t) поступления в СМО ровно i заявок за время t вычисляется по формуле:

т.е. вероятности распределены по закону Пуассона с параметром λ t. По этой причине простейший поток называется также пуассоновским потоком.

Функция распределения F(t) случайного интервала времени T между двумя последовательными заявками по определению равна . Но , где – вероятность того, что следующая после последней заявки поступит в СМО по истечении времени t, т.е. за время t в СМО не поступит ни одна заявка. Но вероятность этого события находится из (6) при i = 0. Таким образом:

Плотность вероятности f(t) случайной величины T определяется формулой:

,

Математическое ожидание, дисперсия и среднее квадратическое отклонение случайной величины T равны соответственно:

Каналом обслуживания называется устройство в СМО, обслуживающее заявку. СМО, содержащее один канал обслуживания, называется одноканальной, а содержащее более одного канала обслуживания – многоканальной.

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

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

СМО могут также различаться по дисциплине обслуживания.

Если в СМО нет приоритета, то заявки отбираются из очереди в канал по различным правилам.

· Первым пришел – первым обслужен (FCFS – First Came – First Served)

· Последним пришел – первым обслужен (LCFS – Last Came – First Served)

· Первоочередное обслуживание требований с кратчайшей длительностью обслуживания (SPT/SJE)

· Первоочередное обслуживание требований с кратчайшей длительностью дообслуживания (SRPT)

· Первоочередное обслуживание требований с кратчайшей средней длительностью обслуживания (SEPT)

· Первоочередное обслуживание требований с кратчайшей средней длительностью дообслуживания (SERPT)

Приоритеты бывают двух типов – абсолютный и относительный.

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

СМО описываются некоторыми параметрами, которые характеризуют эффективность работы системы.

– число каналов в СМО;

– интенсивность поступления в СМО заявок;

– интенсивность обслуживания заявок;

– коэффициент загрузки СМО;

– число мест в очереди;

– вероятность отказа в обслуживании поступившей в СМО заявки;

– вероятность обслуживания поступившей в СМО заявки (относительная пропускная способность СМО);

При этом:

А – среднее число заявок, обслуживаемых в СМО в единицу времени (абсолютная пропускная способность СМО)

– среднее число заявок, находящихся в СМО

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

,

где – вероятность нахождения системы в S_k состоянии.

– коэффициент занятости каналов

– среднее время ожидания заявки в очереди

– интенсивность ухода заявок из очереди

– среднее число заявок в очереди. Определяется как математическое ожидание случайной величины m – числа заявок, состоящих в очереди

Здесь – вероятность нахождения в очереди i заявок;

– среднее время пребывания заявки с СМО

– среднее время пребывания заявки в очереди

Для открытых СМО справедливы соотношения:

Эти соотношения называются формулами Литтла и применяются только для стационарных потоков заявок и обслуживания.

Рассмотрим некоторые конкретные типы СМО. При этом будет предполагаться, что плотность распределения промежутка времени между двумя последовательными событиями в СМО имеет показательное распределение (7), а все потоки являются простейшими.

Размеченный граф состояний одноканальной СМО представлен на рисунке 3.

Рисунок 3 – Граф состояний одноканальной СМО

Здесь и – интенсивность потока заявок и выполнения заявок соответственно. Состояние системы S_o обозначает, что канал свободен, а S₁ – что канал занят обслуживанием заявки.

Система дифференциальных уравнений Колмогорова для такой СМО имеет вид:

где p_o(t) и p₁(t) – вероятности нахождения СМО в состояниях So и S1 соответственно. Уравнения для финальных вероятностей p_o и p₁ получим, приравнивая нулю производные в первых двух уравнениях системы. В результате получим:

Вероятность p₀ по своему смыслу есть вероятность обслуживания заявки p_обс, т. к. канал является свободным, а вероятность р₁ по своему смыслу является вероятностью отказа в обслуживании поступающей в СМО заявки р_отк, т. к. канал занят обслуживанием предыдущей заявки.

Пусть СМО содержит n каналов, интенсивность входящего потока заявок равна , а интенсивность обслуживания заявки каждым каналом равна . Размеченный граф состояний системы изображён на рисунке 4.

Рисунок 4 – Граф состояний многоканальной СМО с отказами

Состояние S₀ означает, что все каналы свободны, состояние S_k (k = 1, n) означает, что обслуживанием заявок заняты k каналов. Переход из одного состояния в другое соседнее правое происходит скачкообразно под воздействием входящего потока заявок интенсивностью независимо от числа работающих каналов (верхние стрелки). Для перехода системы из одного состояния в соседнее левое неважно, какой именно канал освободится. Величина характеризует интенсивность обслуживания заявок при работе в СМО k каналов (нижние стрелки).

Сравнивая графы на рис. 3 и на рис. 5 легко увидеть, что многоканальная СМО с отказами является частным случаем системы рождения и гибели, если в последней принять и

При этом для нахождения финальных вероятностей можно воспользоваться формулами (4) и (5). С учётом (16) получим из них:

Формулы (17) и (18) называются формулами Эрланга – основателя теории массового обслуживания.

Вероятность отказа в обслуживании заявки р_отк равна вероятности того, что все каналы заняты, т.е. система находится в состоянии S_n. Таким образом,

Относительную пропускную способность СМО найдём:

Абсолютную пропускную способность найдём

Среднее число занятых обслуживанием каналов можно найти по формуле (10), однако сделаем это проще. Так как каждый занятый канал в единицу времени обслуживает в среднем заявок, то можно найти по формуле:

В СМО с ограниченной очередью число мест m в очереди ограничено. Следовательно, заявка, поступившая в момент времени, когда все места в очереди заняты, отклоняется и покидает СМО. Граф такой СМО представлен на рисунке 5.

Рисунок 5 – Граф состояний одноканальной СМО с ограниченной очередью

Состояния СМО представляются следующим образом:

S₀ – канал обслуживания свободен,

S₁ – канал обслуживания занят, но очереди нет,

S₂ – канал обслуживания занят, в очереди одна заявка,

S_k+1 – канал обслуживания занят, в очереди k заявок,

S_m+1 – канал обслуживания занят, все m мест в очереди заняты.

Для получения необходимых формул можно воспользоваться тем обстоятельством, что СМО на рисунок 5 является частным случаем системы рождения и гибели, представленной на рисунке 2, если в последней принять и

Выражения для финальных вероятностей состояний рассматриваемой СМО можно найти из (4) и (5) с учётом (21). В результате получим:

При р = 1 формулы (22), (23) принимают вид

При m = 0 (очереди нет) формулы (22), (23) переходят в формулы (14) и (15) для одноканальной СМО с отказами.

Поступившая в СМО заявка получает отказ в обслуживании, если СМО находится в состоянии S_m+1, т.е. вероятность отказа в обслуживании заявки равна:

Относительная пропускная способность СМО равна:

Абсолютная пропускная способность равна:

Среднее число заявок, стоящих в очереди L_оч, находится по формуле

и может быть записано в виде:

При формула (24) принимает вид:

– среднее число заявок, находящихся в СМО, находится по формуле(10)

и может быть записано в виде:

При , из (25) получим:

Среднее время пребывания заявки в СМО и в очереди находится по формулам (12) и (13) соответственно.

Примером такой СМО может служить директор предприятия, вынужденный рано или поздно решать вопросы, относящиеся к его компетенции, или, например, очередь в булочной с одним кассиром. Граф такой СМО изображён на рисунке 6.

Рисунок 6 – Граф состояний одноканальной СМО с неограниченной очередью

Все характеристики такой СМО можно получить из формул предыдущего раздела, полагая в них . При этом необходимо различать два существенно разных случая: а) ; б) . В первом случае, как это видно из формул (22), (23), р₀ = 0 и p_k = 0 (при всех конечных значениях k). Это означает, что при очередь неограниченно возрастает, т.е. этот случай практического интереса не представляет.

Рассмотрим случай, когда . Формулы (22) и (23) при этом запишутся в виде:

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

Абсолютная пропускная способность равна:

Среднее число заявок в очереди получим из формулы (24) при :

Среднее число обслуживаемых заявок есть:

Среднее число заявок, находящихся в СМО:

Среднее время пребывания заявки в СМО и в очереди определяются формулами (12) и (13).

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

Граф такой системы представлен на рисунке 7.

Рисунок 7 – Граф состояний многоканальной СМО с ограниченной очередью

– все каналы свободны, очереди нет;

– заняты l каналов (l = 1, n), очереди нет;

- заняты все n каналов, в очереди находится i заявок (i = 1, m).

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

Выражения для финальных вероятностей легко найти из формул (4) и (5). В результате получим:

Образование очереди происходит, когда в момент поступления в СМО очередной заявки все каналы заняты, т.е. в системе находятся либо n, либо (n+1), …, либо (n + m – 1) заявок. Т.к. эти события несовместны, то вероятность образования очереди p_оч равна сумме соответствующих вероятностей :

Отказ в обслуживании заявки происходит, когда все m мест в очереди заняты, т.е.:

Относительная пропускная способность равна:

Абсолютная пропускная способность:

Среднее число заявок, находящихся в очереди, определяется по формуле (11) и может быть записано в виде:

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

Среднее число заявок, находящихся в СМО:

Среднее время пребывания заявки в СМО и в очереди определяется формулами (12) и (13).

Граф такой СМО изображен на рисунке 8 и получается из графа на рисунке 7 при .

Рисунок 8 – Граф состояний многоканальной СМО с неограниченной очередью

Формулы для финальных вероятностей можно получить из формул для n-канальной СМО с ограниченной очередью при . При этом следует иметь в виду, что при вероятность р₀ = р₁=…= p_n = 0, т.е. очередь неограниченно возрастает. Следовательно, этот случай практического интереса не представляет и ниже рассматривается лишь случай . При из (26) получим:

Формулы для остальных вероятностей имеют тот же вид, что и для СМО с ограниченной очередью:

Из (27) получим выражение для вероятности образования очереди заявок:

Поскольку очередь не ограничена, то вероятность отказа в обслуживании заявки:

Относительная пропускная способность:

Абсолютная пропускная способность:

Из формулы (28) при получим выражение для среднего числа заявок в очереди:

Среднее число обслуживаемых заявок определяется формулой: