Одноканальная смо с ограниченной длиной очереди. Системы массового обслуживания с неограниченной очередью Граф состояний многоканальной смо с ограниченной очередью

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

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

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

Среднее время пребывания заявки в системе,

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

Среднее время пребывания заявки в очереди,

Вероятность того, что канал занят (степень загрузки канала).

Что касается абсолютной пропускной способности А и относительной Q, то вычислять их нет надобности: в силу того, что очередь неограниченна, каждая заявка рано или поздно будет обслужена, поэтому по той же причина

Решение. Состояния системы, как и раньше, будем нумеровать по числу заявок, находящихся в СМО:

Канал свободен,

Канал занят (обслуживает заявку), очереди нет,

Канал занят, одна заявка стоит в очереди,

Канал занят, заявок стоят в очереди,

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

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

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

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

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

(20.12)

Вероятности найдутся по формулам:

откуда, с учетом (20.12), найдем окончательно:

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

Найдем среднее число заявок в СМО . Тут придется немного повозиться. Случайная величина Z - число заявок в системе - имеет возможные значения с вероятностями

Ее математическое ожидание равно

(20.14)

(сумма берется не от 0 до а от 1 до так как нулевой член равен нулю).

Подставим в формулу (20.14) выражение для

Теперь вынесем за знак суммы :

Тут мы опять применим «маленькую хитрость»: есть не что иное, как производная пор от выражения значит,

Меняя местами операции дифференцирования и суммирования, получим:

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

(20.16)

Ну, а теперь применим формулу Литтла (19.12) и наймем среднее время пребывания заявки в системе:

Найдем среднее число заявок в очереди Будем рассуждать так: число заявок в очереди равно числу заявок в системе минус чйсло заявок, находящихся под обслуживанием. Значит (по правилу сложения математических ожиданий), среднее число заявок в очереди равно среднему числу заявок в системе минус среднее число заявок под обслуживанием. Число заявок под обслуживанием может быть либо нулем (если канал свободен), либо единицей (если он занят). Математическое ожидание такой случайной величины равно вероятности того, что канал занят (мы ее обозначили ). Очевидно, равно единице минус вероятность того, что канал свободен;

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

Имеется n-канальная СМО с неограниченной очередью. Она характеризуется следующими показателями :

Предельные вероятности:

, , . . . , , ,…, ,… (10)

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

(11)

(13)

Среднее время нахождения в очереди:

(15)

Среднее время нахождения заявки в очереди:

Рассмотрим пример решения задачи многоканальной СМО с ожиданием.

Задача . В магазине к кассам поступает поток покупателей с интенсивностью 81 человек в час. Средняя продолжительность обслуживания кассиром одного покупателя tобсл = 2 мин. Определить предельные вероятности состояний и характеристики обслуживания узла расчета.

По условию λ=81(чел./час)= 81/60=1,35 (чел./мин.). По формулам (1, 2):

= λ/μ= λ * tобсл = 1,35 * 2 = 2,7

<1, т.е. при n > = 2,7. Таким образом, минимальное количество кассиров n =3.

Найдем характеристики обслуживания СМО при n=3.

Вероятность того, что в кассах отсутствуют покупатели, по формуле (9):

= (1+2,7+2,7 /2!+2,7 /3!+2,7 /3!(3-2,7)) = 0,025

В среднем 2,5 % времени кассиры будут простаивать.

Вероятность того, что в кассах будет очередь, определим по формуле (11):

P = (2,7 /3!(3-2,7))0,025 = 0,735

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

L = (2,7 /(3*3!(1-2,7/3) ))*0,025 = 7,35 (чел.)

T =7,35/1,35 = 5,44 (мин.)

Определим среднее число покупателей в кассах по формуле (15):

L =7,35+2,7=10,05 (чел.)

Среднее время нахождения покупателей в кассах находится по формуле (16):

T =10,05/1,35=7,44 (мин)

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

Коэффициент (доля) занятых обслуживанием кассиров вычисляется по следующей формуле:

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

Системы массового обслуживания с ограниченной очередью

Имеется n-канальная СМО с ограниченной очередью. Число заявок в очереди ограничено числом m. Если заявка поступает в момент, когда в очереди уже m заявок, она не обслуживается. Такая СМО характеризуется следующими показателями :

