СМО с ожиданием (очередью)

В качестве показателей эффективности СМО с ожиданием, кроме уже известных показателей — абсолютной А и относительной Q пропускной способности, вероятности отказа Р , среднего числа занятых каналов k (для многоканальной системы) будем рассматривать также следующие: 1смст — среднее число заявок в системе; Т — среднее время пребывания заявки в системе; Lm — среднее число заявок в очереди (длина очереди)', Тт — среднее время пребывания заявки в очереди', Р.т< — вероятность того, что канал занят (степень загрузки канала).

Одноканальная система с неограниченной очередью. На практике часто встречаются одноканальные СМО с неограниченной очередью (например, одна будка с телефоном-автоматом). Рассмотрим задачу.

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

Система может находиться в одном из состояний S0, 5, 52,…, Sk, но числу заявок, поступивших в СМО: 50 — канал свободен; 5, — канал занят (обслуживает заявку), очереди нет; S2 — канал занят, одна заявка стоит в очереди; …, Sk - канал занят, (k — 1) заявок стоят в очереди и т. д.

Граф состояний СМО представлен на рис. 15.8.

Рис. 15.8.

Это процесс гибели и размножения, но с бесконечным числом состояний, в котором интенсивность потока заявок равна ?, а интенсивность потока обслуживании ?.

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

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

(15.32).

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

(15.33).

и с учетом соотношений.

найдем предельные вероятности других состояний.

(15.34).

Предельные вероятности образуют убы вающую геометрическую прогрессию со знаменателем р < 1, следовательно, вероятность  — наибольшая. Это означает, что если СМО справляется с потоком заявок (при р < 1), то наиболее вероятным будет отсутствие заявок в системе.

Среднее число заявок в системе определим по формуле математического ожидания, которая с учетом (15.34) примет вид.

(15.35).

(суммирование от 1 до ?, так как нулевой член Ор0 = 0).

Можно показать, что формула (15.35) преобразуется (при р < 1) к виду.

(15.36).

Найдем среднее число заявок в очереди . Очевидно, что.

(15.37).

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

Среднее число заявок под обслуживанием определим по формуле математического ожидания числа заявок под обслуживанием, принимающего значения 0 (если канал свободен) либо 1 (если канат занят):

т.е. среднее число заявок под обслуживанием равно вероятности того, что канал занят:

(15.38).

В силу (15.33).

(15.39).

Теперь по формуле (15.37) с учетом (15.36) и (15.39).

(15.40).

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

(15.41).

(15.42).

Формулы (15.41) и (15.42) называются формулами Литтла. Они следуют из того, что в предельном, стационарном режиме среднее число заявок, прибывающих в систему, равно среднему числу заявок, покидающих ее: оба потока заявок имеют одну и ту же интенсивность ?.

На основании формул (15.41) и (15.42) с учетом (15.36) и (15.40) среднее время пребывания заявки в системе определится по формуле.

(15.43).

а среднее время пребывания заявки в очереди -.

(15.44).

15.8. В порту имеется один причал для разгрузки судов. Интенсивность потока судов равна 0,4 (судов в сутки). Среднее время разгрузки одного судна составляет 2 суток. Предполагается, что очередь может быть неограниченной длины. Найти показатели эффективности работы причала, а также вероятность того, что ожидают разгрузки не более чем 2 судна.

Решение. Имеем? = ?/? = ???6 = 0,4−2 = 0,8. Так как р = 0,8 < 1, то очередь на разгрузку не может бесконечно возрастать, и предельные вероятности существуют. Найдем их.

Вероятность того, что причал свободен, по формуле (15.33) Ро =1−0,8 = 0,2, а вероятность того, что он занят, РШ1 =1−0,2 = 0,8. По формуле (15.34) вероятности того, что у причала находятся 1, 2, 3 судна (т.е. ожидают разгрузки 0, 1, 2 судна), равны t= 0,8(1 — 0,8) = 0,16; р2 = = 0,82 (1 — 0,8) = 0,128; p3= 0,83 (1 — 0,8) = 0,1024.

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

По формуле (15.40) среднее число судов, ожидающих разгрузки,

а среднее время ожидания разгрузки, но формуле (15.42).

По формуле (15.36) среднее число судов, находящихся у причала, ?сист = 0,8/(1 — 0,8) = 4 (судна) или проще по формуле (15.37) ?сист = 3,2 + 0,8 = 4 (судна), а среднее время пребывания судна у причала по формуле (15.41) Гснст = 4/0,4 = = 10 (суток).

Очевидно, что эффективность разгрузки судов невысокая. Для ее повышения необходимо уменьшить среднее время разгрузки судна Т1)й либо увеличить число причалов п. >

