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

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

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

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

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

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

     1.2.1 Классификация систем массового обслуживания

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

    

    Рисунок 2-Классификация систем массового обслуживания

    Согласно  общей классификации система  массового обслуживания разделяется  на три подсистемы.

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

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

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

    Системы, имеющие очередь, подразделяются на системы с одной очередью и  системы с несколькими очередями.

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

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

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

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

1. СМО с типом дисциплины «первый пришел – первый обслуживается» – дисциплина «живой очереди»;
2. СМО с типом дисциплины «последний пришел – первый обслуживается» – примером такой системы является склад, заполненный изделиями, из которого на доработку удобно брать изделия, поступившие последними;
3. СМО с типом дисциплины выбора требований случайным способом;
4. СМО с типом дисциплины выбора требований в соответствии с присвоенными приоритетами.

 

    Другими вариантами классификаций могут быть следующие.

    Поступление требований может быть единичным и групповым.

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

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

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

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

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

Рисунок 2-Классификация входного потока

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

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

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

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

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

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

1. продолжительность интервалов между поступлениями требований статистически независимы;
2. продолжительность интервалов описывается одной и той же плотностью распределения;
3. вероятность поступления требований на достаточно малом интервале Δt зависит только лишь от величины Δt (это свойство называется стационарностью или однородностью прихода);
4. вероятность поступления требований на интервале Δt не зависит от предыстории процесса;
5. характер потока требований таков, что в любой момент времени может поступить только одно требование.

    Таким образом, простейший поток требований или совершенно случайный поток – это поток, определяющейся свойствами стационарности, ординарности и отсутствием последствия одновременно.

    Предположения о совершенно случайном входном  потоке требований эквивалентно тому, что плотность распределения  интервалов времени между последовательными поступлениями требований описывается экспоненциальным законом:

                                                                                                 (1.1)

     где λ– интенсивность поступления заявок в систему.

    Если  интервалы распределены по экспоненциальному  закону, то процесс пуассоновский. Такие  процессы называются М-процессами (Марковскими).

    Кроме закона Пуассона часто применяется  закон распределения Эрланга.

                                                                                 (1.2)

    Обозначения Кендалла систем массового  обслуживания.

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

    Детерминированный процесс обслуживания характеризуется постоянной величиной времени обслуживания

                                                                                                             (1.3)

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

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

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

     Используются  следующие обозначения:

     M – пуассоновское или экспоненциальное распределение;

     D – постоянная величина;

     E_k – распределение Эрланга;

     G – общий вид распределения;

     GI – рекуррентный входной поток.

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

                                                                                                             (1.4)

     где Н₁ – характеристика входного потока, H₂ – характеристика времени обслуживания прибора, i – число приборов.

    Например, система M /D /s – система с s приборами, обслуживающая поступающие требования за строго определенный интервал времени, поступающие требования образуют пуассоновский поток. 

    Классификация систем массового  обслуживания по характеру обслуживания

     СМО с отказами.

     Одноканальная СМО содержит один канал (n = 1), и на ее вход поступает пуассоновский поток заявок П_вх интенсивность (среднее число событий в единицу времени) которого inП_вх=λ. Так как интенсивность входящего потока может изменяться во времени, то вместо λ записывают λ(t). Тогда время обслуживания каналом одной заявки Т_об распределено по показательному закону и записывается в виде: , где λ – интенсивность отказов.