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

1) входящий поток заявок;

2) очередь;

3) каналы обслуживания;

4) выходящий поток обслуженных  заявок.

Требование (заявка) — каждый отдельный запрос на выполнение какой-либо работы.

Входящий поток требований — требования, поступающие от всех источников в обслуживающую систему.

Очередь — совокупность требований, ожидающих обслуживания.

Канал обслуживания — обслуживание, состоящее из последовательности фаз обслуживания. Фаза обслуживания — последовательность операций, выполняемых на отдельном обслуживающем аппарате.

Выходящий поток требований — поток требований, покидающих систему после обслуживания.     [http://www.dis.ru/library/detail.php?ID=26707]

Эффективность функционирования системы массового обслуживания определяется ее пропускной способностью — относительным числом обслуженных заявок. .  [3]

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

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

 По числу каналов системы массового обслуживания подразделяют на одноканальные  (n= 1)  , когда имеется один канал обслуживания)  и многоканальные,  точнее n -канальные  (когда количество каналов n ≥ 2 ). [8]

Многоканальные системы массового обслуживания могут состоять из однородных каналов, либо из разнородных,  отличающихся длительностью обслуживания одной заявки.  Практически время обслуживания каналом одной заявки Tоб является непрерывной случайной величиной. Однако при условии абсолютной однородности поступающих заявок и каналов время обслуживания может быть и величиной постоянной (T const об= ). [9]

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

1. Системы массового обслуживания с отказами, в которых заявка, поступившая на вход системы массового обслуживания в момент, когда все каналы заняты,  получает  «отказ»  и покидает СМО («пропадает»). Чтобы эта заявка все же была обслужена, она должна снова поступить на вход системы массового обслуживания и рассматриваться при этом как заявка, поступившая впервые. Примером системы массового обслуживания с отказами может служить работа АТС: если набранный телефонный номер (заявка, поступившая на вход) занят, то заявка получает отказ, и,  чтобы дозвониться по этому номеру,  следует его набрать еще раз  (заявка поступает на вход как новая).

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

3. Системы массового обслуживания смешанного типа  (с ограниченным ожиданием). Это такие системы, в которых на пребывание заявки в очереди накладываются некоторые ограничения. [8]

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

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

 

 

2.4  Потоки событий

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

Поток событий называется простейшим (или стационарным пуассоновским) , если он одновременно стационарен, ординарен и не имеет последействия. Название "простейший" объясняется тем, что СМО с простейшими потоками имеет наиболее простое математическое описание. Заметим, что регулярный поток не является "простейшим", так как он обладает последействием: моменты появления событий в таком потоке жестко зафиксированы. Для простейшего потока частота поступления требований в систему подчиняется закону Пуассона, то есть вероятность поступления за время t ровно k требований задается по формуле:  

  (6)

Простейший поток обладает четырьмя основными свойствами: ординарностью, стационарностью, регулярностью и отсутствием последействия.

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

Стационарным называют поток, для которого математическое ожидание числа требований, поступающих в систему в единицу времени ,  не меняется во времени. Таким образом, вероятность поступления в систему определенного количества требований в течение заданного промежутка времени t,  зависит от его величины и не зависит от начала его отсчета на оси времени.  [13]

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

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

Поток событий называется потоком без последействия, если для любых двух непересекающихся участков времени  T1 и T2 — число событий, попадающих на один из них, не зависит от числа событий, попадающих на другие. Например, поток пассажиров, входящих в метро, практически  не имеет последействия. А, скажем,поток покупателей,  отходящих с покупками от прилавка, уже имеет последействие (хотя бы потому,  что интервал времени между отдельными покупателями не  может быть меньше, чем минимальное время обслуживания каждого из них).  [3]

2.5  Случайные процессы. Марковские процессы.

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

Примеры: 1. Система S – технологическая система (участок станков). Станки время от времени выходят из строя и ремонтируются. Процесс, протекающий в этой системе, случаен. [10]