Многоканальная СМО с неограниченной очередью. Рассмотрим задачу. Имеется «-канальная СМО с неограниченной очередью. Поток заявок, поступающих в СМО, имеет интенсивность ?, а поток обслуживаний каждого канала — интенсивность ?. Необходимо найти предельные вероятности состояний СМО и показатели ее эффективности.

Система может находиться в одном из состояний

нумеруемых по числу заявок, находящихся в СМО: 50 — в системе нет заявок (все каналы свободны); 5, — занят один канал, остальные свободны; S2 - заняты два канала, остальные свободны; …, Sk — занято k каналов, остальные свободны;…, 5И — заняты все п каналов (очереди нет); Sn+l — заняты все п каналов, в очереди одна заявка;

5 — заняты все п каналов, г заявок стоит в очереди.

Граф состояний системы показан на рис. 15.9. Обратим внимание на то, что в отличие от предыдущей СМО, интенсивность потока обслуживаний (переводящего систему из одного состояния в другое справа налево) не остается постоянной, а по мере увеличения числа заявок в СМО от 0 до п увеличивается от величины? до «?, так как соответственно увеличивается число каналов обслуживания. При числе заявок в СМО большем, чем п, интенсивность потока обслуживаний сохраняется равной «?.

Рис. 15.9.

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

(15.45).

(15.46).

(15.47).

Вероятность того, что заявка окажется в очереди,.

(15.48).

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

(15.49).

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

(15.50).

среднее число заявок в системе.

(15.51).

коэффициент занятости канала обслуживания.

(15.52).

Среднее время пребывания заявки в очереди и среднее время пребывания заявки в системе, как и ранее, находятся по формулам Литтла (15.42) и (15.41).

Замечание. Для СМО с неограниченной очередью при р < 1 любая заявка, пришедшая в систему, будет обслужена, т. е. вероятность отказа Ротк = 0, относительная пропускная способность Q = 1, а абсолютная пропускная способность равна интенсивности входящего потока заявок, т. е. А = ?.

• 15.9. В универсаме к узлу расчета поступает поток покупателей с интенсивностью? = 81 человек в час. Средняя продолжительность_обслуживания контролером-кассиром одного покупателя /;оГ) = 2 мин. Определить:
  • а) минимальное количество контролеров-кассиров nmin, при котором очередь не будет расти до бесконечности, и соответствующие характеристики обслуживания при п = wmin;
  • б) оптимальное количество пот контролеров-кассиров, при котором относительная величина затрат С, связанная с издержками на содержание каналов обслуживания и с пребыванием в очереди покупателей, задаваемая, например, как , будет минимальна, и сравнить характеристики обслуживания при и
  • в) вероятность того, что в очереди Оудет не более трех покупателей.

Решение, а) По условию? = 81 (1/ч) = 81/60= 1,35(1/мин). По формуле (15.24)? = ?/? = ?/)6 = 1,35 • 2 = 2,7. Очередь не будет возрастать до бесконечности при условии р/п < 1, т. е. при п> р = 2,7. Таким образом, минимальное количество контролеров-кассиров nmin = 3.

Найдем характеристики обслуживания СМО при п = 3. Вероятность того, что в узле расчета отсутствуют покупатели, по формуле (15.45) р0 = (1 + 2,7 + 2,72/2! + 2,73/3! + + 2,74/3!(3 — 2,7)) 1 = 0,025, т. е. в среднем 2,5% времени контролеры-кассиры будут простаивать.

Вероятность того, что покупатель окажется в очереди, по формуле (15.48).

Среднее число покупателей, находящихся в очереди, по формуле (15.50)

Среднее время ожидания в очереди по формуле (15.42).

Среднее число покупателей в узле расчета по формуле (15.51).

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

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

Коэффициент (доля) занятых обслуживанием контролеров-кассиров по формуле (15.52).

Абсолютная пропускная способность узла расчета А = = 1,35 (1/мин), или 81 (1/ч), т. е. 81 покупатель в час.

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

б) Относительная величина затрат при п = 3.

Рассчитаем относительную величину затрат при других значениях п (табл. 15.2).

Таблица 15.2

Как видно из табл. 15.2, минимальные затраты получены при п = пот = 5 контролерах-кассирах.

Определим характеристики обслуживания узла расчета при n = nom = 5. Получим Роч = 0,091; 1оч = 0,198; Tm = 0,146 (мин); LCIICI = 2,90; Гсист = 2,15 (мин); к = 2,7; k3 = 0,54.

Как видим, при ? = 5 но сравнению с ? = 3 существенно уменьшились вероятность возникновения очереди Роч, длина очереди L и среднее время пребывания в очереди Тт и, соответственно, среднее число покупателей LcmT и среднее время нахождения в узле расчета Гсисг, а также доля занятых обслуживанием контролеров kt. Но среднее число занятых обслуживанием контролеров-кассиров к и абсолютная пропускная способность узла расчета А, естественно, не изменились.