Предельные вероятности:

(17)

, , . . . , , ,…, (18)

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

(19)

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

Абсолютная пропускная способность:

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

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

(23)

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

Пример оптимизации СМО

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

Задача.

Определить оптимальное количество причалов в порту с минимальными затратами, если известно, что за год было обслужено 270 судов. Разгрузка одного судна длится в среднем 12 часов. Пеня за простой судна в порту составляет 100 тыс.р./сут.. Затраты на причал 150 тыс.р./сут. Расчеты приведены в таблице.

Решение.

По условию

λ=270(судов/год)=270/360=0,75(судов/сут.),

tобсл=12ч=12/24=0,5 сут.

По формулам (1, 2):

= λ/μ= λ * tобсл = 0,75 * 0,5 = 1,5

Очередь не будет возрастать до бесконечности при условии /n <1, т.е. при n > = 1,5. Таким образом, минимальное количество причалов n =2.

Найдем характеристики обслуживания СМО порта при количестве причалов n=2.

Вероятность того, что в порту отсутствуют суда, вычислим по формуле (9):

В среднем 1,4 % времени причалы будут простаивать.

Среднее число судов, находящихся в очереди рассчитывается по формуле (13):

Среднее время ожидания в очереди вычисляется по формуле (14):

T =1,93/0,75 = 2,57 (сут.)

Определим среднее число судов в порту по формуле (15):

L =1,93+1,5=3,43 (судна)

Среднее время нахождения судов в порту находится по формуле (16):

T =3,43 /0,75 =4,57 (сут)

Среднее число занятых причалов (12) =1,5.

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

Найдем суммарную пеню за простой судов в порту в сутки. Для этого перемножим пеню за простой судна в порту и среднее число судов в очереди:

= * L .

Определим затраты по обслуживанию причалов в сутки: = *n.

Для двух причалов в сутки

Суммарные затраты составят: С= + =193+300=493(ден.ед.)

Суммарные затраты по условию задачи должны быть минимальны.

Рассчитаем суммарные затраты для количества причалов n = 2, 3, 4. Расчеты приведены в таблице. Как видно из таблицы, минимальные затраты достигаются при n = 3. Следовательно, для минимизации затрат необходимо 3 причала.

Таблица 1.- Расчет оптимального числа причалов

Показатель	Количество причалов
Интенсивность потока судов	0,75	0,75	0,75
Интенсивность обслуживания судов	0,5	0,5	0,5
Интенсивность нагрузки причала	1,5	1,5	1,5
Вероятность, что все причалы свободны	0,14	0,21	0,22
Среднее число судов в очереди	1,93	0,24	0,04
Среднее время пребывания судна в очереди, сут.	2,57	0,32	0,06
Среднее число судов в порту	3,43	1,74	1,54
Среднее время пребывания судна в порту, сут	4,57	2,32	2,06
Пеня за простой судна в порту, ден.ед./сут. ()	100,00	100,00	100,00
Затраты по обслуживанию причала в сутки, ден.ед./сут. ()	150,00	150,00	150,00
Суммарная пеня за простой судов в порту в сутки, ден.ед. ()	192,86	23,68	4,48
Суммарные затраты по обслуживанию причалов в сутки, ден.ед. ()	300,00	450,00	600,00
Суммарные затраты, ден.ед.(С)	492,86	473,68	604,48

Варианты заданий

Таблица 2 - Варианты заданий

Номер варианта
Задача
Номер варианта
Задача

1. В парикмахерской в зависимости от сложности стрижки, мастер выполняет работу в среднем за 30 мин. Посетители приходят в среднем через 25 мин. За каждый час работы мастер зарабатывает 300 ден.ед.. Очередь ограничена до 4 человек. Если в очереди больше 4 человек, клиент уходит, и потери за час составляют 150 ден.ед. Определить предельные вероятности состояний и характеристики обслуживания. Определить оптимальное количество мастеров.

2. Автомобили подъезжают на АЗС со средней частотой 2 автомобиля за 5 минут. Заправка автомобиля в среднем длится 3 минуты. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество колонок, чтобы средняя длина очереди не превышала 3 авт.

