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

Случай произвольного распределения длительностей обслуживания.

Весьма несложным оказывается вычисление ожидаемого количества требований в системе массового обслуживания и средней продолжительности их пребывания в ней в том случае, когда входной поток требований характеризуется экспоненциальным распределением, а относительно вида распределения длительностей обслуживания не делается никаких специальных предположений (т. е. в случае, когда модель относится к типу M/G/1).

Пусть

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

Соотношения (29) и (32) часто называют формулами Поллачека -- Хинчина.

Нетрудно проверить, что если плотность распределения g (f) является экспоненциальной и, следовательно, V = 1/м2, то формулы (29), (30) и (32) преобразуются соответственно в формулы (13), (15) и (20). Эти формулы определяют также соответствующие математические ожидания в случае, когда скорость обслуживания постоянна, так как при этом V = 0. Другими словами, при

V = 0 полученные выше формулы описывают модель типа M/D/I, Обратите внимание на то, что средние значения всех указанных выше показателей являются линейными функциями V и зависят лишь от частоты поступления требований л, траффик-интенсивности р и дисперсии

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

Заметим далее, что в условиях статистического равновесия

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

Дисциплина очереди при наличии приоритета.

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

он обнаружит на своем рабочем столе ряд телефонограмм, среди которых может оказаться и телефонограмма от какого-нибудь важного должностного лица, в подчинении которого данный молодой административный работник находится. Скорее всего, что в первую очередь он уделит внимание именно этой телефонограмме. Предположим, что требования, поступающие на вход системы обслуживания, можно подразделять на г различных категорий, каждой из которых приписывается приоритет k (k = 1, 2, . . ., г), выраженный соответствующим номером. Допустим, что приоритет падает с увеличением его номера, т. е. приоритет 1 оказывается наивысшим, а приоритет г -- самым низким. Как только прибор заканчивает обслуживание того или иного требования, он немедленно переходит к обслуживанию следующего требования, отдавая при этом предпочтение тому из находящихся в очереди требований, приоритет которого оказывается наиболее высоким. (Если в очереди находится несколько требований с одинаковыми приоритетами, очередность их обслуживания определяется правилом ?первым пришел -- первым обслуживаешься?.) В некоторых случаях, кроме того, предполагается, что при поступлении в систему обслуживания требования с более высоким приоритетом по сравнению с приоритетом требования, которое в этот момент находится в процессе обслуживания, система бросает уже начатую процедуру обслуживания и переключается на обслуживание требования с более высоким приоритетом. Другими словами, предполагается использование дисциплины нокаутирующих приоритетов. Приведенные ниже результаты относятся к случаю ненокаутирующих приоритетов. Допустим, что поток требований, обладающих приоритетом k, является пуассоновским при значении k = 1, 2, . . ., r, причем соответствующие средние частоты поступлений равняются лk.

Предположим также, что каждый приоритет k (k = 1, 2, . . ., г) характеризуется распределением длительностей обслуживания с плотностью gk (t) совершенно произвольного вида и

и будем предполагать, что о> < 1. (Это гарантирует возможность постепенного перехода системы в состояние статистического равновесия.)

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

Нетрудно убедиться в том, что при r = 1 выражение (35) сводится к (32). Поскольку лk / есть вероятность того, что вновь поступившее требование обладает приоритетом k, среднее время пребывания в очереди произвольным образом выбранного требования вычисляется по следующей формуле:

т. е. математическое ожидание продолжительности пребывания в очереди, ассоциированное с полным ансамблем требований, представляет собой сумму подансамблей требований, каждое из которых обладает приоритетом k (k -- 1, 2, . . ., r).

В некоторых задачах продолжительность процедуры обслуживания зависит от номера (или, как говорят, от уровня) приоритета. Тогда, обеспечивая требованиям с более высокими уровнями приоритета ускоренное обслуживание, мы тем самым сокращаем среднее время ожидания в очереди, вычисленное по суммарному выходному потоку обслуженных требований. В качестве иллюстрации этого утверждения вновь обратимся к случаю, когда л= 18, м= 20 (так что коэффициент загруженности обслуживающей системы при этом равняется 0,9, а среднее время ожидания в очереди 0,45). Перейдем теперь к схеме обслуживания с двумя уровнями приоритета и предположим, что л1= л2= 9, a м1= 30 и м2= 15, так что коэффициент загруженности ? r= 9/30+9/15 = 0,9 (т. е. остается таким же, как и в схеме обслуживания при отсутствии приоритетов). С помощью (35) и (36) легко убедиться, что в этом случае средняя продолжительность пребывания в очереди требования с приоритетом 1 равняется 1/14 = 0,0714, а требования с приоритетом 2 -- 10/14 = = 0,7142, т. е. меньше, чем в случае, когда м1= м2= м3 = 20. При этом средняя продолжительность пребывания в очереди, вычисленная на суммарном ансамбле обслуженных требований, равняется 0,3928, т. е. оказывается меньшей по сравнению с аналогичной операционной характеристикой системы без приоритетов, а также по сравнению со случаем, когда м1= м2 =20.

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

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

причем длительности обслуживания взаимонезависимы как для отдельно взятого прибора, так и по системе в целом. Уравнения в конечных разностях, аналогичные приведенным в предыдущем разделе уравнениям (7) и (8) для случая одноканалъной системы массового обслуживания и определяющие значения Рп в условиях установившегося режима, имеют следующий вид:

