Решение управленческой задачи методами теории массового обслуживания

Заявка, заставшая канал  занятым, получает отказ и покидает систему. Обслуживание заявки продолжается в течение случайного времени T_об, распределенного по показательному закону с параметром µ:

ƒ(t)=µе^-µt (t >0) (1.1)

Из этого следует, что  «поток обслуживания» — простейший, с интенсивностью µ .Чтобы представить себе этот поток, вообразим один непрерывно занятый канал, который будет выдавать обслуженные заявки потоком с интенсивностью µ.

Требуется найти:

1)абсолютную пропускную  способность СМО (А);

2)относительную пропускную  способность СМО (q).

Рассмотрим единственный канал обслуживания как физическую систему S, которая может находиться в одном из двух состояний: S₀ — свободен, S₁ — занят.

ГСП системы показан на рис. 3 (а).

Рис. 3. ГСП для одноканальной СМО с отказами (а); график решения уравнения (1.4) (б)

Из состояния S₀ в S₁ систем у, очевидно, переводит поток заявок с интенсивностью λ; из S₁ в S₀ — «поток обслуживания» с интенсивностью µ.

Вероятности состояний: P₀ (t) и P₁ (t). Очевидно, для любого момента t:

P₀ (t) + P₁ (t) = 1. (1.2)

Составим дифференциальные уравнения Колмогорова для вероятностей состояний согласно правилу, данному  выше:

(1.3)

Из двух уравнений (1.3) одно является лишним, так как P₀ и P₁ связаны соотношением (1.2). Учитывая это, отбросим второе уравнение, а в первое подставим вместо P₁ выражение: (1- P₀)

или

(1.4)

Поскольку в начальный  момент канал свободен, уравнение  следует решать при начальных  условиях: P₀(0) = 1, P₁(0) =0.

Линейное дифференциальное уравнение (1.4) с одной неизвестной функцией P₀ легко может быть решено не только для простейшего потока заявок (λ= const) , но и для случая, когда интенсивность этого потока со временем меняется.

Для первого случая решение  есть:

Зависимость величины P₀ от времени имеет вид, изображенный на рис. 3 (б). В начальный момент (при t = 0) канал заведомо свободен (P₀(0) = 1). С увеличением t вероятность P₀ уменьшается и в пределе (при ) равна . Величина, P₁(t) дополняющая P₀ (t) до единицы, изменяется так, как показано на том же рисунке.

Нетрудно убедиться, что  для одноканальной СМО с отказами вероятность P₀ есть не что иное, как относительная пропускная способность q. Действительно, P₀ есть вероятность того, что в момент t канал свободен, или вероятность того, что заявка, пришедшая в момент t, будет обслужена. Следовательно, для данного момента времени t среднее отношение числа обслуженных заявок к числу поступивших также равно P₀ (q=P₀)

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

Зная относительную пропускную способность q, легко найти абсолютную А. Они связаны очевидным соотношением:

В пределе, при , абсолютная пропускная способность тоже установится и будет равна

Зная относительную пропускную способность системы q (вероятность того, что пришедшая в момент t заявка будет обслужена), легко найти вероятность отказа:

 или среднюю часть необслуженных заявок среди поданных. При

, а общее число не обслуженных  заявок равно  

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

3.2. Многоканальная СМО без очереди

 

В коммерческой деятельности примерами многоканальных СМО являются офисы коммерческих предприятий  с несколькими телефонными каналами. Бесплатная справочная служба по наличию в авто магазинах самых дешевых автомобилей в Нижнем Новгороде имеет 7 телефонных номеров, а дозвониться и получить справку, как известно, очень трудно. Следовательно, авто магазины теряют клиентов, возможность увеличить количество проданных автомобилей и выручку от продаж, товарооборот, прибыль.

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

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

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

S₀ – все каналы свободны k=0,

S₁ – занят только один канал, k=1,

S₂ – заняты только два канала, k=2,

S_k – заняты k каналов,

S_n – заняты все n каналов, k= n.

Состояния многоканальной СМО  меняются скачкообразно в случайные  моменты времени. Переход из одного состояния, например S₀ в S₁, происходит под воздействием входного потока заявок с интенсивностью λ, а обратно – под воздействием потока обслуживания заявок с интенсивностью μ. Для перехода системы из состояния S_k в S_k-1 безразлично, какой именно из каналов освободиться, поэтому поток событий, переводящий СМО, имеет интенсивность kμ, следовательно, поток событий, переводящий систему из S_n в S_n-1, имеет интенсивность nμ. Так формулируется классическая задача Эрланга, названная по имени датского инженера-математика – основателя теории массового обслуживания.

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