3. Рассматривается круглосуточная работа пункта проведения профилактического осмотра автомашин. На осмотр и выявление дефектов каждой машины затрачивается в среднем 30 минут. На осмотр поступает в среднем 36 машин в сутки. Если машина, прибывшая в пункт осмотра, не застает ни одного канала свободным, она покидает пункт осмотра не обслуженной. Определить вероятности состояний и характеристики обслуживания профилактического пункта осмотра. Определить количество каналов, чтобы относительная пропускная способность была не меньше 0,8.

4. В срочной мастерской по починке обуви в зависимости от сложности ремонта мастеру требуется в среднем 15 мин. Посетители приходят в среднем через каждые 14 мин. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество мастеров, чтобы средняя длина очереди не превышала 5 заказов.

5. В справочной оператор дает справку в среднем за 4 мин. Звонки поступают каждые 3мин. Если операторы заняты, то звонок не обслуживается. Определить вероятности состояний и характеристики обслуживания справочной. Определить количество каналов, чтобы относительная пропускная способность была не меньше 0,75.

6. В зависимости от количества продуктов у покупателя кассиру в магазине требуется в среднем на один чек 2 мин. Покупатели подходят к кассе с интенсивностью 81 человек/час. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество кассиров, чтобы средняя длина очереди не превышала 4 покупателей.

7. Диспетчеру в АТП в зависимости от типа автомобиля требуется в среднем на выдачу одного маршрутного листа 20 минут. Заявки на автомобили поступают в среднем через каждые 30 минут. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество диспетчеров, чтобы средняя длина очереди не превышала 2 заявок.

8. Требуется оценить работу АТС. Если все линий связи заняты, то абонент выбывает из системы. Звонки поступают с интенсивностью 2 вызов/мин.. Продолжительность разговоров распределена экспоненциально, и в среднем равна 1,5 мин. Определить предельные вероятности и показатели эффективности системы. Определить количество операторов, чтобы относительная пропускная способность АТС была не меньше 0,9.

9. В банке в зависимости от сложности запроса клиента кассиру требуется в среднем 10 минут. Клиенты подходят к нему в среднем через каждые 12 минут. Кассир зарабатывает 15000 ден.ед. за месяц. Очередь ограничена до 6 человек. Если в очереди больше 6 человек, клиент уходит, и потери за час составляют 200 ден.ед. Определить предельные вероятности состояний и характеристики обслуживания. Определить оптимальное количество кассиров.

10. В среднем на одну транзакцию у банкомата уходит 2 минуты. Клиенты подходят к нему в среднем через каждые 20 минут. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество банкоматов, чтобы средняя длина очереди не превышала 2 человек.

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

12. В отделе заказов мебельной фабрики менеджеру по продажам в зависимости от заказа клиента требуется в среднем на оформление одного заказа 25 минут. Клиенты приходят в среднем через каждые 30 минут. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество менеджеров, чтобы средняя длина очереди не превышала 3 человек.

Порядок выполнения работы

1.Рассчитайте в системе Excel показатели системы массового обслуживания по формулам, приведенным в методичке. Количество каналов обслуживания n=1, 2, 3...k перебирается для нахождения оптимального значения по варианту. Предполагается, что входные потоки и обслуживание соответствуют пуассоновскому распределению.

2.Проведите анализ полученных результатов.

3.Составьте отчет.

1) Цель работы;

2) постановка задачи;

3) результаты расчетов, проведенных в Excel;

4) выводы по выполнению работы.

Контрольные вопросы

1. Что включает в себя понятие система массового обслуживания?

2. Какие существуют виды систем массового обслуживания?

3. Что относится к основным характеристикам и показателям эффективности систем массового обслуживания?

4. Укажите основные свойства (характеристики) входящего потока требований?

5. Перечислите основные особенности и характеристики систем массового обслуживания с ожиданием?

6. Каковы основные характеристики СМО с отказами?

7. Приведите примеры различных видов СМО?

Библиографический список

1. Афанасьев М.Ю. Исследование операций в экономике: модели, задачи, решения. / М.Ю. Афанасьев, Б.П. Суворов.- М.:ИНФРА, 2003.-444с.

2. Вентцель Е.С. Исследование операций. Задачи, приниципы, методология./ Е.С. Вентцель.-М.: Высшая школа, 2001.-208с.