2. Система S – самолет, совершающий рейс на заданной высоте по определенному маршруту. Возмущающие факторы – метеоусловия, ошибки экипажа и т.д., последствия – «болтанка», нарушение графика полетов и т.д.

Пример. Система S – группа самолетов, участвующих в воздушном бою. Пусть x – количество «красных» самолетов, y – количество «синих» самолетов. К моменту времени t0 количество сохранившихся ( не сбитых) самолетов соответственно – x0, y0. Нас интересует вероятность того, что в момент времени  t0+ 1  численный перевес будет на стороне «красных». Эта вероятность зависит от того, в каком состоянии находилась система в момент времени t0, а не от того, когда и в какой последовательности погибали сбитые до момента t0 самолеты.

Случайный процесс, протекающий в системе, называется Марковским, если для любого момента времени t0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t0 и не зависят от того, когда и как система пришла в это состояние. [11]

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

Схема возможных состояний системы и возможных переходов из состояния в состояние показана на рисунке 2 (такая схема называется графом состояний).

Построить  граф состояний следующего случайного  процесса:

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

Решение.  Возможные состояния системы:  S0 - оба узла исправны; S1 — первый узел ремонтируется,  второй исправен;  S2 — второй узел ремонтируется,  первый исправен;  S3 — оба узла ремонтируются. Граф системы приведен на рис. 15.1

 

 [13]

 

2.6  Процессы гибели и размножения

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

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

 

Рассмотрим упорядоченное множество состояний системы S0, S1,…, Sn.  Переходы

могут осуществляться из любого состояния только в состояния с соседними номерами, т.е. из состояния Sk возможны переходы либо в состояние Sk −1, либо в состояние Sk +1 [14]

 

3.1 Системы массового обслуживания с ожиданием

 

СМО с ожиданием распространены наиболее широко. Их классифицируют по двум большим группам:

- Одноканальные системы  массового обслуживания с ожиданием.

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

 

-Многоканальные системы  массового обслуживания с ожиданием

В отличие от модели одноканальной СМО с отказами (потерями) в модели многоканальной СМО используется n>1 обслуживающих приборов с одинаковой интенсивностью обслуживания µ. [12]

3.1.1  Одноканальная СМО с ожиданием

Рассмотрим одноканальную СМО с ожиданием. 
     Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание поток имеет интенсивность λ. Интенсивность потока обслуживания равна μ (т. е. в среднем непрерывно занятый канал будет выдавать μ обслуженных заявок). Длительность обслуживания — случайная величина, подчиненная показательному закону распределения. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания. 
     Рассмотрим систему с ограниченной очередью. Предположим, что независимо от того, сколько требований поступает на вход обслуживающей системы, данная система (очередь + обслуживаемые клиенты) не может вместить более N-требований (заявок), из которых одна обслуживается, а (N-1) ожидают. Клиенты, не попавшие в ожидание, вынуждены обслуживаться в другом месте и такие заявки теряются. Наконец, источник, порождающий заявки на обслуживание, имеет неограниченную (бесконечно большую) емкость. 
     Обозначим Pn - вероятность того, что в системе находится n заявок. Эта величина вычисляется по формуле:

   (7) 
     Здесь   - приведенная интенсивность потока.  Тогда вероятность того, что канал обслуживания свободен и в системе нет ни одного клиента, равна:  
    

       C учетом этого можно обозначить

 

    Определим характеристики  одноканальной СМО с ожиданием  и ограниченной длиной очереди, равной (N-1): 
     вероятность отказа в обслуживании заявки: 
     Pотк=РN=                 (8) 
     

относительная пропускная способность системы: 
                                    (9) 
     абсолютная пропускная способность: 
     А=q∙λ;                                                                 (10)

среднее число находящихся в системе заявок: 
        (11) 
     среднее время пребывания заявки в системе: 
                                                         (12)

 

     средняя продолжительность пребывания клиента (заявки) в очереди: 
     Wq=Ws- 1/μ;                                                        (13) 
     среднее число заявок (клиентов) в очереди (длина очереди): 
     Lq=λ(1-PN)Wq.                                                     (14)