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

Тема № 5 Элементы теории массового обслуживания Теория массового обслуживания (иначе называемая теорией очередей) изучает случайные процессы в системах массового обслуживания с приложением к рациональному построению этих систем. Она устанавливает зависимость между характером потока заявок (требований), производительностью отдельного канала (обслуживающего аппарата), числом каналов и эффективностью обслуживания. Система массового обслуживания – это объект, в котором выполняется последовательность (элементарных) операций. Характерной особенностью массового обслуживания является наличие потока однородных (идентичных) требований (событий, заявок), которые подвергаются обслуживанию. Множество моментов поступления в систему требований называется входным потоком требований данной системы массового обслуживания. Будем считать, что в момент поступления требования происходит событие. Тогда множество моментов, когда происходят события, называется потоком однородных событий. Операции в системах массового обслуживания выполняются приборами. Считается, что прибор (обслуживающий прибор, канал или линия) может одновременно выполнять лишь одну операцию. Операции, выполняемые приборами, называют ещё операциями обслуживания требований. Приборов в системе массового обслуживания конечное или счётное множество. Система массового обслуживания, содержащая один прибор, называется одноканальной (однолинейной), если приборов не меньше двух, то многоканальной (многолинейной). Очередью называется совокупность требований, ожидающих обслуживание в момент, когда все приборы заняты обслуживанием других требований. Ожидающие требования находятся в накопителе, который характеризуется ёмкостью, т. е. максимальным числом требований, которые могут присутствовать в нём одновременно. Ёмкость накопителя может быть конечной (конечный накопитель) и бесконечной (бесконечный накопитель). Характерной особенностью систем массового обслуживания является наличие правил, некоторого порядка, в соответствии с которым происходит выбор требований из очереди при освобождении канала, называемого дисциплиной обслуживания. В большинстве моделей принята дисциплина «первый пришёл – первый обслужен» это прямой порядок обслуживания (возможны и инверсный, и случайный порядки). Рассмотрим функционирование простейших систем массового обслуживания. 1). Одноканальная система с ожиданием. Графически ее можно изобразить следующим образом: где a – поток требований на обслуживание, b – поток обслуженных требований, - источник требований, - накопитель, 2 - обслуживающий прибор. Из источника требование поступает в накопитель, затем, если прибор свободен, то требование обслуживается, иначе требование остаётся в накопителе, становясь в конец очереди. Пример такой системы - приём экзамена одним экзаменатором. 2). Система с конечным накопителем. где с – поток потерянных требований. В системе может находиться N требований (в накопителе может находиться N  1 требование). Если в накопителе N  1 место уже занято, то очередное требование теряется. Самостоятельно приведите пример такой системы. 3.Система с потерями или отказами. Это вариант системы 2, в которой N  1 . Ожидание здесь не допускается, так как нет накопителя. Пример такой системы – поток вызовов на телефонный номер. Для классификации систем массового обслуживания используется символика, предложенная в середине 50-х годов XX века Д. Кендаллом. Систему обслуживания кодируют символами: G1 / G2 / k / N / Q * , где G1 обозначает входящий поток требований (поток с соответствующим распределением интервалов между моментами поступления требований); G2 распределение времени обслуживания; k - число обслуживающих приборов, N максимальная длина очереди или емкость накопителя (может быть N   , если N  0 это система с отказами, 0  N   - система с конечным накопителем), вместо A / B / k /  часто пишут A / B / k ; Q* - вводится для описания системы массового обслуживания с приоритетами и для однородного потока требований не рассматривается. Основные показатели эффективности функционирования или качества обслуживания системой массового обслуживания – это: 1) вероятность потери требования в системах с потерями; 2) функция распределения времени ожидания требованием начала обслуживания; 3) среднее время ожидания требованием начала обслуживания; 4) распределение интервала времени занятости прибора; 5) распределение величины очереди. Модели массового обслуживания могут характеризоваться и определяться указанием класса случайных процессов, описывающих процесс обслуживания. Отсюда возникают понятия марковских и немарковских моделей систем массового обслуживания. 3 Марковская модель массового обслуживания – это описание систем массового обслуживания с помощью марковского процесса с дискретным множеством состояний. Отказ от таких требований в немарковских моделях обычно приводит к усложнению задачи описания характеристик систем массового обслуживания. Конкретной моделью системы массового обслуживания, описываемой марковским процессом, является одноканальная система массового обслуживания M / M /1/  или M / M /1 . Обозначение M означает, что интервалы между поступлением требований (длительность обслуживания) имеют показательное распределение. Пусть на вход прибора поступает пуассоновский поток требований с параметром  . Найдём распределение случайной величины 1 - времени до первого появления события в пуасоновского процессе  x , x   0,   . По определению, F1  x   P  1  x . Событие  1  x означает, что на отрезке  0, x  произошло хотя бы один раз интересующее нас событие, что можно записать в виде  x  1 , так как  x – число появлений события на отрезке  0, x  . Поэтому P 1  x   P x  1  1  P x  0  1  e x , так как случайная величина  x распределена по закону Пуассона с параметром  x . Следовательно, случайная величина  1 имеет показательное распределение с параметром  x . В силу однородности во времени делаем вывод, что в пуассоновском потоке интервалы времени между поступлениями требований имеют показательное распределение. Итак, пусть на вход системы массового обслуживания подается простейший поток однородных событий с параметром  (т. е. пуассоновский), а время обслуживания отдельного требования - случайная величина, имеющая показательное распределение с параметром  . Эта последняя величина не зависит от совокупности моментов событий входящего потока и времени обслуживания других требований. В данной модели число требований в системе образует процесс размножения и гибели  Nt , t  T  [0; ) с бесконечной матрицей интенсивностей:  Если 0   0  (   )  0  .  (   )             , то случайная величина Nt имеет стационарное распределение  k k k 1      P  N t  k      1              для любых k   0 , которое является предельным. В качестве показателей эффективности системы массового обслуживания с отказами будем рассматривать: A - абсолютную пропускную способность системы массового обслуживания, т.е. среднее число заявок, обслуживаемых в единицу времени; Q - относительную пропускную способность, т.е. среднюю долю пришедших заявок, обслуживаемых системой; 4 Pотк - вероятность отказа, т.е. того, что заявка покинет систему массового обслуживания необслуженной; k - среднее число занятых каналов (для многоканальной системы). 1. Одноканальная система с отказами. Рассмотрим следующую задачу. Имеется один канал, на который поступает поток заявок с интенсивностью  . Поток обслуживаний имеет интенсивность  . Найти предельные вероятности состояний системы и показатели ее эффективности. Здесь и в дальнейшем будем предполагать, что все потоки событий, переводящие систему массового обслуживания из состояния в состояние, - простейшие. К ним относится и поток обслуживаний - поток заявок, обслуживаемых одним непрерывно занятым каналом. Поскольку среднее время между двумя произвольными соседними событиями простейшего потока обратно по величине интенсивности потока, а для потока обслуживаний это время есть время обслуживания (одной заявки), то среднее время 1 обслуживания Tcp  .  Система массового обслуживания имеет два состояния: S0 - канал свободен, S1 - канал занят В предельном стационарном режиме система уравнений Колмогорова для вероятностей состояний будет иметь вид:  p  p 1  0 ,   p1   p0  т.е. система вырождается в одно уравнение. Учитывая нормировочное условие p0+p1=1, найдем из полученной предельные вероятности состояний:   p0  , p1    Предельные вероятности состояний p0 и p1 можно выразить через средние времена простоя канала Tnp и обслуживания одной заявки Тcp. Для этого в формулы для вероятно1 1 стей следует подставить   и  . В результате получим Tnp Tcp p0  Tcp Tcp  Tnp , p1  Tnp Tcp  Tnp Предельные вероятности выражают среднее относительное время пребывания системы в состоянии S0 (когда канал свободен) и S1 (когда канал занят), т.е. определяют соответственно относительную пропускную способность Q системы и вероятность отказа Ротк: Tcp Tnp Q , Pomk  Tcp  Tnp Tcp  Tnp Почему p0  Q ? В самом деле, p0 есть вероятность того, что заявка будет принята к обслуживанию (система находится в состоянии S0, т.е. канал свободен). Всего в единицу времени приходит в среднем  заявок и из них обслуживается  p0 заявок. Тогда доля обслуживаемых заявок по отношению ко всему потоку заявок определяется величиной p Q  0  p0 .  5 Абсолютную пропускную способность (или, иначе, среднее число заявок, поступающих в систему массового обслуживания в единицу времени) найдем, умножив относительную пропускную способность Q на интенсивность потока заявок:  A  Q   Пример. В фирму поступает простейший поток заявок на телефонные переговоры с интенсивностью  = 90 вызовов в час, а средняя продолжительность разговора по телефону Тcp = 2 мин. Определить показатели эффективности работы системы массового обслуживания (телефонной связи) при наличии одного телефонного номера. 1 Решение. Интенсивность потока обслуживаний   = 1/2 = 0,5(1 /мин) = 30(1/ч). Tcp Относительная пропускная способность системы массового обслуживания Q = 30/(90 + 30) = 0,25, т.е. в среднем только 25% поступающих заявок осуществят переговоры по телефону. Соответственно вероятность отказа составит Pотк = 1 — 0,25 = 0,75 . Абсолютная пропускная способность системы массового обслуживания A = 90 • 0,25 = 22,5 , т.е. в среднем в час будут обслужены 22,5 заявки на переговоры. Очевидно, что при наличии только одного телефонного номера система массового обслуживания будет плохо справляться с потоком заявок. 2. Многоканальная система с отказами (задача Эрланга). Здесь мы рассмотрим одну из первых по времени, «классических» задач теории массового обслуживания; эта задача возникла из практических нужд телефонии и была решена в 1909 г. датским инженеромматематиком А.К. Эрлангом. Задача ставится так: имеется п каналов (линий связи), на которые поступает поток заявок с интенсивностью  . Поток обслуживаний каждого канала имеет интенсивность  . Найти предельные вероятности состояний системы и показатели ее эффективности. Система массового обслуживания имеет следующие состояния (нумеруем их по числу заявок, находящихся в системе): S0, S1..., Sn, где Sk - состояние системы, когда в ней находится к заявок, т.е. занято k каналов. Граф состояний системы массового обслуживания соответствует процессу гибели и размножения Поток заявок последовательно переводит систему из любого левого состояния в соседнее правое с одной и той же интенсивностью  . Интенсивность же потока обслуживаний, переводящих систему из любого правого состояния в соседнее левое, постоянно меняется в зависимости от состояния. Действительно, если система массового обслуживания находится в состоянии S2 (два канала заняты), то она может перейти в состояние S1 (один канал занят), когда закончит обслуживание либо первый, либо второй канал, т. е. суммарная интенсивность их потоков обслуживаний будет 2  . Аналогично суммарный поток обслуживаний, переводящий системe массового обслуживания из состояния S3 (три канала заняты) в S2, будет иметь интенсивность 3  , т.е. может освободиться любой из трех каналов, и т. д. В формуле для схемы гибели и размножения для предельной вероятности состояния S0 получим 1   2 k n    p0  1    ...   ...    2 ! 2 k ! k n ! n  6  2 k n , ,..., ,..., - коэффициенты при р0 в  2! 2 k ! k n ! n выражениях для предельных вероятностей р1, р2,..., pn. Заметим, что в эту формулу интенсивности  и  входят не по отдельности, а только где члены разложения в виде отношения  . Обозначим     и будем называть величину  приведенной интенсивностью потока заявок или интенсивностью нагрузки канала. Она выражает среднее число заявок, приходящих за среднее время обслуживания одной заявки. Пользуясь этим обозначением, перепишем формулу в виде: 1  1 2 1 k 1 n   p0  1      ...    ...     2! k! n !  k p при k от 1 до n. k! 0 Вероятность отказа системы массового обслуживания есть предельная вероятность того, что все п каналов системы будут заняты, т. е. n Pomk  pn  p n! 0 Отсюда находим относительную пропускную способность - вероятность того, что заявка будет обслужена: n Q  1  Pomk  1  p n! 0 Абсолютную пропускную способность получим, умножая интенсивность потока заявок  на Q:   n  A  Q   1  p   n ! 0  При этом pk  Осталось только найти среднее число занятых каналов k . Эту величину можно было бы найти «впрямую», как математическое ожидание дискретной случайной величины с возможными значениями 0,1,..., п и вероятностями этих значений p0 , p1 ,... , pп . Однако среднее число занятых каналов можно найти проще, если учесть, что абсолютная пропускная способность A системы есть не что иное, как интенсивность потока обслуженных системой заявок (в единицу времени). Так как каждый занятый канал обслуживает в среднем  заявок (в единицу времени), то среднее число занятых каналов  A n  k    1  p    n ! 0  Пример. В условиях предыдущего примера определить оптимальное число телефонных номеров в фирме, если условием оптимальности считать удовлетворение из каждых 100 заявок на переговоры в среднем не менее 90 заявок. Решение. Интенсивность нагрузки канала  = 90/30 = 3, т.е. за время среднего (по продолжительности) телефонного разговора Тcp = 2 мин поступает в среднем 3 заявки на переговоры. Будем постепенно увеличивать число каналов (телефонных номеров) n = 2, 3, 4,... и определим для получаемой n-канальной системы массового обслуживания 7 характеристики обслуживания. Значения характеристик систем массового обслуживания сведем в таблицу Показатели эффективности Обозначение Число каналов (телефонных номеров) 1 2 3 4 5 6 Относительная способность пропускная Q 0,25 0,47 0,65 0,79 0,90 0,95 Абсолютная способность пропускная A 22,5 42,3 58,8 71,5 80,1 85,3 По условию оптимальности Q > 0,9, следовательно, в фирме необходимо установить 5 телефонных номеров (в этом случае Q = 0,90 ). При этом в час будут обслуживаться в среднем 80 заявок (A = 80,1), а среднее число занятых телефонных номеров (каналов) A 80,1 k   2, 67 к =  30 Тут уже проглядывает некоторый намек на оптимизацию. В самом деле, содержание каждого канала в единицу времени обходится в какую-то сумму. Вместе с тем, каждая обслуженная заявка приносит какой-то доход (если речь идет о системе массового обслуживания, для которых этот доход можно оценить). Умножая этот доход на среднее число заявок А, обслуживаемых в единицу времени, мы получим средний доход от систем массового обслуживания в единицу времени. Естественно, при увеличении числа каналов этот доход растет, но растут и расходы, связанные с содержанием каналов. Что перевесит - увеличение доходов или расходов? Это зависит от условий операции, т. е. от «платы за обслуживание заявки» и от стоимости содержания канала. Зная эти величины, можно найти оптимальное число каналов, наиболее экономически эффективное. При решении многих практических задач приходиться сталкиваться с системами массового обслуживания с очередью (очередь в любой кассе, очередь к врачу и т. д.). Число мест в очереди может быть ограниченным (в таблице это число обозначено как m), а может быть бесконечным. Если все каналы заняты, то заявка на обслуживание становится в очередь. Если и все места в очереди также заняты, то заявка покидает систему массового обслуживания, т. е. не обслуживается. Вероятностные характеристики систем массового обслуживания с очередями приведены в двух крайних справа столбцах  ниже приведенной таблицы, в которой   .  К анализу различных систем массового обслуживания Вы вернетесь при изучении многих общепрофилирующих и специальных дисциплин