3. Зайченко Ю.П. Исследование операций./ Ю.П. Зайченко.- К.: Вища школа, 1975.-320с.

4. Конюховский П.В. Математические методы исследования операций. / П.В. Конюховский.- СПб.: Питер, 2001.-192с.

5. Кремер Н.Ш., Путко Б.А. Исследование операций в экономике./ Н.Ш. Кремер, Б.А. Бутко, И.М. Тришин.- М.:Банки и биржи, ЮНИТИ, 1997.-407с.

1. Кудрявцев Е.М. GPSS World.Основы имитационного моделирования различных систем.- М.: ДМК Пресс, 2004.- 320 с.

2. Советов В.Я., Яковлев С.А. Моделирование систем. - М.: Высшая школа, 1985

3. Советов В.Я., Яковлев С.А. Моделирование систем: курсовое проектирование. - М.: Высшая школа, 1989

операции или эффективности системы массового обслуживания являются следующие.

Для СМО с отказами :

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

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

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

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

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

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

Рассмотрим примеры некоторых СМО.

2.5.1. Многоканальная СМО с отказами

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

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

Описание состояний:

Все инспекторы свободны;

Занят один инспектор;

Заняты два инспектора;

Заняты три инспектора.

Граф состояний системы приведен на рис. 2.11 .

Рис. 2.11.

На графе: - интенсивность потока грузовых автомобилей; - интенсивность проверок документов одним автоинспектором.

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

Решение

Искомая часть вероятности - вероятности занятости всех трех инспекторов. Поскольку граф состояний представляет типовую схему "гибели и размножения", то найдем , используя зависимости (2.2).

Пропускную способность этого поста автоинспекторов можно характеризовать относительной пропускной способностью :

Пример 2.6 . Для приема и обработки донесений от разведгруппы в разведотделе объединения назначена группа в составе трех офицеров. Ожидаемая интенсивность потока донесений - 15 донесений в час. Среднее время обработки одного донесения одним офицером - . Каждый офицер может принимать донесения от любой разведгруппы. Освободившийся офицер обрабатывает последнее из поступивших донесений. Поступающие донесения должны обрабатываться с вероятностью не менее 95 %.

Определить, достаточно ли назначенной группы из трех офицеров для выполнения поставленной задачи.

Решение

Группа офицеров работает как СМО с отказами, состоящая из трех каналов.

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

Описание состояний и граф состояний СМО будут аналогичны приведенным в примере 2.5.

Поскольку граф состояний - это схема "гибели и размножения", то для нее имеются готовые выражения для предельных вероятностей состояния:

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

В примере .

В рассматриваемой СМО отказ наступает при занятости всех трех каналов, то есть . Тогда:

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

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

2.5.2. Многоканальная СМО с ожиданием

Пример 2.7 . На участке форсирования реки имеются 15 однотипных переправочных средств. Поток поступления техники на переправу в среднем составляет 1 ед./мин, среднее время переправы одной единицы техники - 10 мин (с учетом возвращения назад переправочного средства).

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

Решение

Абсолютная пропускная способность , т. е. все, что подходит к переправе, тут же практически переправляется.

Среднее число работающих переправочных средств:

Коэффициенты использования и простоя переправы:

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

Коэффициенты использования переправы после 50 прогонов практически совпадают: .

Максимальная длина очереди 15 ед., среднее время пребывания в очереди около 10 мин.

Назначение сервиса СМО . Онлайн-калькулятор предназначен для расчета следующих показателей одноканальных СМО:

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

Инструкция . Для решения подобных задач в онлайн режиме выберите модель СМО. Укажите интенсивность потока заявок λ и интенсивность потока обслуживания μ . Для одноканальной СМО с ограниченной длиной очереди можно указать длину очереди m , а для одноканальной СМО с неограниченной очередью - число заявок в очереди (для расчета вероятности нахождения этих заявок в очереди). см. пример решения . . Полученное решение сохраняется в файле Word .

Классификация одноканальных систем массового обслуживания

Пример №1 . Авто заправочная станция имеет одну бензоколонку. Предполагается что простейший поток автомашин поступает на станцию с интенсивностью λ=11 автомашин/ч. Время обслуживания заявки случайная величина которая подчиняется экспоненциальному закону с параметром μ=14 автомашин/ч. Определить среднее число автомашин на станции.

