Системы массового обслуживания (СМО)

1. Общие понятия систем массового обслуживания (СМО).

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

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

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

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

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

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

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

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

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

  2.  Классификация СМО и их основные элементы

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

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

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

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

2) с отказами (нулевое ожидание или явные потери). «Отказанная» заявка может вновь поступить в систему, чтобы её обслужили (вызов абонента через АТС);

3) смешанного типа (ограниченное ожидание). Есть ограничение на длину очереди (автосервис). Ограничение на время пребывания заявки в СМО (особые условия обслуживания в КБ).

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

Эффективность функционирования СМО определяется следующими характеристиками:

1)  показателями эффективности использования СМО:

абсолютная пропускная способность (АПС) – среднее число заявок, обслуживаемых в единицу времени (А); относительная пропускная способность – отношение АПС к среднему числу заявок, поступивших за единицу времени  (Q); средняя продолжительность периода занятости СМО (Те); коэффициент использования СМО – средняя доля времени, в течении которого система занята обслуживанием заявок.

2) показателями качества обслуживания заявок:

среднее время ожидания заявки в очереди (T line); среднее время пребывания заявки в СМО (T sys); вероятность отказа заявки в обслуживании без ожидания; вероятность немедленного приёма заявки; среднее число заявок в очереди (N line); среднее число заявок, находящихся в СМО (N sys).

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

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

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

где Т - среднее значение интервала между поступлением очередных требований.

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

потоком).

Эти свойства следующие:

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

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

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

Доказано, что для простейшего потока распределение числа требований, поступающих в систему за время t, подчиняются закону распределения Пуассона с параметром лt, а именно вероятность того, что в обслуживающую систему за время t поступит именно k требований (k=0,1,…):

где - среднее число требований, поступивших на обслуживание в единицу времени.

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

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

  4. Анализ системы обслуживания

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

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

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

При показательном законе распределения времени обслуживания ве­роятность события, что время обслуживания продлиться не более чем t, равна:

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

,                                (4.1)

где - среднее время обслуживания одного требования одним об­служивающим устройством.

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

                                       (4.2)

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

Для СМО с ожиданием количество обслуживаемых устройств n должно быть строго больше коэффициента загрузки (требование установившегося или стационарного режима работы СМО) :

  n>б.  (4.3) 

В противном случае число поступающих требований будет больше суммар­ной производительности всех обслуживающих устройств, и очередь будет неограниченно расти.

Для СМО с отказами и смешанного типа это условие может быть ос­лаблено, для эффективной работы этих типов СМО достаточно потребо­вать, чтобы минимальное количество обслуживаемых устройств n было не меньше коэффициента загрузки :    (4.3)

5. Модели СМО с пуассоновским входным потоком с экспоненциальным распределением длительности обслуживания

Простейшей одноканальной моделью с показательным распределением как длительностей интерва­лов между поступлениями требований, так и длительностей обслу­живания. При этом плотность распределения длительностей интер­валов между поступлениями требований имеет вид

,                                                                        (5.1)

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

Плотность распределения длительностей обслуживания:

,                                                                         (5.2)

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

Потоки заявок и обслуживании простейшие.

5.1 Одноканальная система с отказами.

Необходимо определить абсолютную и относительную пропускную способность системы, вероятность отказа Ротк и среднее время нахождения заявки в системе Тсис.

У такой системы массового обслуживания имеются два состояния:

S0  - канал свободен (ожидание);

S1  - канал занят (идет обслуживание заявки).

Обозначим вероятности состояний: P0(t)  - вероятность состояния «канал свободен»; P1(t) - вероятность состояния «канал занят», очевидно, что P0(t)+ P1(t)=1.

Примем, что первая заявка пришла в  момент t=0 , т. е. P1(0)=1 и определим вероятность P1(t+Дt) того, что система в момент t+Дt будет занята. Это может произойти в двух случаях:

- система была занята в момент t (с вероятностью P1(t)) и не освободилась за Дt (вероятность этого 1-µ Дt);  В силу отсутствия последействия эти события независимы и вероятность такого случая равна произведению вероятностей P1(t)(1-µ Дt);

- система была свободна в момент t (с вероятностью P0(t)), но за время Дt пришла заявка (вероятность этого л Дt);  вероятность такого случая равна л Дt P0(t).

В итоге получаем, что P1(t+Дt)= P1(t)(1-µ Дt)+ P0(t) л Дt, откуда получаем разностное уравнение

[P1(t+Дt)- P1(t)]/ Дt = - µ P1(t)+ л P0(t).

Используя  P1(t)=1- P0(t) , получаем отсюда

[P1(t+Дt)-P1(t)]/Дt = л-( л - µ) P1(t),

что при Дt→0 приводит нас к дифференциальному уравнению для определения вероятности P1(t):  .

Получая аналогичным образом второе уравнение относительно P0(t), мы приходим к системе дифференциальных уравнений Колмогорова для вероятностей состояний:

                                                               (5.3)

Система линейных дифференциальных уравнений (5.3) имеет решение с учетом нормировочного условия P0(t) + P1(t) = 1 . Реше­ние данной системы называется неустановившимся, поскольку оно непосредственно зависит от t  и выглядит следующим образом:

,                                                                (5.4)

P1(t) = 1 - P0(t) = 1 .                                (5.5)                                                        

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

P0(t)  есть не что иное, как относительная пропускная способность системы q.

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

  q = P0(t),                        (5.6)                                        

По истечении большого интервала времени (при ) дости­гается стационарный (установившийся) режим:

,                                                                                (5.7)

Зная относительную пропускную способность, легко найти аб­солютную. Абсолютная пропускная способность (А) - среднее чис­ло заявок, которое может обслужить система массового обслужива­ния в единицу времени:

.                                                                                (5.8)

Вероятность отказа в обслуживании заявки будет равна вероят­ности состояния «канал занят»:

.                                                        (5.9)

Данная величина Pотк=P1  может быть интерпретирована как сред­няя доля необслуженных заявок среди поданных.

Пример 5.1. Пусть одноканальная СМО с отказами представля­ет собой один пост ежедневного обслуживания (ЕО) для мойки ав­томобилей. Заявка - автомобиль, прибывший в момент, когда пост занят, - получает отказ в обслуживании. Интенсивность потока ав­томобилей = 1,0 (автомобиль в час). Средняя продолжительность обслуживания - 1,8 часа. Поток автомобилей и поток обслужива­нии являются простейшими.

Требуется определить в установившемся режиме предельные значения:

- относительной пропускной способности q;

- абсолютной пропускной способности А;

- вероятности отказа Pотк ;

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

Решение

1. Определим интенсивность обслуживания:

.

2. Вычислим относительную пропускную способность:

.

Величина q означает, что в установившемся режиме система будет обслуживать примерно 35% прибывающих на пост ЕО авто­мобилей.

3. Абсолютную пропускную способность определим по формуле:

.

Это означает, что система (пост ЕО) способна осуществить в среднем 0,356 обслуживания автомобилей в час.

5. Вероятность отказа:

.

Это означает, что около 65% прибывших автомобилей на пост ЕО получат отказ в обслуживании.

5. Определим номинальную пропускную способность системы:

(автомобилей в час).

Оказывается, что Аном  в 1,5 раза   больше, чем фактическая пропускная способность, вычисленная с учетом случай­ного характера потока заявок и времени обслуживания.

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

Обозначения:

  - система рассматривается в моменты прихода очередной к-й заявки, начиная с момента прихода первой заявки (к=1,2,3…., n)

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

Дtk  -  интервал времени между приходом к-й и (к+1)-й заявками;

stk - время обслуживания к-й заявки.

  - Переменные состояний системы:

WTk  - время ожидания для к-й заявки;

IDTk – время простоя СМО в ожидании к-й заявки.

  - Выходные переменные (результат):