в) Вероятность того, что в очереди будет не более 3 покупателей, определится как.

, где каждое слагаемое найдем по формулам (15.45)-(15.48). Получим при ? = 5.

Заметим, что в случае ? = 3 контролеров-кассиров та же вероятность существенно меньше: P (r< 3) = 0,464. >

• 15.10. Железнодорожная касса с двумя окошками продает билеты в два пункта А и В. Интенсивность потока пассажиров, желающих купить билеты, для обоих пунктов одинакова: ЛЛ=ЛВ = 0,45 (пассажиров в минуту). На обслуживание пассажиров кассир тратит в среднем 2 мин. Рассматриваются два варианта продажи билетов: первый — билеты продаются в одной кассе с двумя окошками одновременно в оба пункта /1 н В, второй — билеты продаются в двух специализированных кассах (по одному окошку в каждой), одна только в пункт Л, другая — только в пункт В. Необходимо:
  • а) сравнить два варианта продажи билетов по основным характеристикам обслуживания;
  • б) определить, как надо изменить среднее время обслуживания одного пассажира, чтобы по второму варианту продажи пассажиры затрачивали на приобретение билетов в среднем меньше времени, чем по первому варианту.

Решение, а) По первому варианту имеем двухканальную СМО, на которую поступает поток заявок интенсивностью? = 0,45 + 0,45 = 0,9; интенсивность потока обслуживании? = ½ = 0,5; р = ?/? = 1,8. Так как р/" = 1,8/2 = 0,9 < 1, то предельные вероятности существуют.

Вероятность простоя двух кассиров по формуле (15.45).

Среднее число пассажиров в очереди по формуле (15.50).

Среднее число пассажиров у кассы по формуле (15.51).

Среднее время на ожидание в очереди и покупку билетов равно соответственно (по формулам (15.42) и (15.41)): Тт = 7,67/0,9 = 8,52 (мин) и Гсист = 9,47/0,9 = 10,5 (мин).

По второму варианту имеем две одноканальные СМО (два специализированных окошка); на каждую поступает поток заявок с интенсивностью? = 0,45. По-прежнему? = = 0,5;? = ?/? = 0,9 < 1, предельные вероятности существуют. По формулам (15.40), (15.36), (15.42), (15.41) для каждой кассы.

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

Можно заметить, что среднее время на покупку билетов по второму варианту увеличилось более чем в 2 раза. Такое значительное увеличение связано с тем, что СМО работает на пределе своих возможностей (р = 0,9): достаточно_незначительно увеличить среднее время обслуживания ?, т. е. уменьшить ?, и р превзойдет единицу, т. е. очередь начнет неограниченно возрастать.

б) Выше было получено, что по первому варианту продажи билетов при среднем времени обслуживания одного пассажира 106 = 2 (мин) среднее время на покупку билетов составит Гсист = 10,5 (мин). По условию для второго варианта продажи ГС|1СТ2 <7'cltCTi или с учетом (15.36) и (15.41):

Полагая , получим , откуда найдем или (мин).

Итак, средние затраты времени на покупку билетов, но второму варианту продажи уменьшатся, если среднее время обслуживания одного пассажира уменьшится более чем на 0,17 мин, или более чем на 8,5%. >

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

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

Таблица 15.3

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

Примечания.

• 1. Формулы даны при условии, что р/п * 1 или р Фп (для одноканальной СМО — при р Ф I).
• 2. Среднее время пребывания заявки в системе (очереди) находится по формулам Литтла (15.43), (15.44).

Среднее время пребывания заявки в очереди и в системе, как и ранее, определяем по формулам Литтла (15.44) и (15.43).

О 15Л1. По условию задачи 15.8 найти показатели эффективности работы причала. Известно, что приходящее судно покидает причал (без разгрузки), если в очереди на разгрузку стоит более 3 судов.

Решение. По условию т = 3. Используем формулы, приведенные во второй графе табл. 15.3.

Вероятность того, что причал свободен:

Вероятность того, что приходящее судно покинет причал без разгрузки:

Относительная пропускная способность причала:

Абсолютная пропускная способность причала А = = 0,4 • 0,878 = 0,351, т. е. в среднем в сутки разгружается 0,35 судна.

Среднее число судов, ожидающих разгрузку:

а среднее время ожидания разгрузки по формуле (15.42):

Среднее число судов, находящихся у причала:

а среднее время пребывания судна у причала по формуле (15.41):

(суток). >

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

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

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

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

Понятие о статистическом моделировании СМО (метод Монте-Карло)

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

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

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

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

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

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