Тема 2. Классификация систем массового обслуживания как объектов моделирования

ТЕМА 2. Классификация СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ как объектов моделирования

Системы массового обслуживания (их составные компоненты и особенности организации работы)

Структура систем массового обслуживания

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

· входной поток заявок;

· каналы – как устройства обслуживания (в телефонии – одно- и многоканальные системы); 

· очереди заявок, ожидающих обслуживания; 

· выходной поток заявок.

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

Входной поток заявок

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

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

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

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

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

 

3.1.3 Каналы (устройства) обслуживания

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

 

Наличие очереди в системе

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

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

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

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

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

 

Дисциплина обслуживания заявок

По правилам занятия свободных каналов вновь поступившими заявками системы различаются по следующим признакам:

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

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

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

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

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

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

· заявки принимаются к обслуживанию в случайном порядке (например в системе ПВО объекта при отражении воздушного налета противника).

 

Время обслуживания заявок

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

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

 

Выходной поток заявок

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

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

 

Задание СМО перечислением свойств

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

X 1/ X 2/ X 3/ X 4/ X 5,

где X 1 –– характеристика входного потока заявок;

            X 2 –– характеристика обслуживания заявок;

            X 3 –– количество каналов обслуживания (1… n);

            X 4 –– длина очереди (0, m, ∞), m –– длина очереди;

            X 5 –– характеристика дисциплины обслуживания.

Х5 может принимать значение:

· Х5 = 0 –– без приоритетов;

· Х5 = 1 –– относительный приоритет;

· Х5 = 2 –– абсолютный приоритет (см. ниже).

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

1. M –– экспоненциальный закон.

2. D –– регулярное поступление заявок.

3. Е _k –– k –й закон Эрланга.

4. G ––  произвольный закон.

 

По длине очереди

По длине очереди различают следующие СМО (Рисунок 3.5):

1. Длина очереди не ограничена, что условно обозначаем как m = ∞ (СМО без отказов).

2. Длина очереди m = 0 –– СМО без очереди или с отказами, так как если заявка поступает в СМО в тот момент, когда устройство занято обслуживанием ранее поступившей заявки, то эта заявка не сохраняется и удаляется из системы).

3.  0 < m <= L_max –– СМО с ограниченной очередью (с потерями тех заявок, которые появляются на входе системы при занятости всех мест в очереди, предусмотренных условием задачи).

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

 

3.2.4 По дисциплине обслуживания

По дисциплине обслуживания различают:

· FIFO ––   дисциплина обслуживания «первой заявка пришла –– первая обслуживается», образуя очередь заявок без приоритета, то есть обслуживаемых в порядке поступления в очередь ––  все предыдущие примеры СМО с очередями;

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

 

Рисунок 3.6 ––  Одноканальная СМО с двумя очередями заявок, имеющих различные относительные приоритеты

При появлении очередной заявки с более высоким приоритетом обслуживание заявки с низким приоритетом не прекращается, а продолжается до завершения. Обычно приоритеты обозначаются целыми числами 1, 2, …М, где 1 ––  наименьший приоритет.

Очередь с абсолютным приоритетом (Рисунок 3.7): если в момент поступления в систему заявки с абсолютным приоритетом канал занят обслуживанием некоторой заявки без приоритета или с относительным приоритетом, то обслуживание заявки прерывается и канал захватывается заявкой с абсолютным приоритетом, а после завершения обслуживания этой заявки прерванная заявка поступает в канал для ее дообслуживания. Дисциплина обслуживания с абсолютным приоритетом называется LIFO (Last In First Out, то есть первой обслуживается заявка, пришедшая последней). Это в какой-то степени ассоциируется с обработкой информации в памяти типа стек.

Рисунок 3.7 ––  Одноканальная СМО с обслуживанием заявок с абсолютными приоритетами

Рисунок 3.9 ––   Удаление заявки из СМО, если общее время нахождения заявки в системе превысило заданное

По наличию обратной связи

По наличию обратной связи делят:

1. Разомкнутые СМО, в которых обратная связь отсутствует (Рисунки 3.1 – 3.9, то есть все представленные выше схемы).

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

3. Смешанные СМО (Рисунок 3.11): некоторая часть потока заявок с выхода системы подается на вход, а остальные обслуженные заявки покидают систему. Такой режим работы характерен, например, для системы разделения времени: для обслуживания заявки выделяется квант времени, и если этого достаточно для завершения обслуживания, заявка, покидает систему, иначе заявка возвращается на вход, образуя новую очередь заявок, имеющих, например, меньший относительный приоритет, чем исходный поток заявок, для продолжения процесса обслуживания.

Рисунок 3.10 –– Система технического обслуживания

                                                                               Рисунок 3.11 –– Обработка заявок квантами времени в системе разделения времени

 

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

 

Эта система имеет три состояния:

1. S₀ –– система свободна (устройство обслуживания не занято, очередь пуста).

2. S₁ –– устройство занято, очередь пуста.

3. S₂ –– система занята (устройство и место в очереди заняты).