Решение системы уравнений (3) имеет вид

Установившийся режим функционирования системы массового обслуживания, характеризующийся соотношениями (4) и (5), возможен при условии л< мS (или < S.

В случае неограниченного количества обслуживающих приборов (например, в условиях самообслуживания) первая из формул (4) становится применимой для любого значения п. Следовательно, в этом случае Рп принимает пуассоновский вид, причем Е [п] = р.

Для такой модели используют символическое обозначение М/М/?. При S = ? пуассоновский характер Рп имеет место фактически при любом виде распределения длительностей обслуживания, т. е. и в случае M/G/?.

Формулы (4) применимы и в том случае, когда действует ограничение на суммарное количество требований М (?S), которое может находиться в системе. При этом п ? М, а Р0 определяется из условия

Отметим, кроме того, что формулы (4) остаются при этом справедливыми и в случае, когда л< мS

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

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

Введем в рассмотрение следующие величины:

В правой части (13) первое слагаемое представляет собой Е [Продолжительность ожидания в очереди], а второе -- Е [Продолжительность процедуры обслуживания].

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

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

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

6 Процессы рождения и гибели

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

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

Будем считать, что исследуемая система функционирует непрерывно, т. е. не имеет определенной стартовой точки, и в момент t характеризуется количеством находящихся в ней требований, которое мы обозначим через п (п = 0, 1, 2, . . .). Нам, разумеется, нужно договориться относительно выбора на оси времени начала отсчета t. Пусть в качестве начала отсчета времени выбрана точка t = 0; обозначим одновременно через i количество требований, находящихся в системе в момент 0. Пусть, по определению,

Поскольку процесс однороден во времени, величина Pin (h) при h > 0 определяет не только вероятность перехода на интервале (0, h), но и вероятность перехода на интервале (Т, Т+h) при произвольном значении Т, т. е. представляет собой вероятность того,что в момент Т+ h в системе будет находиться п требований при условии, что в момент Т в данной системе находилось i требований. Нами постулируется, что вероятности Pin (Т) удовлетворяют известным уравнениям Колмогорова -- Чэпмена для однородныхво времени марковских процессов.

Эти уравнения имеют следующий вид:

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

Процесс рождения и гибели является частным случаем дискретного марковского процесса, определяемого уравнением (2). Предположим, что в течение очень малого интервала времени (Т, Т+h), причем h > 0, количество поступивших в систему требований, так же как и количество требований, обслуженных системой, не превышает единицы (т. е. равняется либо нулю, либо единице). Для этого случая мы получим

Соотношение (6) является уже не приближенным, а точным, так как при h > 0 члены, опущенные нами в (5), в процессе указанного предельного перехода обращаются в нуль. Уравнение (6) позволяет также описать случай, когда п = 0; для этого достаточно положить

л-1= 0 и м0 = 0. Итак, (6) представляет собой систему уравнений для п =0О, 1, 2, . . . при начальном количестве требований в системе, равном i.

Термин опережающие уравнения отражает то обстоятельство, что при их выводе рассматривалось положительное приращение времени в пределах интервала (Т, T+h), где h > 0, а в качестве приближенных формул для вероятностей переходов были использованы соотношения (3) и (4). Можно вывести также ?запаздывающие уравнения?, рассматривая переходы на интервале (Т+ h, Т) при h > 0 [или, что то же самое, на интервале (Т, T+h) при h < 0] и используя аналоги соотношений (3) и (4) для Pim (h), построенные применительно к данному случаю. В получаемых таким путем дифференциальных уравнениях значение п в момент Т считается заданным, a i (т. е. количество требований, находящихся в системе в момент 0) варьируется, принимая значения i = 0, 1, 2, ....

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

что согласуется с приведенными до этого формулами (10) и (XI) для i = 0.

Примеры.

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

Пример 1. Предположим, что поток требований является пуассоновским с параметром л, причем будем считать, что каждое требование обслуживает себя в соответствии с экспоненциальным распределением длительностей обслуживания с параметром м. (Такую систему можно квалифицировать как систему с бесконечно большим количеством обслуживающих приборов и представить символически в виде М/М/?. Таким образом, лn = л,, а мn = мn.

Следовательно,

Пример 2. Пусть имеется один прибор, характеризующийся экспоненциальным распределением длительностей обслуживания, т. е. мn = м (п ?1). Однако допустим, что наблюдаются отказы требований присоединиться к очереди, причем наблюдается следующая закономерность: лn = л/(n+1). Нетрудно убедиться, что при сформулированных выше предположениях мы также придем к формулам (17) и (18).

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

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

Пусть в момент t число вышедших из строя агрегатов равняется п и, следовательно, число действующих агрегатов равняется М -- п. Тогда вероятность того, что в течение очень малого интервала [t, t + h] (h > 0) произойдет поломка одного из агрегатов, которые в момент t нормально функционировали, определяется следующей приближенной:

Простых формул для ожидаемого количества вышедших из строя агрегатов, к сожалению, не существует. Однако в каждом конкретном случае значение Е [га] легко вычисляется, если воспользоваться уже известными численными значениями Рп, найденными с помощью формулы (25).

Вопросы интерпретации модели.

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

7 О других методах массового обслуживания

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

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

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

Литература

1. Г.Вагнер «Основы исследования операций», Том 3, Глава 20

2. Таха, Хемди А «Введение в исследование операций», 7-ое издание