Пример №2 . Имеется пункт проведения профилактического осмотра машин с одной группой проведения осмотра. На осмотр и выявление дефектов каждой машины затрачивается в среднем 0,4 часа. На осмотр поступает в среднем 328 машин в сутки. Потоки заявок и обслуживаний - простейшие. Если машина, прибывшая в пункт осмотра не застает ни одного канала свободным, она покидает пункт осмотра необслуженной. Определить предельные вероятности состояний и характеристики обслуживания пункта профилактического осмотра.
Решение. Здесь α = 328/24 ≈ = 13.67, t = 0.4. Эти данные необходимо ввести в калькулятор.

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

Алгоритм рассмотрения СМО с неограниченной очередью.

Постановка задачи.

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

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

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

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

Мы рассмотрим здесь классическую задачу теории массового обслуживания в тех условиях, в каких она была рассмотрена и решена К.Эрлангом. на n одинаковых приборов поступает простейший поток требований интенсивности. Если в момент поступления имеется хотя бы один свободный прибор, оно немедленно начинает обслуживаться. Если же все приборы заняты, то вновь прибывшее требование становится в очередь за всеми теми требованиями, которые поступили раньше и ещё не начали обслуживаться. Освободившийся прибор немедленно приступает к обслуживанию очередного требования, если только имеется очередь. Каждое требование обслуживается только одним прибором, и каждый прибор обслуживает в каждый момент времени не более одного требования. Длительность обслуживания представляет собой случайную величину с одним и тем же распределением вероятностей F(x). Предполагается, что при x0.

где - постоянная.

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

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

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

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

А так как всегда и

и, следовательно,

Требуемое доказано.

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

где > 0, a k -- целое положительное число.

Распределение Эрланга представляет собой распределение суммы k- независимых слагаемых, каждое из которых имеет рас-пределение (1).

Обозначим для случая распределения (1) через время обслуживания требования. Тогда средняя длительность обслуживания равна

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

Процесс обслуживания как марковский случайный процесс.

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

В каждый момент рассматриваемая система может находить-ся в одном из следующих состоянии: в момент t в системе на-ходятся k требовании (k=0, 1, 2, ...). Если krn, то в систе-ме находятся и обслуживаются k требований, а m-k - приборов свободны. Если km, то m требований обслуживаются, а k-m находятся в очереди и ожидают обслуживания. Обозначим через состояние, когда в системе находятся k требований. Таким образом, система может находиться в состояниях .. . Обозначим через -- вероятность того, что система в мо-мент t окажется в состоянии .

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

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

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

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

Составление уравнений.

Задача теперь состоит в том, чтобы найти те уравнения, которым удовлетворяют вероятности. Одно из уравнения очевидно, a именно для каждого t

Найдём сначала вероятность того, что и момент t.+h все приборы свободны. Это может произойти следующими способами:

в момент t все приборы были свободны и за время h новых требований не поступало;

в момент t один прибор был занят обслуживанием требования, все остальные приборы свободны; за время h обслуживание требования было завершено и новых требований не поступило.

Остальные возможности, как-то: были заняты два или три прибора и за время h работа на них была закончена - имеют вероятность о(h), как легко в этом убедится.

Вероятность первого из указанных событий равна

вероятность второго события

Таким образом

Отсюда очевидным образом приходим уравнению

Перейдём теперь к составлению уравнений для при 1. Рассмотрим отдельно два различных случая: 1 и. Пусть в начале 1. Перечислим только существенные состояния, из которых можно прийти в состояние в момент t+h. Эти состояния таковы:

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

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

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

Все остальные мыслимые возможности перехода в состояние за промежуток времени h имеют вероятность, равную о(h).

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

Несложные преобразования приводят от этого равенства к такому уравнению для 1;

Подобные же рассуждения для приводят к уравнению

Для определения вероятностей получили бесконечную систему дифференциальных уравнений (2)-(5). Её реше-ние представляет несомненные технические трудности.

Определение стационарного решения.

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

при .

Сказанное позволяет заключить, что уравнения (3), (4), (5) для стационарных вероятностей принимают следующий вид:

К этим уравнениям добавляется нормирующее условие