Граф состояний системы показан на Рисунок 4.2.

 

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

 

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

                                                     – λ P ₀ + µ P ₁=0;     (1)                             

                                               λ P ₀ – (λ+µ) P ₁ +µ P ₂=0; (2)                                

                                                       λ P ₁ – µ P ₂=0; (3)                             

                                                       P ₀ + P ₁+ P ₂ =1.     (4)                                

Особенностью системы уравнений Колмогорова является то, что одно уравнение всегда лишнее, но только не последнее – нормирующее. Одно из уравнений, например, уравнение (2), из данной системы уравнений удалим как избыточное: для определения 3 неизвестных (вероятности состояний) достаточно трёх уравнений, включая обязательное –– нормирующее уравнение.

 

                                          – λ P ₀ + µ P ₁=0;   (1)                                               – λ P ₁ – µ P ₂=0;            (2)                         

                                      P ₀ + P ₁+ P ₂ =1  (3)

 

Из (1) находим .

Из (2) находим .

Тогда уравнение (3) получаем в виде , из которого получаем

P ₀  = 1/(1+ ρ + ρ²) = (1– ρ)/(1– ρ³),

так как 1+ ρ + ρ² = (1– ρ³)/(1– ρ)   ––  как сумма членов геометрической прогрессии, первый член которой b ₁=1, знаменатель q = ρ.

4.1.2. Одноканальную СМО с ограниченной очередью длины m –– систему М/М/1/m.

Структурная схема этой системы аналогична схеме системы М/М/1/1, только длина очереди не 1, а m. Граф состояний системы показан на Рисунке 4.3.

Система имеет m + 2 состояния:

· S ₀ –– система свободна;

· S ₁ ––  устройство занято, очереди нет;

· S ₂ –– в очереди 1 заявка;

· S ₃ ––  в очереди 2 заявки;

· …

· S_m –– в очереди m – 1 заявка;

· S_{m +1} ––  в очереди m заявок (следующей заявке будет отказано).

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

 

Система уравнений КОЛМОГОРОВА:

–λ P ₀ + µ P ₁ = 0;        

λ P ₀ –(λ+µ) P ₁ +µ P ₂ = 0; 

λ P ₁ – (λ +µ) P ₂ + µ P ₃ = 0;

…

λ P_{m– 1} – (λ +µ) P_m + µ P_{m+ 1} = 0;

λ P_m – µ P_{m +1} = 0;

P ₀ + P ₁ + P ₂ + … + P_m + P_{m +1} = 1 или .

Используя результаты, полученные при расчете характеристик системы М/М/1/1, здесь будем иметь следующие результаты решения системы уравнений:

P ₁ = ρ P ₀;

P ₂ = ρ² P ₀;  

P ₃ = ρ³ P ₀;  

…

P_m = ρ ^m P ₀;

P_{m +1} = ρ ^{m +1} P ₀.   

P ₀ =1/(1+ ρ+ ρ²+ ρ³ +.... + ρ ^{m +1}) = (1 – ρ)/(1 – ρ ^{m +2}), так как в знаменателе снова имеем геометрическую прогрессию с первым членом, равным 1, и знаменателем ρ<>1.

Характеристики одноканальной СМО с ограниченной очередью:

1. Вероятность простоя системы P ₀ = (1 – ρ)/(1 – ρ ^{m +2}).

2. Вероятность потерь (отказов): , ρ<>1.

3. Относительная пропускная способность (доля обслуженных заявок) .

4. Абсолютная пропускная способность А = λ q ––  интенсивность потока обслуженных заявок.

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

Вероятности соответствующего числа заявок в очереди:

· нет заявок в очереди P ₀ + P ₁;     

· одна заявка в очереди P ₂;

· две заявки в очереди P ₃  и т.д.

  = 1ρ² P ₀  + 2 ρ³ P ₀ +...+ m ρ ^{m +1} P ₀ = ρ² P ₀(1 + 2ρ +...+ m ρ ^{m –1}) =

= ρ P ₀ = .

Ряд, представленный в полученном выражении суммой, можно свернуть, но получаемая при этом формула сложна. Вот что получается

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

= ρ P ₀ .

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

 = 0* P ₀ + 1*(1 – P ₀),

так как в состоянии S₀ на обслуживании заявок нет заявок, а в остальных состояниях на обслуживании находится одна заявка (как при отсутствии очереди, так и наличии её!).

Для вероятности 1– P ₀ получаем

1 – P ₀  = ((1 – ρ ^{m +2}) – (1 – ρ))/(1 – ρ ^{m +2}) = (ρ – ρ ^{m +2})/(1 – ρ ^{m +2}).

Поэтому

 = (ρ – ρ ^{m +2})/(1 – ρ^m+2).

 

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

.

8. Среднее время ожидания в очереди определяется из следующих соображений.

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

Вероятность нахождения заявки только в канале равна P ₁, вероятность того, что длина очереди равна 1, равна P ₂ и т.д.

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

Умножив и разделив это выражение на ρ, получаем

 

 

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

.

 

ТЕМА 2. Классификация СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ как объектов моделирования