Алгоритмы решения задач систем массового обслуживания

     Состояние СМО характеризуется простаиванием  или занятостью ее канала, т.е. двумя состояниями: S₀ – канал свободен и простаивает, S₁ – канал занят. Переход системы из состояния S₀ в состояние S₁ осуществляется под воздействием входящего потока заявок П_вх, а из состояния S₁ в состояние S₀ систему переводит поток обслуживании П_об: если в данный момент времени система находится в некотором состоянии, то с наступлением первого после данного момента времени СМО переходит в другое состояние. Плотности вероятностей перехода из состояния S₀ в S₁ и обратно равны соответственно λ и µ. Граф состояний подобной СМО с двумя возможными состояниями приведен на рисунке 3.

     

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

     Для многоканальной СМО с отказами (n > 1) при тех же условиях состояния системы обозначим по числу занятых каналов (по числу заявок, находящихся в системе под обслуживанием, так как каждый канал в СМО либо свободен, либо обслуживает только одну заявку). Таким образом, подобная СМО может находиться в одном из следующих (n+1) состояний: s₀ – все n каналов свободны; s₁ – занят только один из каналов, остальные (n-1) каналов свободны; s_i – заняты i – каналов, (n-i) каналов свободны; s_n – заняты все n каналов. Граф состояний такой СМО приведен на рисунке 4.

     

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

    При этом имеет место  а

    Пользуясь общим правилом составления дифференциальных уравнений Колмогорова, можно для приведенных на рисунке 3 и рисунке 4 графов состояний составить системы дифференциальных уравнений:

1. например, для одноканальной СМО (рисунок 3):

     

     

     

2. для многоканальной СМО (рисунок 4) имеем:

     

     ……………………………

     

     ……………………………

     

     

    Решив первую систему уравнений, можно  найти значения p₀(t) и p₁(t) для одноканальной СМО и построить графики при трех случаях: 1) λ >µ; 2) λ=µ; 3) λ<µ (рисунок 5).Можно также определить предельную пропускную способность СМО. Решение второй системы уравнений для многоканальной СМО в аналитическом виде получить вручную сложно, и его обычно получают с помощью ЭВМ в численном виде.

     

     Рисунок 5-а, б, в, г.

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

 

     Таблица 1-Характеристики одноканальной СМО с отказами

 

     СМО с ожиданием.

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

    Предположим, что независимо от того, сколько  требований поступает на вход обслуживающей  системы, данная система (очередь + обслуживаемые клиенты) не может вместить более N-требований (заявок), т.е. клиенты, не попавшие в ожидание, вынуждены обслуживаться в другом месте. Наконец, источник, порождающий заявки на обслуживание, имеет неограниченную (бесконечно большую) емкость. Граф состояний СМО в этом случае имеет вид, показанный на рисуноке 6.

     

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

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

     S₀ – канал свободен;

     S₁ – канал занят (очереди нет);

     S₂ – канал занят (одна заявка стоит в очереди);

     ……………………………………………………

     S_n – канал занят (n-1 заявок стоит в очереди);

     ………………………………………………….

     S_N – канал занят (N-1 заявок стоит в очереди).

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

                                                     (1.4)

     где ρ=λ/µ; n – номер состояния.

     Решение приведенной выше системы уравнений (1.4) для нашей модели СМО имеет вид:

     

     

     Тогда

    Следует отметить, что выполнение условия  стационарности для данной СМО необязательно, поскольку число допускаемых в обслуживающую систему заявок контролируется путем введения ограничения на длину очереди (которая не может превышать N-1), а не соотношением между интенсивностями входного потока, т.е. не отношением λ/µ=ρ.

    Определим характеристики одноканальной СМО  с ожиданием и ограниченной длиной очереди, равной (N-1):

1. вероятность отказа в обслуживании заявки:

 

                                                             (1.5)

2. относительная пропускная способность системы:

                                                        (1.6)

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

                                                                                                          (1.7)

4. среднее число находящихся в системе заявок:

                                                       (1.8)

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

                                                                                            (1.9)

6. средняя продолжительность пребывания клиента (заявки) в очереди:

                                                                                          (1.10)

7. среднее число заявок (клиентов) в очереди (длина очереди):

                                                                                        (1.11)

    Теперь  рассмотрим более подробно СМО, имеющую  n-каналов с неограниченной очередью. Поток заявок, поступающих в СМО, имеет интенсивность λ, а поток обслуживаний – интенсивность µ. Необходимо найти предельные вероятности состояний СМО и показатели ей эффективности.

    Система может находиться в одном состоянии  S₀, S₁, S₂,…, S_k,…, S_n,…, нумеруемых по числу заявок, находящихся в СМО: S0 – в системе нет заявок (все каналы свободны); S₁ – занят один канал, остальные свободны; S₂ – заняты два канала, остальные свободны;S_k – занято k каналов, остальные свободны;S_n – заняты все n каналов (очереди нет); S_n+1 – заняты все n каналов, в очереди одна заявка; S_n+r – заняты все n каналов, r заявок стоит в очереди.Граф состояний показан на рисунке 7.

     

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

     По мере увеличения в СМО от 0 до n увеличивается число каналов обслуживания. При числе заявок в СМО, большем, чем n, интенсивность потока обслуживания сохраняется равной nµ.

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

                                                             (1.12)

                                                               (1.13)

                                                                  (1.14)

    Вероятность того, что заявка окажется в очереди  равна:

                                                                                             (1.15)

    Для n-канальной СМО с ожиданием, используя прежние формулы, можно найти:

• среднее число занятых каналов:

                                                                                                        (1.16)

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

                                                                                          (1.17)

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

                                                                                        (1.18) 
 
 

     2. Практическое применение  теории массового  обслуживания

     2.1 Решение задачи  математическими  методами

     2.1.1 Постановка задачи

    В универсаме к узлу расчета поступает  поток покупателей с интенсивностью λ=81 человек в час. Средняя продолжительность обслуживания контролером-кассиром одного покупателя _об.= 2 минуты. Рабочее время 8 часов (1 час обеденный перерыв). Средняя з/п одного контролера-кассира составляет 5000 руб. в месяц. Кассовый аппарат стоит 3000 руб. (срок службы 5 лет). Стоимость канцтоваров (бумага, кассовая лента, ручки и т.д.) на одного кассира составляет 150 руб. в месяц.