Для решения полученной бесконечной алгебраической системы введём обозначения:

Система уравнений (6)-(8) в этих обозначениях принимает такой вид:

Отсюда заключаем, что при всех

Введём для удобства записи обозначение

Уравнение (10) позволяет заключить, что

При из (11) находим, что

и, следовательно, при

Остаётся найти. Для этого в (9) подставляем выражения из (12) и (13). В результате

так как бесконечная сумма, стоящая в квадратных скобках, сходится только при условии, что

то при этом предположении находим равенство

Если условие (14) не выполнено, т.е. если, то ряд, стоящий в квадратной скобке уравнения для определения , расходится и, значит, должно быть равно 0. Но при этом, как следует из (12) и (13), при всех оказывается.

Методы теории цепей Маркова позволяют заключить, что при с течением времени очередь стремится к по ве-роятности.

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

Пусть врач успевает удовлетворительно осмотреть больного и заполнить его историю болезни в среднем за 15 минут. Планирующие органы из этого обычно делают вывод: за четырёхчасовый рабочий день врач должен принимать 16 человек. Однако больные приходят в случайные моменты времени. В ре-зультате при таком подсчете пропускной способности врача к нему неизбежно скапливается очередь, так как при проведен-ном подсчете принимается равным 1. Те же заключения от-носятся и к расчету числа коек в больницах, числа работа-ющих касс в магазинах, числа официантов в ресторанах и т. д. К сожалению, некоторые экономисты совершают такую же ошибку и при расчете погрузочных средств в карьерах, числе приемщиков на элеваторах, числе причалов в морских портах и пр.

Во всем дальнейшем мы предполагаем, что условие (14) выполнено.

Некоторые подготовительные результаты.

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

Прежде чем преобразовать эту формулу к виду, удобному для использования, приготовим некоторые необходимые для дальнейшего сведения. Прежде всего для случаев m=1 и m=2 найдем простые формулы для . Несложные преобразования приводят к таким равенствам: при m= 1

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

Эта формула для m=1 принимает особенно простой вид:

В формуле (19) может принимать любое значение от 0 до m (исключительно). Так что в формуле (20) < 1, а в (21) <2.

Определение функции распределения длительности ожи-дания.

Если в момент поступления требования в очереди уже находились k-m требований, то, поскольку обслуживание про-исходит в порядке очередности, вновь поступившее требование должно ожидать, когда будут обслужены k-m+ 1 требований. Пусть означает вероятность того, что за промежуток вре-мени длительности t после поступления интересующего тре-бования закончилось обслуживание ровно s требований. Ясно, что при имеет место равенство

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

Если все приборы заняты обслуживанием и ещё имеется достаточная очередь требований, которые ожидают обслуживания, то поток обслуженных требований будет простейшим. Действи-тельно, в этом случае все три условия -- стационарность, отсут-ствие последействия и ординарность -- выполнены. Вероятность освобождения за промежуток времени t ровно s приборов равна (это можно показать и простым подсчетом)

и, следовательно,

Но вероятности известны:

Очевидными преобразованиями приводим правую часть по-следнего равенства к виду

Из формул (18) и (19) следует, что поэтому при m0

Само собой разумеется, что при t0

Функция имеет в точке t=1 разрыв непрерывности, равный вероятности застать все приборы занятыми.

Средняя длительность ожидания.

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

Несложные вычисления приводят к формуле

Дисперсия величины равна

Формула (23) даёт среднюю длительность ожидания одного требования. Найдем среднюю потерю времени требованиями, пришедшими в систему обслуживания в течение промежутка времени T. За время T в систему поступает требований и среднем; общая потеря ими времени па ожидание в среднем равна

Приведем небольшие арифметические подсчеты, которые про-демонстрируют нам, как быстро возрастают суммарные потери времени па ожидание с изменением величины. При этом мы ограничиваемся случаем Т=1 и рассматриваем лишь самые малые значения т: т =1 и т=2.

При т =1 в силу (20)

При р=0,1; 0,3; 0,5; 0,9 значение а приблизительно равно 0,011; 0,267; 0,500; 1,633; 8,100.

При m=2 в силу (24)

При =0,1; 1,0; 1,5; 1,9 значение а приблизительно равно 00003; 0,333; 1,350; 17,537.

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