Тож – среднее время ожидания заявки в очереди;

Тпр – среднее время простоя СМО в ожидании очередной заявки;

Как находить средние величины. ; ;

Рис.1. Временная диаграмма процессов прибытия и обслуживания заявок

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

  Для простейшего входного потока и показательного времени обслуживания переменные Дtk  - и stk -  вычисляются по формулам: Дtk  = - ln(r1)/ л ; stk = - tобс ln(r2), где –  r1 и r2  очередные случайные числа с равномерным распределением, полученные в программном датчике случайных чисел.

  Блок-схема расчетов рассматриваемой одноканальной СМО представлена на рис. 2 

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

  В блоке 2 генерируется время появления новой заявки, как сумма tk+1=tk+Дtk.

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

  Продолжительность этого обслуживания вычисляется в блоке 4.

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

  Поэтому в блоке 6 время простоя обнуляется.

  Время ожидания новой заявки в этом случае вычисляется в блоке 7 и равно разности между временем обслуживания предыдущей заявки и относительным временем ее прибытия.

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

  Если же относительное время появления новой заявки больше времени обслуживания предыдущего требования, то ей ждать не придется и в блоке 11 время ожидания зануляется.

  Зато возникнет простой системы, продолжительность которого вычисляется в блоке 12, как разность этих времен.

  Полное время простоя СМО. вычисляется в блоке 13.

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

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

установившийся режим и сравнивать эти характеристики с их теоретическими значениями

5.2 Многоканальные системы с отказами и СМО смешанного типа.

Формулы Эрланга

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

Пусть n – число каналов (обслуживающих приборов.

Коэффициент загруженности СМО  .

Тогда вероятность pk, что занято к приборов из n имеющихся

Отсюда при к=0 получаем вероятность того, что система простаивает, т. е. все приборы свободны .

При k=n получаем вероятность отказа Ротк, т. е. того, что все приборы заняты

.

На базе этих вероятностей можно рассчитать основные характеристики СМО:

- среднее число занятых приборов

- среднее число свободных приборов

- коэффициент простоя .  Очевидно, что если этот коэффициент недопустимо велик, то надо уменьшать число каналов n

В 50-х годах прошлого века доказал справедливость формул Эрланга для произвольного распределения времени обслуживания с естественным конечности среднего времени обслуживания  tобс<∞. ___________________________________________________

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

n	Ротк  = Рn
1 2 3 4 5	0.5 0.2 0.062 0.015 0.003

Пример 1.  Спроектировать АТС, имеющую загрузку с л=0.5 выз/мин, чтобы обеспечить малую вероятность отказа Ротк<0.01, если статистические подсчеты показали, что средняя продолжительность разговора  tобс =2 мин. 

Находим коэффициент загрузки б=л tобс =1. Есть таблицы для вычисления вероятностей Эрланга. По ним или с помощью программы, вычисляющей эти вероятности, находим, что АТС надо проектировать на 5 линий связи.

  2. Смешанные СМО с очередью и отказами

По-прежнему имеем и число каналов  n, но имеется еще

буферная память объёма  m.

Вероятность, что нет заявок в СМО (вероятность простоя):

.

Вероятность, что  k каналов занято: .

Вероятность, что  все каналы заняты и s заявок в очереди: .

Вероятность отказа: .

Пропускная способность СМО: .

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

Средняя длина очереди: .

Общее время пребывания в системе: .

Пример 2. Телеателье. мастер, комната хранения объёмом , дня, телевизоров в день. .

Вероятность отказа = (несут домой каждый 5-й ТВ).

Абсолютная пропускная способность Q=л(1- Ротк)=0.4 ТВ в сутки.

Ср. число ТВ, ожидающих ремонта, Мож=1.2, а среднее время ремонта вообще Тсис=4.4 суток - очень велико, так как мало обслуживающих приборов (мастеров).

Оптимизация. Надо нанять еще одного мастера, тогда будет Ротк =0.021, т. е вероятность отказа уменьшится в 10 раз!