Одноканальная система с неограниченной очередью. На практике часто встречаются одноканальные СМО с неограниченной очередью (например, телефон-автомат с одной будкой). Рассмотрим задачу.
Имеется одноканальная СМО с очередью, на которую не наложены никакие ограничения (ни по длине очереди, ни по времени ожидания). Поток заявок, поступающих в СМО, имеет интенсивность λ, а поток обслуживании - интенсивность μ. Необходимо найти предельные вероятности состояний и показатели эффективности СМО.
Система может находиться в одном из состояний S 0 , S 1 , S 2 , …, S k , по числу заявок, находящихся в СМО: S 0 - канал свободен; S 1 - канал занят (обслуживает заявку), очереди нет, S 2 - канал занят, одна заявка стоит в очереди; ... S k - канал занят, (k-1) заявок стоят в очереди и т.д.
Граф состояний СМО представлен на рис. 8.
Рис. 8
Это процесс гибели и размножения, но с бесконечным числом состояний, в котором интенсивность потока заявок равна λ, а интенсивность потока обслуживании μ.
Прежде чем записать формулы предельных вероятностей, необходимо быть уверенным в их существовании, ведь в случае, когда время t→∞, очередь может неограниченно возрастать. Доказано, что если ρ<1, т.е. среднее число приходящих заявок меньше среднего числа обслуженных заявок (в единицу времени), то предельные вероятности существуют. Если ρ≥1, очередь растет до бесконечности.
Для определения предельных вероятностей состояний воспользуемся формулами (16), (17) для процесса гибели и размножении (здесь мы допускаем известную нестрогость, так как ранее эти формулы были получены для случая конечного числа состояний системы). Получим (32)
Так как предельные вероятности существуют лишь при ρ < 1, то геометрический ряд со знаменателем
ρ < 1, записанный в скобках в формуле (32), сходится к сумме, равной . Поэтому
(33)
и с учетом соотношений (17)
найдем предельные вероятности других состояний
(34)
Предельные вероятности p 0 , p 1 , p 2 , …, p k ,… образуют убывающую геометрическую профессию со знаменателем р < 1, следовательно, вероятность р 0 - наибольшая. Это означает, что если СМО справляется с потоком заявок (при ρ < 1), то наиболее вероятным будет отсутствие заявок в системе.
Среднее число заявок в системе L сист. определим по формуле математического ожидания, которая с учетом (34) примет вид
(35)
(суммирование от 1 до ∞, так как нулевой член 0p 0 =0).
Можно показать, что формула (35) преобразуется (при ρ < 1) к виду
(36)
Найдем среднее число заявок в очереди L оч. Очевидно, что
(37)
где L об. - среднее число заявок, находящихся под обслуживанием.
Среднее число заявок под обслуживанием определим по формуле математического ожидания числа заявок под обслуживанием, принимающего значения 0 (если канал свободен) либо 1 (если канал занят):
т.е. среднее число заявок под обслуживанием равно вероятности того, что канал занят:
(38)
В силу (33)
(39)
Теперь по формуле (37) с учетом (36) и (39)
(40)
Доказано, что при любом характере потока заявок, при любом распределении времени обслуживания, при любой дисциплине обслуживания среднее время пребывания заявки в системе (очереди) равна среднему числу заявок в системе (в очереди), деленному на интенсивность потока заявок,
т.е.
(41)
(42)
Формулы (41) и (42) называются формулами Литтла.
Они вытекают из того, что в предельном, стационарном режиме среднее число заявок, прибывающих в систему, равно среднему числу заявок, покидающих
ее:
оба потока заявок имеют одну и ту же интенсивность λ.
На основании формул (41) и (42) с учетом (36) и (40) среднее время пребывания заявки в системе определится по формуле:
(43)
а среднее время пребывания заявки в очереди
(44)
Многоканальная СМО с неограниченной очередью
. Рассмотрим задачу. Имеется n-канальная СМО с неограниченной очередью. Поток заявок, поступающих в СМО, имеет интенсивность λ, а поток обслуживании - интенсивность μ.
Необходимо найти предельные вероятности состояний СМО и показатели ее эффективности.
Система может находиться в одном из состояний S 0 , S 1 , S 2 ,…, S k ,…, S n ,…, - нумеруемых по числу заявок, находящихся в СМО: S 0 - в системе нет заявок (все каналы свободны); S 1 - занят один канал, остальные свободны; S 2 - заняты два канала, остальные свободны;..., S k - занято k каналов, остальные свободны;..., S n - заняты все n каналов (очереди нет); S n+1 - заняты все n каналов, в очереди одна заявка;..., S n+r - заняты все n каналов, r заявок стоит в очереди,....
Граф состояний системы показан на рис. 9. Обратим внимание на то, что в отличие от предыдущей СМО, интенсивность потока обслуживаний (переводящего систему из одного состояния в другое справа налево) не остается постоянной, а по мере увеличения числа заявок в СМО от 0 до n увеличивается от величины m до nm, так как соответственно увеличивается число каналов обслуживания.
При числе заявок в СМО большем, чем n, интенсивность потока обслуживании сохраняется равной nm.
Рис. 9
Можно показать, что при r/n < 1 предельные вероятности существуют. Если r/n > 1, очередь растет до бесконечности. Используя формулы (16) и (17) для процесса гибели и размножения, можно получить следующие формулы для предельных вероятностей состояний n-канальной СМО с неограниченной очередью
(45)
(46)
(47)
Вероятность того, что заявка окажется в очереди,
(48)
Для n-канальной СМО с неограниченной очередью, используя прежние приемы, можно найти:
среднее число занятых каналов
(49)
среднее число заявок в очереди
(50)
среднее число заявок в системе
(51)
Среднее время пребывания заявки в очереди и среднее время пребывания заявки в системе, как и ранее, находятся по формулам Литтла (42) и (41).
Замечание.
Для СМО с неограниченной очередью при r < 1 любая заявка, пришедшая в систему, будет обслужена,
т.е. вероятность отказа P отк = 0, относительная пропускная способность
Q =
1, а абсолютная пропускная способность равна интенсивности входящего потока заявок, т.е. А =
l.
СМО с ограниченной очередью
СМО с ограниченной очередью. СМО с ограниченной очередью отличаются от рассмотренных выше задач лишь тем, что число заявок в очереди ограничено (не может превосходить некоторого заданного т). Если новая заявка поступает в момент, когда все места в очереди заняты, она покидает СМО необслуженной, т.е. получает отказ.Очевидно: для вычисления предельных вероятностей состояний и показателей эффективности таких СМО может быть использован тот же подход, что и выше, с той разницей, что суммировать надо не бесконечную прогрессию (как, например, мы делали при выводе формулы (33)), а конечную.
Среднее время пребывания заявки в очереди и в системе, как и ранее, определяем по формулам Литтла (44) и (43).
СМО с ограниченным временем ожидания. На практике часто встречаются СМО с так называемыми "нетерпеливыми" заявками. Такие заявки могут уйти из очереди, если время ожидания превышает некоторую величину. В частности, такого рода заявки возникают в различных технологических системах, в которых задержка с началом обслуживания может привести к потере качества продукции, в системах оперативного управления, когда срочные сообщения теряют ценность (или даже смысл), если они не поступают на обслуживание в течение определенного времени.
В простейших математических моделях таких систем предполагается, что заявка может находиться в очереди случайное время, распределенное по показательному закону с некоторым параметром υ, т.е. можно условно считать, что каждая заявка, стоящая в очереди на обслуживание, может покинуть систему с интенсивностью υ.
Соответствующие показатели эффективности СМО с ограниченным временем получаются на базе результатов, полученных для процесса гибели и размножения.
В заключение отметим, что на практике часто встречаются замкнутые системы обслуживания , у которых входящий поток заявок существенным образом зависит от состояния самой СМО. В качестве примера можно привести ситуацию, когда на ремонтную базу поступают с мест эксплуатации некоторые машины: понятно, что чем больше машин находится в состоянии ремонта, тем меньше их продолжает эксплуатироваться и тем меньше интенсивность потока вновь поступающих на ремонт машин. Для замкнутых СМО характерным является ограниченное число источников заявок, причем каждый источник "блокируется" на время обслуживания его заявки (т.е. он не выдает новых заявок). В подобных системах при конечном числе состояний СМО предельные вероятности будут существовать при любых значениях интенсивностей потоков заявок и обслуживании. Они могут быть вычислены, если вновь обратиться к процессу гибели и размножения.
Рассмотрим n - канальную систему массового обслуживания с ожиданием.
Интенсивность потока обслуживания равна μ. Длительность обслуживания – случайная величина, подчиненная показательному закону распределения. Поток обслуживаний является простейшим пуассоновским потоком событий.
Размер очереди допускает нахождение в ней m заявок.
Для нахождения предельных вероятностей можно использовать следующие выражения.
(0‑1)
где.
Вероятность отказа в обслуживании заявки (отказ произойдет в случае, если все каналы заняты и в очереди находятся m заявок):
(0‑2)
Относительная пропускная способность .
(0‑3)
Абсолютная пропускная способность .
(0‑4)
Среднее число занятых каналов.
Для СМО с очередью среднее число занятых каналов не совпадает (в отличие от СМО с отказами) со средним числом заявок в системе. Отличие равно числу заявок, ожидающих в очереди.
Обозначим среднее число занятых каналов. Каждый занятый канал обслуживает в среднем μ заявок в единицу времени, а СМО в целом – А заявок в единицу времени. Разделив А на μ получим
(0‑5)
Среднее число находящихся в очереди заявок.
Для нахождения среднего числа ожидающих в очереди заявок в случае, если χ≠1, можно использовать выражение:
(0‑6)
(0‑7)
где = .
Среднее число находящихся в системе заявок.
(0‑8)
Среднее время ожидания заявки в очереди .
Среднее время ожидания заявки в очереди можно найти из выражения (χ≠1).
(0‑9)
Среднее время пребывания заявки в системе.
Так же как и в случае с одноканальной СМО имеем:
(0‑10)
Содержание работы .
Подготовка инструментария эксперимента .
Выполняется в соответствии с общими правилами.
Расчет на аналитической модели .
1. В приложение Microsoft Excel подготовьте таблицу следующего вида.
|
Параметры |
Аналитическая
|
Имитационная |
|||||||||||||||
|
n |
m |
T a |
Ts |
ρ |
χ |
P0 |
P1 |
p2 |
Pотк |
W |
nож |
q |
A |
Pотк |
W |
q |
A |
2. В столбцах для параметров СМО таблицы запишите свои исходные данные, которые определяются по правилу:
n =1,2,3
m=1,3,5
Для каждой комбинации { n ,m} необходимо найти теоретические и экспериментальные значения показателей СМО для таких пар значений:
= <порядковый номер в списке группы>
3. В столбцы с показателями аналитической модели впишите соответствующие формулы.
Эксперимент на имитационной модели .
1. Установите режим запусков с экспоненциально распределенным временем обслуживания, задав значение соответствующего параметра равным 1.
2. Для каждой комбинации n, m, и осуществите запуск модели.
Результаты запусков внесите в таблицу.
3. Внесите в соответствующие столбцы таблицы формулы для расчета среднего значения показателя Pотк, q и А.
Анализ результатов .
1. Проанализируйте результаты, полученные теоретическим и экспериментальным способами, сравнив результаты между собой.
2. Для одной из комбинаций {n,m} постройте на одной диаграмме графики зависимости Pотк от на теоретически и экспериментально полученных данных.
Оптимизация параметров СМО .
Решите задачу оптимизации размера числа мест в очереди m для двух приборов со средним временем обслуживания = с точки зрения получения максимальной прибыли. В качестве условий задачи возьмите:
- доход от обслуживания одной заявки равным 80у.е./час,
- стоимость содержания одного прибора - 1у.е./час,
- стоимость содержания одного места в очереди – 0.2у.е./час.
1. Для расчетов целесообразно создать таблицу:
Первый столбец заполняется значениями числа приборов n =1.
Второй столбец заполняется значениями чисел натурального ряда (1,2,3…).
Все клетки третьего и четвертого столбцов заполняются значениями.
В клетки столбцов с пятого по четырнадцатый переносятся формулы для столбцов таблицы раздела 0.
В столбцы с исходными данными разделов Доход, Расход, Прибыль внесите значения (см. выше).
В столбцах с вычисляемыми значениями разделов Доход, Расход, Прибыль запишите расчетные формулы:
- число заявок в единицу времени
N r =A
- суммарный доход в единицу времени
I S = I r *N r
- суммарный расход в единицу времени
E S =E s *n + E q *m
- прибыль в единицу времени
P = I S - E S
где
I r - доход от одной заявки ,
E s - расход на один прибор ,
E q - расход на одно место в очереди
2. Заполните строки таблицы для n=2 и n=3.
Найдите m опт для n =1 ,2,3.
3. Постройте на одной диаграмме графики зависимости C(m) для n=1,2,3.
Отчет по работе :
Отчет по работе должен включать:
- исходные данные,
- результаты расчетов и экспериментов с программной моделью,
Графики для P отк ,
- таблицу с данными для нахождения наилучшего m и значение m опт,
- графики зависимости прибыли в единицу времени от m для n=1,2,3.
Контрольные вопросы :
1) Дайте краткое описание многоканальной модели СМО с ограниченной очередью.
2) Какими показателями характеризуется функционирование многоканальной СМО с ограниченной очередью?
3) Как рассчитываются предельные вероятности многоканальной СМО с ограниченной очередью?
4) Как найти вероятность отказа обслуживания заявки?
5) Как найти относительную пропускную способность?
6) Чему равна абсолютная пропускная способность?
7) Как подсчитывается среднее число заявок в системе?
8) Приведите примеры многоканальной СМО с ограниченной очередью.
Задачи .
1) На автозаправочной станции установлены 3 колонки и площадка на 3 автомобиля для ожидания заправки. В среднем на станцию прибывает одна машина каждые 4 минуты. Среднее время обслуживания одной машины - 2,8 мин. Определить характеристики работы автозаправочной станции.
2) На станцию технического осмотра автомобилей, имеющего 3 смотровых поста, в среднем поступает 1 автомобиль за 0,4 часа. Стоянка во дворе вмещает 3 машины. Среднее время работы одного поста - 0,5 часа. Определить характеристики работы СТО.
3) В магазин осуществляется завоз товаров автомобилями. В течение дня прибывают в среднем 6 машин. Подсобные помещения для подготовки товаров к продаже позволяют обрабатывать и хранить товар, привезенный двумя машинами. В магазине работают посменно три фасовщика товаров, каждый из которых в среднем может обрабатывать товар одной машины в течение 5 часов. Продолжительность рабочего дня фасовщиков составляет 12 часов. Определить характеристики работы магазина, а также, какова должна быть емкость подсобных помещений, чтобы вероятность полной обработки товаров была больше 0,96.
4) В магазине работают три кассы. Среднее время обслуживания одного покупателя - 3 мин. Интенсивность потока покупателей - 7 человек в минуту. Число покупателей, стоящих в очереди к кассе, не может превышать 5 человек. Покупатель, пришедший в магазин, в котором в каждой очереди в кассу 5 человек, не ждет, а уходит из магазина. Определить характеристики работы магазина.
5) Оптовый склад производит отпуск товаров клиентам. Погрузку автомашины осуществляют три бригады грузчиков, каждая из которых состоит из 4 человек. Склад одновременно вмещает 5 автомашин и, если в это время прибывает новая автомашина, то она не обслуживается. Интенсивность входящего потока составляет 5 автомашин в час. Интенсивность по грузки составляет 2 автомашины в час. Дайте оценку работы склада и вариант его реорганизации.
6) Таможня располагает тремя терминалами. Интенсивность потока автомашин, перевозящих грузы и подлежащих прохождению таможенного контроля, составляет 30 шт. в сутки. Среднее время таможенной обработки на терминале одной автомашины составляет 3 часа. Если в очереди на прохождение таможенного контроля стоят 5 автомашин, то приезжающие автомашины уезжают на другую таможню. Найти показатели эффективности работы таможни.
7) На строительную площадку в среднем через 40 мин прибывают автомашины со строительным материалом. Среднее время разгрузки одной автомашины составляет 1,8 часа. В разгрузке принимают участие две бригады грузчиков. На территории строительной площадки может находиться в очереди на разгрузку не более 5 автомашин. Определить показатели эффективности работы строительной площадки.
8) На мойку, имеющую три рабочих места, в среднем в час приезжает 12 автомашин. Если в очереди уже находится 6 автомашин, вновь приезжающие автомобили не встают в очередь, а покидают мойку. Среднее время мойки автомашины составляет 20 мин, средняя стоимость услуг мойки - 150 руб. Определить показатели эффективности работы мойки и среднюю величину потери выручки в течение рабочего дня (с 9 до 19 часов).
9) Интенсивность потока автомашин, перевозящих грузы и подлежащих прохождению таможенного контроля, составляет 50 шт. в сутки. Среднее время таможенной обработки на терминале одной автомашины составляет 2,8 часа. Максимальная очередь на прохождение таможенного контроля должна быть не более 8 автомашин. Определить, какое количество терминалов надо открыть на таможне, чтобы вероятность простоя автомашин была минимальна.
В систему поступает пуассоновский поток требований интенсивностью λ, поток обслуживания имеет интенсивность μ, максимальное число мест в очереди – т. Если заявка поступает в систему, когда все места в очереди заняты, она покидает систему необслуженной.
Финальные вероятности состояний такой системы всегда существуют, так как число состояний конечно:
S 0 – система свободна и находится в состоянии простоя;
S 1 – обслуживается одна заявка, канал занят, очереди нет;
S 2 – одна заявка обслуживается, одна в очереди;
S m +1 - одна заявка обслуживается,т в очереди.
Граф состояний такой системы показан на рисунке номер 5:
S 0 S 1 S 2 S m+1
μ μ μ ………. μ μ
Рисунок 5: Одноканальная СМО с ограниченной очередью.
В формуле для р 0 найдем сумму конечного числа членов геометрической прогрессии:
(52)
С учетом формулы для ρ получим выражение:
В скобках находится (m+2) элементов геометрической прогрессии с первым членом 1 и знаменателем ρ. По формуле суммы (m+2) членов прогрессии:
(54)
(55)
Формулы для вероятностей предельных состояний будут иметь вид:
Вероятность отказа в обслуживании заявки определим как вероятность того, что при поступлении заявки в систему ее канал будет занят и все места в очереди также заняты:
(57)
Отсюда вероятность обслуживания (а также и относительная пропускная способность ) равны вероятности противоположного события:
Абсолютная пропускная способность – число заявок, обслуженных системой в единицу времени:
(59)
Среднее число заявок под обслуживанием:
(60)
(61)
Среднее число заявок в системе:
(62)
Одноканальную СМО с ограниченной очередью можно рассмотреть в Mathcad.
Пример :
На стоянке обслуживается 3 машины с интенсивностью потока 0,5 и средним временем обслуживания 2,5 минуты. Определить все показатели системы.
6 Многоканальная смо с неограниченной очередью
Пусть дана система S, имеющаяп каналов обслуживания, на которые поступает простейший поток требований интенсивностью λ. Пусть поток обслуживания также простейший и имеет интенсивность μ. Очередь на обслуживание не ограничена.
По числу заявок, находящихся в системе, обозначим состояния системы: S 0 ,S 1 ,S 2 ,…,S k ,… S n , гдеS k – состояние системы, когда в ней находитсяkзаявок (максимальное число заявок под обслуживанием -n). Граф состояний такой системы изображается в виде схемы на рисунке номер 6:
λ λ λ λ λ λ λ
……. …….
S 0 S 1 S 2 S m+1 S n
μ 2μ 3μ ………. kμ (k+1)μ …… nμ nμ
Рисунок 6: Многоканальная СМО с неограниченной очередью.
Интенсивность потока обслуживаний меняется в зависимости от состояния системы: kμ при переходе из состоянияS k в состояниеS k -1 так как может освободиться любой изk каналов; после того, как все каналы заняты обслуживанием, интенсивность потока обслуживаний остается равнойпμ, при поступлении в систему следующих заявок.
Для нахождения финальных вероятностей состояний получим формулы аналогично тому, как это было сделано для одноканальной системы.
(63)
Отсюда формулы для финальных вероятностей выражаются через
Для нахождения р 0 получим уравнение:
Для слагаемых в скобках, начиная с
(n+ 2)-го, можно применить
формулу нахождения суммы бесконечно
убывающей геометрической прогрессии
с первым членом
и знаменателем ρ/n:
(66)
Окончательно получим формулу Эрланга для нахождения вероятности простоя системы:
(67)
Приведем формулы для расчета основных яоказателей эффективности работы системы.
Система будет справляться с потоком заявок, если
выполнено условие
,
(68)
которое означает, что число заявок, поступивших в систему за единицу времени, не превосходит числа заявок, обслуженных системой за это же время. При этом вероятность отказа в обслуживании равна нулю.
Отсюда вероятность обслуживания (а также иотносительная пропускная способность системы) равны вероятности противоположного события, то есть единице:
(69)
Абсолютная пропускная способность - число заявок, обслуженныхсистемой в единицу времени:
(70)
Если система справляется с потоком заявок, то в стационарном режиме интенсивность выходящего потока равна интенсивности потока поступающих в систему заявок, так как обслуживаются все заявки:
ν=λ . (71)
Так как каждый канал обслуживает μ заявок в единицу времени, то среднее число занятых каналов можно вычислить:
(72)
Среднее время обслуживания каналом одной заявки;
.
(73)
Вероятность того, что при поступлении в систему заявка окажется в очереди, равна вероятности того, что в системе находится более чем п заявок:
(74)
Число заявок, находящихся под обслуживанием, равно числу занятых каналов:
(75)
Среднее число заявок в очереди:
(76)
Тогда среднее число заявок в системе:
(77)
Среднее время пребывания заявки в системе (в очереди):
(78)
(79)
Многоканальную СМО с неограниченной очередью можно рассмотреть в системе Mathcad.
Пример 1 :
Салон-парикмахерская имеет 5 мастеров. В час пик интенсивность потока клиентов равна 6 человек. В час. Обслуживание одного клиента длится в среднем 40 минут. Определить среднюю длину очереди, считая ее неограниченной.
Фрагмент решения задачи в Mathcad.
Пример 2:
В железнодорожной кассе имеются 2 окна. Время на обслуживания одного пассажира 0,5 минут. Пассажиры подходят к кассе по 3 человека. Определить все характеристики системы.
Фрагмент решения задачи в Mathcad.
Продолжение решения задачи в Mathcad.
Имеется n -канальная СМО с неограниченной очередью. Поток заявок, поступающих в СМО, имеет интенсивность , а поток обслуживаний – интенсивность . Необходимо найти предельные вероятности состояний СМО и показатели ее эффективности.
Система может находиться в одном из состояний s 0 , s 1 , s 2 ,…,s k ,…,s n , нумеруемых по числу заявок, находящихся в СМО: s 0 – в системе нет заявок (все каналы свободны); s 1 – занят один канал, остальные свободны; s 2 – заняты два канала, остальные свободны;…; s k – занято k каналов, остальные свободны;…; s n – заняты все n каналов (очереди нет); s n +1 – заняты все n каналов, в очереди одни заявка;…; s n + r – заняты все n каналов, r заявок в очереди.
Граф состояний приведен на рис. 7
|
В отличие от одноканальной СМО интенсивность потока обслуживаний не остается постоянной, а по мере увеличения числа заявок в СМО от 0 до n увеличивается от величины до , т.к. соответственно увеличивается число каналов обслуживания. При числе заявок больше, чем n , интенсивность потока обслуживаний сохраняется равной . Если в системе n каналов обслуживания с интенсивностью , интенсивность входящего потока равна , то, чтобы очередь не стала бесконечно большой, необходимо выполнение условия стационарности
Это условие означает, что суммарная скорость обслуживания всех каналов системы должна превосходить скорость поступления требований , иначе система не справится с обслуживанием потока.
Данное условие характерно только для систем с очередью в отличие от систем с отказом, т.к. все поступившие требования должны получить обслуживание.
Используя формулы (11)для процесса гибели и размножения, можно получить формулы для предельных вероятностей состояний n -канальной СМО с неограниченной очередью
(31)
,…, ,…, (32)
,…, 
Вероятность того, что в системе заняты обслуживанием все n каналы, определяется по формуле
(33)
Для n -канальной СМО с неограниченной очередью, используя прежние приемы, можно найти:
Среднее число занятых каналов
Среднее число заявок в очереди
,
Среднее число заявок в системе
,
Среднее время обслуживания заявки
Среднее время ожидания обслуживания
Полученные выше формулы значительно упрощаются в случае одно – или двухканальной системы
При n=1
Т.к. 
;
При n=2
Т.к. 
,
Пример 7. К двум продавцам поступает на обслуживание поток покупателей с интенсивностью 220 человек в час. Каждый из продавцов затрачивает на обслуживание покупателя в среднем 30 секунд. Определите среднюю длину очереди и показатели занятости продавцов.
Решение.
, 
,
– интенсивность загрузки
– среднее число занятых обслуживанием каналов
– средняя длина очереди
– доля времени простоя продавцов
– доля времени занятости одного из двух продавцов
– доля времени занятости двух продавцов
Пример 8.
В универсаме к узлу расчета поступает поток покупателей с интенсивностью 
. Средняя продолжительность обслуживания контролером-кассиром одного покупателя . Определить минимальное количество контролеров-кассиров n мин
, при котором очередь не будет расти до бесконечности и соответствующие характеристики обслуживания при n=n мин
.
Решение.
По условию 
, 
. Очередь не будет возрастать до бесконечности при условии , т.е. при . Таким образом, минимальное количество контролеров-кассиров n min =3
.Р отк =0
, относительная пропускная способность Q=1
, а абсолютная пропускная способность равна интенсивности входящего потока заявок, т.е. .
Для нашей задачи абсолютная пропускная способность узла расчета A=1,35 1/мин или 81 1/ч , т.е. 81 покупатель в час.
Анализ характеристик обслуживания свидетельствует о значительной перегрузке узла расчета при наличии трех контролеров-кассиров.
Более сложные задачи теории массового обслуживания
В этом параграфе мы кратко рассмотрим некоторые вопросы, относящиеся к немарковским СМО. До сих пор все формулы нами выводились или, по крайней мере, могли быть выведены читателем, вооруженным схемой гибели и размножения, формулой Литтла и умением дифференцировать. То, что будет рассказано в данном параграфе, читателю придется принять на веру.
До сих пор мы занимались только простейшими СМО, для которых все потоки событий, переводящий их из состояния в состояние, были простейшими. А как быть, если они не простейшие? Насколько реально это допущение? Насколько значительны ошибки, к которым оно приводит, когда оно нарушается? На все эти вопросы мы попытаемся ответить здесь.
Как это ни грустно, но надо признаться, что в области немарковской теории массового обслуживания похвастать нам особенно нечем. Для немарковских СМО существуют только отдельные, считанные результаты, позволяющие выразить в явном, аналитическом виде характеристики СМО через заданные условия задачи - число каналов, характер потока заявок, вид распределения времени обслуживания. Приведем некоторые из этих результатов.
1. n -канальная СМО с отказами, с простейшим потоком заявок и произвольным распределением времени обслуживания. В предыдущем параграфе мы вывели формулы Эрланга (20.4), (20.5) для финальных вероятностей состояний СМО с отказами. Сравнительно недавно (в 1959 г.) Б. А. Севастьянов доказал, что эти формулы справедливы не только при показательном, но и при произвольном распределении времени обслуживания.
^ 2. Одноканальная СМО с неограниченной очередью, простейшим потоком заявок и произвольным распределением времени обслуживания. Если на одноканальную СМО с неограниченной очередью поступает простейший поток заявок с интенсивностью λ, а время обслуживания имеет произвольное распределение с математическим ожиданием t об = 1/μ. и коэффициентом вариации v μ , то среднее число заявок в очереди равно
а среднее число заявок в системе
(21.2)
Где, как и ранее, ρ = λ/μ., a v μ - отношение среднего квадратического отклонения времени обслуживания к его математическому ожиданию. Формулы (21.1), (21.2) носят название формул Полячека - Хинчина.
Деля L оч, и L сист на λ, получим, согласно формуле Литтла, среднее время пребывания заявки в очереди и среднее время пребывания в системе:
(21.3)
(21.4)
Заметим, что в частном случае, когда время обслуживания - показательное, v μ = 1 и формулы (21.1), (21.2) превращаются в уже знакомые нам формулы (20.16), (20.20) для простейшей одноканальной СМО. Возьмем другой частный случай - когда время обслуживания вообще не случайно и v μ = 0. Тогда среднее число заявок в очереди уменьшается вдвое по сравнению с простейшим случаем. Это и естественно: если обслуживание заявки протекает более организованно, «регулярно», то СМО работает лучше, чем при плохо организованном, беспорядочном обслуживании.
^ 3. Одноканальная СМО с произвольным потоком заявок и произвольным распределением времени обслуживания. Рассматривается одноканальная СМО с неограниченной очередью, на которую поступает произвольный рекуррентный поток заявок с интенсивностью λ и коэффициентом вариации v λ интервалов между заявками, заключенным между нулем и единицей: 0 < v λ < 1. Время обслуживания Т об также имеет произвольное распределение со средним значением t об = 1/μ и коэффициентом вариации v μ , тоже заключенным между нулем и единицей. Для этого случая точных аналитических формул получить не удается;
можно только приближенно оценить среднюю длину очереди, ограничить ее сверху и снизу.
Доказано, что в этом случае
Если входящий поток - простейший, то обе оценки - верхняя и нижняя - совпадают, и получается формула Полячека - Хинчина (21.1). Для грубо приближенной оценки средней длины очереди М. А. Файнбергом (см. ) получена очень простая формула:
(21.6)
Среднее число заявок в системе получается из L оч простым прибавлением ρ - среднего числа обслуживаемых заявок:
L сист = L оч + ρ. (21.7)
Что касается средних времен пребывания заявки в очереди и в системе, то они вычисляются через L оч и L сист по формуле Литтла делением на λ.
Таким образом, характеристики одноканальных СМО с неограниченной очередью могут быть (если не точно, то приближенно) найдены и в случаях, когда потоки заявок и обслуживании не являются простейшими.
Возникает естественный вопрос: а как же обстоит дело с многоканальными немарковскими СМО? Со всей откровенностью ответим: плохо. Точных аналитических методов для таких систем не существует. Единственное, что мы всегда можем найти, это среднее число занятых каналов k = ρ. Что касается L оч, L сист, W оч, W сист, то для них таких общих формул написать не удается.
Правда, если каналов действительно много (4-5 или больше), то непоказательное время обслуживания не страшно: был бы входной поток простейшим. Действительно, общий поток «освобождений» каналов складывается из потоков освобождений отдельных каналов, а в результате такого наложения («суперпозиции») получается, как мы знаем, поток, близкий к простейшему. Так что в этом случае замена непоказательного распределения времени обслуживания показательным приводит к сравнительно малым ошибкам. К счастью, входной поток заявок вомногих задачах практики близок к простейшему.
Хуже обстоит дело, когда входной поток заведомо не простейший. Ну, в этом случае приходится пускаться на хитрости. Например, подобрать две одноканальные СМО, из которых одна по своей эффективности заведомо «лучше» данной многоканальной, а другая - заведомо «хуже» (очередь больше, время ожидания больше). А для одноканальной СМО мы худо-бедно уже умеем находить характеристики в любом случае.
Как же подобрать такие одноканальные СМО - «лучшую» и «худшую»? Это можно сделать по-разному. Оказывается, заведомо худший вариант можно получить, если расчленить данную n
-канальную СМО на п
одноканальных, а общий поступающий на них простейший поток распределять между этими одноканальными СМО в порядке очереди: первую заявку - в первую СМО, вторую - во вторую и т. д. Мы знаем, что при этом на каждую СМО будет поступать поток Эрланга n
-го порядка, с коэффициентом вариации, равным 1/ . Что касается коэффициента вариации времени обслуживания, то он остается прежним. Для такой одноканальной СМО мы уже умеем вычислять время пребывания заявки в системе W
сист; оно будет заведомо больше, чем для исходной n
-канальной СМО. Зная это время, можно дать «пессимистическую» оценку и для среднего числа заявок в очереди, пользуясь формулой Литтла и умножая среднее время на интенсивность λ общего потока заявок. «Оптимистическую» оценку можно получить, заменяя n
-канальную СМО одной одноканальной, но с интенсивностью потока обслуживании в n
раз большей, чем у данной, равной nμ
. Естественно, при этом параметр ρ тоже должен быть, изменен, уменьшен в n
раз. Для такой СМО время пребывания заявки в системе W
сист уменьшается за счет того, что обслуживание продолжается в n
раз меньше времени. Пользуясь измененным значением , коэффициентом вариации входящего потока v
λ и времени обслуживания v
μ ,
мы можем приближенно вычислить среднее число заявок в системе . Вычитая из него первоначальное (не измененное) значение ρ, мы получим среднее число заявок в очереди 
. Обе характеристики будут меньше, чем для исходной n
-канальной СМО (будут представлять собой «оптимистические» оценки). От них, деля на λ,
можно перейти к «оптимистическим» оценкам для времени пребывания в СМО и в очереди.