P₀ = (1 + ρ +ρ²/2! + ρ³/3! + .... ρⁿ/n!)^-1;   

Вычислив все вероятности  состояний n – канальной СМО с отказами P₀ , P₁, P₂, …,P_k,…, P_n, можно найти характеристики системы обслуживания.

Вероятность отказа в обслуживании определяется вероятностью того, что  поступившая заявка на обслуживание найдет все n каналов занятыми, система  будет находиться в состоянии S_n:

   k = 1…n.

В системах с отказами события  отказа и обслуживания составляют полную группу событий, поэтому Р_отк + Р_обс=1

На этом основании относительная  пропускная способность определяется по формуле:

Q = P_обс = 1-Р_отк=1-Р_n  

Абсолютную пропускную способность  СМО можно определить по формуле:

А=λ*Q

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

 k = ρ(1- ρⁿ/n! * P₀)

3.3. Одноканальная СМО с ограниченной длиной очереди

 

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

                 

Рис. 5. Одноканальная СМО с ограниченной длиной очереди.

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

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

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

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

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

S_m+1 - один канал занят и m-заявок в очереди.

Предельные вероятности  возможных состояний системы  имеют вид:

P₀ = (1- ρ)/(1- ρ^m+2);  P₁= ρ*P₀;  P₂= ρ²*P₀; … P_k= ρ^k*P₀

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

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

P_отк = p_m+1 = ρ^m+1 * P₀

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

Q = 1- p_отк = 1- ρ^m+1 * p₀

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

A = Q * λ

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

L_оч = M(k) или по формуле:

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

Т_оч = (1/ λ)* L_оч

Такой результат, когда оказывается, что Т_оч ~ 1/ λ, может показаться странным: с увеличением интенсивности потока заявок как будто бы должна возрастать длина очереди и уменьшается среднее время ожидания. Однако следует иметь в виду, что, во-первых, величина L_оч является функцией от λ и μ и, во-вторых, рассматриваемая СМО имеет ограниченную длину очереди не более m заявок.

Заявка, поступившая в  СМО в момент времени, когда все  каналы заняты, получает отказ, и, следовательно, время ее «ожидания» в СМО равно  нулю. Это приводит в общем случае (при р ≠ 1) к уменьшению Т_оч ростом λ, поскольку доля таких заявок с ростом λ увеличивается.

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

Т_сис = (1/ λ)* L_сис

В свою очередь L_сис можно найти по формулам: L_сис = L_оч + L_об;  L_об = 1- Р₀

3.4. Одноканальная СМО с неограниченной очередью.

 

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

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

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

Размеченный граф состояний  такой системы приведен на рис. 6

Количество возможных  состояний ее бесконечно:

S₀ - канал свободен, очереди нет, k =0;

S₁- канал занят обслуживанием, очереди нет, k =1;

S₂- канал занят, одна заявка в очереди, k =2;

S₃ - канал занят k-1, заявка в очереди.

                                  

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

Следует заметить, что для  СМО с неограниченной длиной очереди в формуле

Р₀ = [1+ λ / μ + (λ / μ)² + (λ / μ)^k + …]  = [1+ρ + ρ² + ρ³+… +ρ^k +…] = 1/ 1-ρ

имеет место геометрическая прогрессия с первым членом 1 и знаменателем ρ. Такая последовательность представляет собой сумму бесконечного числа членов при . Эта сумма сходится, если прогрессия, бесконечно убывающая при ρ< 1, что определяет установившийся режим работы СМО, с при ρ> 1очередь при с течением времени может расти до бесконечности.

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

P₁= ρ*P₀; P₂= ρ²*P₀; … P_k= ρ^k *P₀

Поскольку в рассматриваемой  СМО ограничение на длину очереди  отсутствует, то любая заявка может  быть обслужена, поэтому P_обс =1, следовательно, относительная пропускная способность Q = P_обс =1, соответственно P_отк =0, а абсолютная пропускная способность

A = Q * λ

Среднее число заявок в  очереди:

Среднее число заявок в  системе:

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

Т_оч = L_оч / λ

А среднее время пребывания заявки в системе: