Смо с неограниченной очередью пример. Одноканальная смо с очередью

Федеральное агентство по образованию РФ

ФГОУ СПО «Перевозский строительный колледж»

Курсовая работа

по дисциплине «Математические методы»

на тему «СМО с ограниченным временем ожидания. Замкнутые СМО»

Введение.......................................................................................................... 2

1. Основы теории массового обслуживания.................................................. 3

1.1 Понятие случайного процесса.................................................................. 3

1.2 Марковский случайный процесс.............................................................. 4

1.3 Потоки событий......................................................................................... 6

1.4 Уравнения Колмогорова для вероятностей состояний. Финальные вероятности состояний......................................................................................................... 9

1.5 Задачи теории массового обслуживания............................................... 13

1.6 Классификация систем массового обслуживания.................................. 15

2. Системы массового обслуживания с ожиданием..................................... 16

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

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

3. Замкнутые СМО........................................................................................ 37

Решение задачи............................................................................................. 45

Заключение.................................................................................................... 50

Список литературы....................................................................................... 51

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

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

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

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

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

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

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

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

Т.е. здесь как, например, в теории игр задачи рассматриваются в условиях неопределенности .

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

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

Пусть имеется некоторая система S (техническое устройство, группа таких устройств, технологическая система – станок, участок, цех, предприятие, отрасль промышленности и т.д.). В системе S протекает случайный процесс , если она с течением времени меняет свое состояние (переходит из одного состояния в другое), причем, заранее неизвестным случайным образом.

Примеры:

1. Система S – технологическая система (участок станков). Станки время от времени выходят из строя и ремонтируются. Процесс, протекающий в этой системе, случаен.

2. Система S – самолет, совершающий рейс на заданной высоте по определенному маршруту. Возмущающие факторы – метеоусловия, ошибки экипажа и т.д., последствия – «болтанка», нарушение графика полетов и т.д.

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

Пусть в настоящий момент t 0 система находится в определенном состоянии S 0 . Мы знаем характеристики состояния системы в настоящем и все, что было при t <t 0 (предысторию процесса). Можем ли мы предугадать (предсказать) будущее, т.е. что будет при t >t 0 ? В точности – нет, но какие-то вероятностные характеристики процесса в будущем найти можно. Например, вероятность того, что через некоторое время система S окажется в состоянии S 1 или останется в состоянии S 0 и т.д.

Пример . Система S – группа самолетов, участвующих в воздушном бою. Пусть x – количество «красных» самолетов, y – количество «синих» самолетов. К моменту времени t 0 количество сохранившихся (не сбитых) самолетов соответственно – x 0 , y 0 . Нас интересует вероятность того, что в момент времени численный перевес будет на стороне «красных». Эта вероятность зависит от того, в каком состоянии находилась система в момент времени t 0 , а не от того, когда и в какой последовательности погибали сбитые до момента t 0 самолеты.

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

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

Процесс называется процессом с дискретным состоянием , если его возможные состояния S 1 , S 2 , … можно заранее определить, и переход системы из состояния в состояние происходит «скачком», практически мгновенно.

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

Пример . Технологическая система (участок) S состоит из двух станков, каждый из которых в случайный момент времени может выйти из строя (отказать), после чего мгновенно начинается ремонт узла, тоже продолжающийся заранее неизвестное, случайное время. Возможны следующие состояния системы:

S 0 - оба станка исправны;

S 1 - первый станок ремонтируется, второй исправен;

S 2 - второй станок ремонтируется, первый исправен;

S 3 - оба станка ремонтируются.

Переходы системы S из состояния в состояние происходят практически мгновенно, в случайные моменты выхода из строя того или иного станка или окончания ремонта.

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

Рис. 1. Граф состояний системы

Примечание. Переход из состояния S 0 в S 3 на рисунке не обозначен, т.к. предполагается, что станки выходят из строя независимо друг от друга. Вероятностью одновременного выхода из строя обоих станков мы пренебрегаем.

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

В предыдущем примере – это поток отказов и поток восстановлений. Другие примеры: поток вызовов на телефонной станции, поток покупателей в магазине и т.д.

Поток событий можно наглядно изобразить рядом точек на оси времени O t – рис. 2.

Рис. 2. Изображение потока событий на оси времени

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

Интенсивность потока событий ( ) – это среднее число событий, приходящееся на единицу времени.

Рассмотрим некоторые свойства (виды) потоков событий.

Поток событий называется стационарным , если его вероятностные характеристики не зависят от времени.

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

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

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

Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами:

1) стационарен;

2) ординарен;

3) не имеет последствий.

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

Для простейшего потока с интенсивностью интервал T между соседними событиями имеет так называемое показательное (экспоненциальное) распределение с плотностью:

где - параметр показательного закона.

Для случайной величины T , имеющей показательное распределение, математическое ожидание есть величина, обратная параметру, а среднее квадратичное отклонение равно математическому ожиданию:

Рассматривая Марковские процессы с дискретными состояниями и непрерывным временем, подразумевается, что все переходы системы S из состояния в состояние происходят под действием простейших потоков событий (потоков вызовов, потоков отказов, потоков восстановлений и т.д.). Если все потоки событий, переводящие систему S из состояния в состояние простейшие, то процесс, протекающий в системе, будет Марковским.

Итак, на систему, находящуюся в состоянии , действует простейший поток событий. Как только появится первое событие этого потока, происходит «перескок» системы из состояния в состояние (на графе состояний по стрелке ).

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

Рис. 3. Размеченный граф состояний системы

На этом рисунке - интенсивности потока отказов; - интенсивности потока восстановлений.

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

Пусть система находится в состоянии S 0 . В состояние S 1 ее переводит поток отказов первого станка. Его интенсивность равна:

где - среднее время безотказной работы первого станка.

Из состояния S 1 в S 0 систему переводит поток «окончаний ремонтов» первого станка. Его интенсивность равна:

где - среднее время ремонта первого станка.

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

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

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

Что будет происходить с вероятностями состояний при ? Будут ли стремиться к каким-либо пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний .

где - конечное число состояний системы.

Финальные вероятности состояний – это уже не переменные величины (функции времени), а постоянные числа. Очевидно, что:

Финальная вероятность состояния – это по–существу среднее относительное время пребывания системы в этом состоянии.

Например, система S имеет три состояния S 1 , S 2 и S 3 . Их финальные вероятности равны соответственно 0,2; 0,3 и 0,5. Это значит, что система в предельном стационарном состоянии в среднем 2/10 времени проводит в состоянии S 1 , 3/10 – в состоянии S 2 и 5/10 – в состоянии S 3 .

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

Пользуясь этим правилом, напишем систему уравнений для нашего примера :

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

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

Четвертое уравнение отбрасываем, добавляя вместо него нормировочное условие:

Т.е. в предельном, стационарном режиме система S в среднем 40% времени будет проводить в состоянии S 0 (оба станка исправны), 20% - в состоянии S 1 (первый станок ремонтируется, второй работает), 27% - в состоянии S 2 (второй станок ремонтируется, первый работает), 13% - в состоянии S 3 (оба станка ремонтируются). Знание этих финальных вероятностей может помочь оценить среднюю эффективность работы системы и загрузку ремонтных органов.

Пусть система S в состоянии S 0 (полностью исправна) приносит в единицу времени доход 8 условных единиц, в состоянии S 1 – доход 3 условные единицы, в состоянии S 2 – доход 5 условных единиц, в состоянии S 3 – не приносит дохода. Тогда в предельном, стационарном режиме средний доход в единицу времени будет равен: условных единиц.

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

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

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

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

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

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

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

Первое деление (по наличию очередей):

1. СМО с отказами;

2. СМО с очередью.

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

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

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

Итак, например, рассматриваются следующие СМО:

· СМО с нетерпеливыми заявками (длина очереди и время обслуживания ограничено);

· СМО с обслуживанием с приоритетом, т.е. некоторые заявки обслуживаются вне очереди и т.д.

Кроме этого СМО делятся на открытые СМО и замкнутые СМО.

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

Классификация СМО далеко не ограничивается приведенными разновидностями, но этого достаточно.

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

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

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

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

Канал занят, очереди нет;

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

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

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

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

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

Изображенная на рис. 4 схема представляет собой схему размножения и гибели. Напишем выражения для предельных вероятностей состояний:

(5)

или с использованием: :

(6)

Последняя строка в (6) содержит геометрическую прогрессию с первым членом 1 и знаменателем р, откуда получаем:

(7)

в связи с чем предельные вероятности принимают вид:

(8).

Выражение (7) справедливо только при < 1 (при = 1 она дает неопределенность вида 0/0). Сумма геометрической прогрессии со знаменателем = 1 равна m+2, и в этом случае:

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

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

(9).

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

(10).

Средняя длина очереди. Найдем среднее число -заявок, находящихся в очереди, как математическое ожидание дискретной случайной величины R-числа заявок, находящихся в очереди:

С вероятностьюв очереди стоит одна заявка, с вероятностью- две заявки, вообще с вероятностьюв очереди стоят k-1 заявок, и т.д., откуда:

(11).

Поскольку , сумму в (11) можно трактовать как производную по от суммы геометрической прогрессии:

Подставляя данное выражение в (11) и используя из (8), окончательно получаем:

(12).

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

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

(13).

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

Если же k=m+1, т.е. когда вновь приходящая заявка застает канал обслуживания занятым и m-заявок в очереди (вероятность этого ), то в этом случае заявка не становится в очередь (и не обслуживается), поэтому время ожидания равно нулю. Среднее время ожидания будет равно:

если подставить сюда выражения для вероятностей (8), получим:

(14).

Здесь использованы соотношения (11), (12) (производная геометрической прогрессии), а также из (8). Сравнивая это выражение с (12), замечаем, что иначе говоря, среднее время ожидания равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.

(15).

Среднее время пребывания заявки в системе. Обозначим - матожидание случайной величины - время пребывания заявки в СМО, которое складывается из среднего времени ожидания в очереди и среднего времени обслуживания . Если загрузка системы составляет 100%, очевидно, , в противном же случае:

Пример 1. Автозаправочная станция (АЗС) представляет собой СМО с одним каналом обслуживания (одной колонкой).

Площадка при станции допускает пребывание в очереди на заправку не более трех машин одновременно (m = 3). Если в очереди уже находятся три машины, очередная машина, прибывшая к станции, в очередь не становится. Поток машин, прибывающих для заправки, имеет интенсивность =1 (машина в минуту). Процесс заправки продолжается в среднем 1,25 мин.

Определить:

вероятность отказа;

относительную и абсолютную пропускную способности АЗС;

среднее число машин, ожидающих заправки;

среднее число машин, находящихся на АЗС (включая обслуживаемую);

среднее время ожидания машины в очереди;

среднее время пребывания машины на АЗС (включая обслуживание).

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

Находим вначале приведенную интенсивность потока заявок: =1/1,25=0,8; =1/0,8=1,25.

По формулам (8):

Вероятность отказа 0,297.

Относительная пропускная способность СМО: q=1-=0,703.

Абсолютная пропускная способность СМО: A==0,703 машины в мин.

Среднее число машин в очереди находим по формуле (12):

т.е. среднее число машин, ожидающих в очереди на заправку, равно 1,56.

Прибавляя к этой величине среднее число машин, находящихся под обслуживанием:

получаем среднее число машин, связанных с АЗС.

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

Прибавляя к этой величине , получим среднее время, которое машина проводит на АЗС:

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

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

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

Если, то соотношения (8) принимают вид:

(16).

При отсутствии ограничений по длине очереди каждая заявка, пришедшая в систему, будет обслужена, поэтому q=1, .

Среднее число заявок в очереди получим из (12) при :

Среднее число заявок в системе по формуле (13) при :

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

Наконец, среднее время пребывания заявки в СМО есть:

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

Состояния системы нумеруются по числу заявок, связанных системой:

нет очереди:

Все каналы свободны;

Занят один канал, остальные свободны;

Заняты -каналов, остальные нет;

Заняты все -каналов, свободных нет;

есть очередь:

Заняты все n-каналов; одна заявка стоит в очереди;

Заняты все n-каналов, r-заявок в очереди;

Заняты все n-каналов, r-заявок в очереди.

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

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

Граф типичен для процессов размножения и гибели, для которой решение ранее получено. Напишем выражения для предельных вероятностей состояний, используя обозначение : (здесь используется выражение для суммы геометрической прогрессии со знаменателем ).

Таким образом, все вероятности состояний найдены.

Определим характеристики эффективности системы.

Вероятность отказа. Поступившая заявка получает отказ, если заняты все n-каналов и все m-мест в очереди:

(18)

Относительная пропускная способность дополняет вероятность отказа до единицы:

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

(19)

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

Обозначим среднее число занятых каналов . Каждый занятый канал обслуживает в среднем -заявок в единицу времени, а СМО в целом обслуживает в среднем А-заявок в единицу времени. Разделив одно на другое, получим:

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

(20)

Здесь опять (выражение в скобках) встречается производная суммы геометрической прогрессии (см. выше (11), (12) - (14)), используя соотношение для нее, получаем:

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

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

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

(21)

Так же, как и в случае одноканальной СМО с ожиданием, отметим, что это выражение отличается от выражения для средней длины очереди (20) только множителем , т. е.

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

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

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

Вероятности состояний получим из формул предельным переходом (при ). Заметим, что сумма соответствующей геометрической прогрессии сходится при и расходится при >1. Допустив, что <1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:

(22)

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

Среднее число заявок в очереди получим при из (20):

а среднее время ожидания - из (21):

Среднее число занятых каналов , как и ранее, определяется через абсолютную пропускную способность:

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

Пример 2. Автозаправочная станция с двумя колонками (n = 2) обслуживает поток машин с интенсивностью =0,8 (машин в минуту). Среднее время обслуживания одной машины:

В данном районе нет другой АЗС, так что очередь машин перед АЗС может расти практически неограниченно. Найти характеристики СМО.

Поскольку<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:

и т. д.

Среднее число занятых каналов найдем, разделив абсолютную пропускную способность СМО А==0,8 на интенсивность обслуживания =0,5:

Вероятность отсутствия очереди у АЗС будет:

Среднее число машин в очереди:

Среднее число машин на АЗС:

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

Среднее время пребывания машины на АЗС:

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

Рассмотрим СМО подобного типа, предполагая, что ограничение времени ожидания является случайной величиной.

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

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

нет очереди:

Все каналы свободны;

Занят один канал;

Заняты два канала;

Заняты все n-каналов;

есть очередь:

Заняты все n-каналов, одна заявка стоит в очереди;

Заняты все n-каналов, r-заявок стоят в очереди и т. д.

Граф состояний и переходов системы показан на рис. 23.

Рис. 23. СМО с ограниченным временем ожидания

Разметим этот граф, как и раньше; у всех стрелок, ведущих слева направо, будет стоять интенсивность потока заявок . Для состояний без очереди у стрелок, ведущих из них справа налево, будет, как и раньше, стоять суммарная интенсивность потока обслуживании всех занятых каналов. Что касается состояний с очередью, то у стрелок, ведущих из них справа налево, будет стоять суммарная интенсивность потока обслуживания всех n-каналов плюс соответствующая интенсивность потока уходов из очереди. Если в очереди стоят r-заявок, то суммарная интенсивность потока уходов будет равна .

Как видно из графа, имеет место схема размножения и гибели; применяя общие выражения для предельных вероятностей состояний в этой схеме (используя сокращенные обозначения , запишем:

(24)

Отметим некоторые особенности СМО с ограниченным ожиданием сравнительно с ранее рассмотренными СМО с «терпеливыми» заявками.

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

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

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

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

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

Среднее число занятых каналов по-прежнему получаем, деля абсолютную пропускную способность А на :

(26)

Среднее число заявок в очереди. Соотношение (26) позволяет вычислить среднее число заявок в очереди , не суммируя бесконечного ряда (25). Из (26) получаем:

а входящее в эту формулу среднее число занятых каналов можно найти как математическое ожидание случайной величины Z, принимающей значения 0, 1, 2,..., n с вероятностями ,:

В заключение заметим, что если в формулах (24) перейти к пределу при (или, что то же, при ), то при получатся формулы (22), т. е. «нетерпеливые» заявки станут «терпеливыми».

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

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

Пусть n - число каналов обслуживания, s - число потенциальных заявок, n <s , - интенсивность потока заявок каждого потенциального требования, μ - интенсивность обслуживания:

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

Р 0 = .

Финальные вероятности состояний системы:

P k = при k = при .

Через эти вероятности выражается среднее число занятых каналов

=P 1 + 2P 2 +…+n(P n +P n+ 1 +…+P s) или

=P 1 + 2P 2 +…+(n- 1)P n- 1 +n( 1-P 0 -P 1 -…-P n-1 ).

Через находим абсолютную пропускную способность системы:

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

М =s- =s- .

Пример 1 . На вход трехканальной СМО с отказами поступает поток заявок с интенсивностью =4 заявки в минуту, время обслуживания заявки одним каналом t обсл =1/μ =0,5 мин. Выгодно ли с точки зрения пропускной способности СМО заставить все три канала обслуживать заявки сразу, причем среднее время обслуживания уменьшается втрое? Как это скажется на среднем времени пребывания заявки в СМО?

Решение. Находим вероятность простоя трехканальной СМО по формуле

ρ = /μ =4/2=2, n=3,

Р 0 = = = 0,158.

Вероятность отказа определяем по формуле:

Р отк =Р n ==

P отк = 0,21.

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

Р обсл = 1-Р отк 1-0,21=0,79.

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

А= Р обсл 3,16.

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

1,58, доля каналов, занятых обслуживанием,

q = 0,53.

Cреднее время пребывания заявки в СМО находим как вероятность того, что заявка принимается к обслуживанию, умноженную на среднее время обслуживания: t СМО 0,395 мин.

Объединяя все три канала в один, получаем одноканальную систему с параметрами μ= 6, ρ= 2/3. Для одноканальной системы вероятность простоя:

Р 0 = = =0,6,

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

Р отк =ρ Р 0 = = 0,4,

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

Р обсл = 1-Р отк =0,6,

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

А= Р обсл =2,4.

t СМО =Р обсл = =0,1 мин.

В результате объединения каналов в один пропускная способность системы снизилась, так как увеличилась вероятность отказа. Среднее время пребывания заявки в системе уменьшилось.

Пример 2 . На вход трехканальной СМО с неограниченной очередью поступает поток заявок с интенсивностью =4 заявки в час, среднее время обслуживания одной заявки t =1/μ=0,5 ч. Найти показатели эффективности работы системы.

Для рассматриваемой системы n =3, =4, μ=1/0,5=2, ρ= /μ=2, ρ/n =2/3<1. Определяем вероятность простоя по формуле:

Р=.

P 0 = =1/9.

Среднее число заявок в очереди находим по формуле:

L =.

L = = .

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

t = = 0,22 ч.

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

Т=t+ 0,22+0,5=0,72.

Пример 3 . В парикмахерской работают 3 мастера, а в зале ожидания расположены 3 стула. Поток клиентов имеет интенсивность =12 клиентов в час. Среднее время обслуживания t обсл =20 мин. Определить относительную и абсолютную пропускную способность системы, среднее число занятых кресел, среднюю длину очереди, среднее время, которое клиент проводит в парикмахерской.

Для данной задачи n =3, m =3, =12, μ =3, ρ =4, ρ/n =4/3. Вероятность простоя определяем по формуле:

Р 0 =.

P 0 = 0,012.

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

Р отк =Р n+m = .

P отк =P n + m 0,307.

Относительная пропускная способность системы, т.е. вероятность обслуживания:

P обсл =1-P отк 1-0,307=0,693.

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

А= Р обсл 12 .

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

.

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

L =

L= 1,56.

Среднее время ожидания обслуживания в очереди:

t = ч.

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

M=L + .

Среднее время пребывания заявки в СМО:

Т=М/ 0,36 ч.

Пример 4 . Рабочий обслуживает 4 станка. Каждый станок отказывает с интенсивностью =0,5 отказа в час, среднее время ремонта t рем =1/μ=0,8 ч. Определить пропускную способность системы.

Эта задача рассматривает замкнутую СМО, μ =1,25, ρ=0,5/1,25=0,4. Вероятность простоя рабочего определяем по формуле:

Р 0 =.

P 0 = .

Вероятность занятости рабочего Р зан = 1-Р 0 . А=( 1-P 0 )μ =0,85μ станков в час.

Задача:

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

Найдите среднюю долю свободного времени для каждого рабочего и среднее время работы станка.

Найдите те же характеристики для системы, в которой:

а) за каждым рабочим закреплены два станка;

б) два рабочих всегда обслуживают станок вместе, причем с двойной интенсивностью;

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

Решение:

Возможны следующие состояния системы S:

S 0 – все станки исправны;

S 1 – 1 станок ремонтируется, остальные исправны;

S 2 – 2 станок ремонтируется, остальные исправны;

S 3 – 3 станок ремонтируется, остальные исправны;

S 4 – 4 станок ремонтируется, остальные исправны;

S 5 – (1, 2) станки ремонтируются, остальные исправны;

S 6 – (1, 3) станки ремонтируются, остальные исправны;

S 7 – (1, 4) станки ремонтируются, остальные исправны;

S 8 – (2, 3) станки ремонтируются, остальные исправны;

S 9 – (2, 4) станки ремонтируются, остальные исправны;

S 10 – (3, 4) станки ремонтируются, остальные исправны;

S 11 – (1, 2, 3) станки ремонтируются, 4 станок исправен;

S 12 – (1, 2, 4) станки ремонтируются, 3 станок исправен;

S 13 – (1, 3, 4) станки ремонтируются, 2 станок исправен;

S 14 – (2, 3, 4) станки ремонтируются, 1 станок исправен;

S 15 – все станки ремонтируются.

Граф состояний системы…

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

Если рабочий занят, он налаживает μ-станков в единицу времени, пропускная способность системы:

Ответ:

Средняя доля свободного времени для каждого рабочего ≈ 0,09.

Среднее время работы станка ≈ 3,64.

а) За каждым рабочим закреплены два станка.

Вероятность простоя рабочего определяется по формуле:

Вероятность занятости рабочего:

Если рабочий занят, он налаживает μ-станков в единицу времени, пропускная способность системы:

Ответ:

Средняя доля свободного времени для каждого рабочего ≈ 0,62.

Среднее время работы станка ≈ 1,52.

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

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

Сравнение 5 ответов:

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

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

Возможность применения теории принятия решений в системах массового обслуживания определяется следующими факторами:

1. Количество заявок в системе (которая рассматривается как СМО) должно быть достаточно велико (массово).

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

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

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

5. Необходимо исключить из системы субъектов или описывать их как требования с постоянной интенсивностью обработки.

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

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

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

1) http://www.5ballov.ru.

2) http://www.studentport.ru.

3) http://vse5ki.ru.

4) http://revolution..

5) Фомин Г.П. Математические методы и модели в коммерческой деятельности. М: Финансы и статистика, 2001.

6) Гмурман В.Е. Теория вероятностей и математическая статистика. М: Высшая школа, 2001.

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

8) Лифшиц А.Л. Статистическое моделирование СМО. М., 1978.

9) Вентцель Е.С. Исследование операций. М: Наука, 1980.

10) Вентцель Е.С., Овчаров Л.А. Теория вероятностей и её инженерные приложения. М: Наука, 1988.

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

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

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

Рис. 5.17

Количество возможных состояний ее бесконечно:

So - канал свободен, очереди нет, k = 0;

S - канал занят обслуживанием, очереди нет, k = 1; S 2 - канал занят, одна заявка в очереди, k = 2;

5/, - канал занят (k - 1), заявка в очереди.

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

Следует заметить, что для СМО с ограниченной длиной очереди в формуле

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

Поскольку в рассматриваемой СМО ограничение на длину очереди отсутствует, то любая заявка может быть обслужена, поэтому Pofc = 1, следовательно, относительная пропускная способность Q = р 0 б с = 1, соответственно р ОТК = О, а абсолютная пропускная способность А = XQ = X, L 0 ^ = р.

Вероятность пребывания в очереди k заявок равна

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

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

Среднее время ожидания обслуживания в очереди

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

Если в одноканальной СМО с ожиданием интенсивность поступления заявок больше интенсивности обслуживания, % > р, то очередь будет постоянно увеличиваться. В связи с этим наибольший интерес представляет анализ устойчивых СМО, работающих в стационарном режиме при X р, р
Пример 5.18. Булочная «Горячий хлеб» имеет одного контроле- ра-кассира. В течение часа приходят в среднем 54 покупателя. Средняя стоимость одной покупки составляет 7 руб. Среднее время обслуживания контролером-кассиром одного покупателя составляет 1 мин. Определим выручку от продажи, характеристики СМО и проведем анализ ее работы.

Решение

По условиям задачи п = 1; X = 54 ед/ч; р = 60 ед/ч, и поскольку р = Х/р = 0,9, то очередь нс будет расти бесконечно, следовательно, предельные вероятности существуют:

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

Вероятность того, что контролер-кассир занят работой,

Среднее число покупателей в очереди

Среднее время пребывания покупателя в булочной

Среднее число покупателей в булочной

Вероятность того, что в булочной находятся 1, 2, 3,4 человека, а следовательно, ожидают расчета в очереди у контролера-кассира 1, 2, 3 человека соответственно

Вероятность того, что ожидают расчета у контролера-кассира не более трех человек, равна

Доля времени простоя контролера-кассира составляет всего 10% от продолжительности рабочего дня, однако время ожидания обслуживания в очереди ощутимо - 9 мин, поэтому следует уменьшать время обслуживания t of -)C , введя дополнительный кассовый аппарат и соответственно контролера-кассира, иначе покупатели будут уходить в другое торговое предприятие, что приведет к ухудшению экономических показателей хозяйственной деятельности, в частности к уменьшению выручки от продажи хлеба и образованию остатков хлеба па следующий день и к потере его качества.

Пример 5.19. Интенсивность потока автомобилей на АЗС к колонке за бензином АИ-92 составляет 30 автомобилей в час, а среднее время заправки равно 5 мин. Проведем анализ работы системы массового обслуживания АЗС.

Решение

X = 30 ед/ч; = 5 мин = 1/12 ч.

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

Поскольку р > 1, то АЭС не будет работать в стационарном режиме и очередь будет постоянно увеличиваться, поэтому необходимо ввести еще одну колонку с бензином АИ-92 или уменьшить время обслуживания до величины ~ 1,9 мин, тогда

следовательно, р
Пример 5.20. В парикмахерской работает только один мужской мастер. Среднее время стрижки одного клиента составляет 20 мин. Клиенты в среднем приходят каждые 25 мин. Средняя стоимость стрижки составляет 60 руб. Как в первую смену с 9 до 15 ч, так и во вторую - с 15 до 21 ч работает один мастер. Провести анализ работы системы обслуживания.

Решение

п = 1; X = 2,4 клиента/ч; t Q fc = 20 мин = 1/3 ч.

Интенсивность нагрузки

Долю времени простоя мастера

Вероятность того, что мастер занят работой,

Среднее число клиентов в очереди

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

Среднее время пребывания клиентов в парикмахерской

Система работает вполне удовлетворительно. Поскольку р X = 4 клиента/ч, то интенсивность нагрузки составит р > 1 и очередь будет постоянно увеличиваться, что приведет к неустойчивому режиму работы СМО.

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

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

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

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

Канал занят, очереди нет;

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

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

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

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

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

Изображенная на рис. 5.8 схема представляет собой схему размножения и гибели. Используя общее решение (5.32)-(5.34), напишем выражения для предельных вероятностей состояний (см. также (5.40)):

или с использованием :

Последняя строка в (5.45) содержит геометрическую прогрессию с первым членом 1 и знаменателем р; откуда получаем:

в связи с чем предельные вероятности принимают вид:

Выражение (5.46) справедливо только при (при она дает неопределенность вида ). Сумма геометрической прогрессии со знаменателем равна , и в этом случае

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

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

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

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

Средняя длина очереди. Найдем среднее число заявок, находящихся в очереди, как математическое ожидание дискретной случайной величины - числа заявок, находящихся в очереди:

С вероятностью в очереди стоит одна заявка, с вероятностью - две заявки, вообще с вероятностью в очереди стоят заявок, и т. д., откуда:

Поскольку , сумму в (5.50) можно трактовать как производную по от суммы геометрической прогрессии:

Подставляя данное выражение в (5.50) и используя из (5.47), окончательно получаем:

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

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

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

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

если подставить сюда выражения для вероятностей (5.47), получим:

Здесь использованы соотношения (5.50), (5.51) (производная геометрической прогрессии), а также из (5.47). Сравнивая это выражение с (5.51), замечаем, что иначе говоря, среднее время ожидания равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.

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

Пример 5.6. Автозаправочная станция (АЗС) представляет собой СМО с одним каналом обслуживания (одной колонкой).

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

Определить:

вероятность отказа;

относительную и абсолютную пропускную способности АЗС;

среднее число машин, ожидающих заправки;

среднее число машин, находящихся на АЗС (включая обслуживаемую);

среднее время ожидания машины в очереди;

среднее время пребывания машины на АЗС (включая обслуживание).

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

Находим вначале приведенную интенсивность потока заявок:

По формулам (5.47):

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

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

Абсолютная пропускная способность СМО

Машины в мин.

Среднее число машин в очереди находим по формуле (5.51)

т. е. среднее число машин, ожидающих в очереди на заправку, равно 1,56.

Прибавляя к этой величине среднее число машин, находящихся под обслуживанием

получаем среднее число машин, связанных с АЗС.

Среднее время ожидания машины в очереди по формуле (5.54)

Прибавляя к этой величине , получим среднее время, которое машина проводит на АЗС:

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

Заметим, что при этом знаменатель в последней формуле (5.45) представляет собой сумму бесконечного числа членов геометрической прогрессии. Эта сумма сходится, когда прогрессия бесконечно убывающая, т. е. при .

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

Если , то соотношения (5.47) принимают вид:

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

Среднее число заявок в очереди получим из (5.51) при :

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

Среднее время ожидания получим из формулы

(5.53) при :

Наконец, среднее время пребывания заявки в СМО есть

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

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

Состояния системы нумеруются по числу заявок, связанных системой:

нет очереди:

Все каналы свободны;

Занят один канал, остальные свободны;

Заняты каналов, остальные нет;

Заняты все каналов, свободных нет;

есть очередь:

Заняты все n каналов; одна заявка стоит в очереди;

Заняты все n каналов, r заявок в очереди;

Заняты все n каналов, r заявок в очереди.

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

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

Граф типичен для процессов размножения и гибели, для которой решение ранее получено (5.29)-(5.33). Напишем выражения для предельных вероятностей состояний, используя обозначение : (здесь используется выражение для суммы геометрической прогрессии со знаменателем ).

Таким образом, все вероятности состояний найдены.

Определим характеристики эффективности системы.

Вероятность отказа. Поступившая заявка получает отказ, если заняты все каналов и все мест в очереди:

Относительная пропускная способность дополняет вероятность отказа до единицы:

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

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

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

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

Здесь опять (выражение в скобках) встречается производная суммы геометрической прогрессии (см. выше (5.50), (5.51)-(5.53)), используя соотношение для нее, получаем:

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

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

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

Так же, как и в случае одноканальной СМО с ожиданием, отметим, что это выражение отличается от выражения для средней длины очереди (5.59) только множителем , т. е.

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

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

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

Вероятности состояний получим из формул (5.56) предельным переходом (при ). Заметим, что сумма соответствующей геометрической прогрессии сходится при и расходится при . Допустив, что и устремив в формулах (5.56) величину m к бесконечности, получим выражения для предельных вероятностей состояний:

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

Среднее число заявок в очереди получим при из (5.59):

а среднее время ожидания - из (5.60):

Среднее число занятых каналов , как и ранее, определяется через абсолютную пропускную способность:

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

Пример 5.7. Автозаправочная станция с двумя колонками () обслуживает поток машин с интенсивностью (машин в минуту). Среднее время обслуживания одной машины

В данном районе нет другой АЗС, так что очередь машин перед АЗС может расти практически неограниченно. Найти характеристики СМО.

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

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

Вероятность отсутствия очереди у АЗС будет:

Среднее число машин в очереди:

Среднее число машин на АЗС:

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

Среднее время пребывания машины на АЗС:

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

Рассмотрим СМО подобного типа, предполагая, что ограничение времени ожидания является случайной величиной.

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

Граф состояний и переходов системы показан на рис. 5.10.

Рис. 5.10. СМО с ограниченным временем ожидания

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

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

Отметим некоторые особенности СМО с ограниченным ожиданием сравнительно с ранее рассмотренными СМО с «терпеливыми» заявками.

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

Напротив, в СМО с «нетерпеливыми» заявками, уходящими рано или поздно из очереди, установившийся режим обслуживания при достигается всегда, независимо от приведенной интенсивности потока заявок, не суммируя бесконечного ряда (5.63). Из (5.64) получаем:

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

В заключение заметим, что если в формулах (5.62) перейти к пределу при (или, что то же, при ), то при получатся формулы (5.61), т. е. «нетерпеливые» заявки станут «терпеливыми».

В систему поступает пуассоновский поток требований интенсивностью λ, поток обслуживания имеет интенсивность μ, максимальное число мест в очереди – т. Если заявка поступает в систему, когда все места в очереди заняты, она покидает систему необслуженной.
Финальные вероятности состояний такой системы всегда существуют, так как число состояний конечно:
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 одинаковых каналов поступает простейший поток заявок интенсивностью λ . Если в момент поступления заявки все каналы заняты, то эта заявка становится в очередь и ждет начала облуживания. Время обслуживания каждой заявки является случайной величиной, которая подчиняется экспоненциальному закону распределения с параметром μ .
Расчетные формулы
Вероятность того, что все каналы свободны

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

Вероятность того, что в системе находится k заявок, в случае, когда их число больше числа каналов,

Вероятность того, что все каналы заняты,

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

Средняя длина очереди

Среднее число свободных от обслуживания каналов
Пример
Автозаправочная станция с двумя колонками обслуживает пуассоновский поток машин с интенсивностью λ=0,8 машин в минуту. Время обслуживания одной машины подчиняется показательному закону со средним значением 2 минуты. В данном районе нет другой АЗС, так что очередь перед АЗС может расти практически неограниченно. Найдите:
1) среднее число занятых колонок;
2) вероятность отсутствия очереди у АЗС;
3) вероятность того, что придется ждать начала обслуживания;
4) среднее число машин в очереди;
5) среднее время ожидания в очереди;
6) среднее время пребывания машины на АЗС;
7) среднее число машин на АЗС.
Решение . По условию задачи n=2, λ=0.8; μ=1/t обсл =0.5; ρ=λ/μ=1.6
Поскольку ρ /n =0,8<1, то очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы системы массового обслуживания.
Находим вероятности состояний СМО:
Среднее число занятых колонок:
N зан =n-N 0 = 2-(2·p 0 +1·p 1) = 2-2·0.1111 - 0.1778 = 1.6
Вероятность отсутствия очереди у АЗС:

Вероятность того, что придется ждать начала обслуживания равна вероятности того, что все колонки заняты:
p 0 +p 1 +p 2 = 0.1111+0.1778+0.1422 = 0.4311
Среднее число машин в очереди:

Среднее время ожидания в очереди:
Среднее время пребывания машины на АЗС:
t преб =t обсл +t ож = 2+3.5556 = 5.5556 мин.
Среднее число машин на АЗС:
N зан +L оч = 1.6+2.8444 = 4.4444
Рассмотрим одноканальную СМО с ожиданиями, в которой число каналов равно единице n = 1, интенсивность поступления заявок – λ, интенсивность обслуживания равна μ. Заявка, поступившая в тот момент времени, когда канал занят, становится в очередь и ждет обслуживания. Количество мест в очереди ограничено и равно m . Если все места в очереди заняты, то заявка покидает очередь не обслуженной. Проанализируем состояние системы:
S 0 – канал свободен;
S 1 – канал занят;
S 2 – канал занят, одна заявка в очереди;
S k – канал занят, (k–1) заявок в очереди;
S m + 1 – канал занят, в очереди m заявок.

Изобразим граф состояний такой СМО (рис. 25).
Рис. 25
По формулам Эрланга найдем вероятности событий, состоящих в том, что СМО находится в состоянии S 1 , S 2 , …, S m+1:
(28)
При этом вероятность того, что заявка, прибывшая в систему, найдет ее свободной, равна
. (29)
Отношение интенсивности поступления заявок λ к интенсивности обслуживания заявок μ есть приведенная интенсивность μ, т.е.
ρ=λ/μ
Произведем замену в формулах (28) и (29) отношения λ/&mu на ρ, тогда выражения примут вид:
(30)
Вероятность Р 0 будет вычисляться по следующей формуле:
p 0 = -1 . (31)
Выражение для вероятности P 0 есть геометрическая прогрессия, сумма которой будет равна
.
Таким образом, формулы (30) и (31) позволяют определить вероятность любого события, которое может произойти в системе, т. е. определить вероятность нахождения системы в любом состоянии.
Формула для P 0 справедлива для случая, когда ρ ≠ 1 . В случае, когда ρ = 1 , т. е. интенсивность поступления заявок равна интенсивности их обслуживания, используется другая формула для вычисления вероятности того, что система свободна:
,
где m – это количество заявок, находящихся в очереди.
Определим характеристики эффективности одноканальной СМО :
вероятность того, что очередная заявка, прибывшая в систему, получит отказ Р отк;
абсолютную пропускную способность А ,
относительную пропускную способность Q ,
число занятых каналов k ,
среднее число заявок в очереди r ,
среднее число заявок, связанных с СМО, z .

Очередная заявка, поступившая в систему, получает отказ в том случае, когда занят канал, т. е. идет обслуживание другой заявки, и все m мест в очереди также заняты. тогда вероятность этого события можно вычислить по следующей формуле:
. (32)
Вероятность того, что заявка придет в систему и либо немедленно будет обслужена, либо будут места в очереди, т. е. относительную пропускную способность, можно найти по формуле
. (33)
Среднее число заявок, которые могут быть обслужены в единицу времени, т. е. абсолютную пропускную способность, рассчитывают следующим образом:
A=Q·λ (34)
Таким образом, по формулам (32), (33), (34) можно вычислить основные показатели эффективности для любой системы массового обслуживания. теперь выведем выражения для вычисления характеристик, присущих лишь данной СМО.
Среднее число заявок в очереди r определим как математическое ожидание дискретной случайной величины, где R – число заявок в очереди.
♦ Р 2 – это вероятность того, что в очереди на обслуживание находится одна заявка;
♦ Р 3 – вероятность того, что в очереди две заявки;
♦ Р k – вероятность того, что в очереди (k–1) заявка;
♦ Р m + 1 – вероятность того что в очереди m заявок.
Тогда среднее число заявок в очереди можно вычислить следующим образом:
r =1·P 2 +2·P 3 + ... +(k-1)·P k + ... +m·P m+1 . (35)
Подставим в формулу (35) найденные ранее значения вероятностей, вычисленные в формуле (30):
r =1·ρ 2 ·p 0 +2·ρ 3 ·p 0 + ... +(k-1)·ρ k ·p 0 + ... +m·ρ m+1 ·p 0 . (35)
Вынесем за скобку вероятность P 0 и Р 2 , тогда получим итоговую формулу для вычисления среднего числа заявок в очереди на обслуживание:
r =ρ 2 ·p 0 (1+2·ρ+ ... +(k-1)·ρ k-2 + ... +m·ρ m-1)
Выведем формулу для среднего числа заявок, связанных с СМО, z , т. е. число заявок в очереди, находящихся на обслуживании. Рассмотрим общее число заявок, связанных с СМО, z как сумму двух величин среднего числа заявок в очереди r и числа занятых каналов k :
z = r +k .
Так как канал один, то число занятых каналов k может принимать значения 0 или 1. Вероятность того, что k = 0, т.е. система свободна, соответствует вероятности Р 0 , значение которой можно найти по формуле (31). Если k = 1, т.е. канал занят обслуживанием заявки, но места в очереди еще есть, то вероятность этого события можно вычислить по формуле
.
Следовательно, z будет равно:
. (37)
Одноканальная СМО с ожиданием
Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание - простейший поток с интенсивностью l. Интенсивность потока обслуживания равна m (т. е. в среднем непрерывно занятый канал будет выдавать m. обслуженных заявок). Длительность обслуживания - случайная величина, подчиненная показательному закону распределения. Поток обслуживании является простейшим пуассоновским потоком событий. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.
Предположим, что независимо от того, сколько требований поступает на вход обслуживающей системы, данная система (очередь + обслуживаемые клиенты) не может вместить более N-требований (заявок), т. е. клиенты, не попавшие в ожидание, вынуждены обслуживаться в другом месте. Наконец, источник, порождающий заявки на обслуживание, имеет неограниченную (бесконечно большую) емкость.
Граф состояний СМО в этом случае имеет вид, показанный на Рис. 3.2.

Граф состояний одноканальной СМО с ожиданием (схема гибели и размножения)
Состояния СМО имеют следующую интерпретацию:
S 0 - канал свободен
S 1 - канал занят (очереди нет);
S 2 - канал занят (одна заявка стоит в очереди);
………………………………
S n - канал занят (n - 1 заявок стоит в очереди);
……………………………
S N - канал занят (N - 1 заявок стоит в очереди).
Стационарный провес в данной системе будет описываться следующей системой алгебраических уравнений :

п - номер состояния.
Решение приведенной выше системы уравнений (3.10) для нашей модели СМО имеет вид

Следует отметить, что выполнение условия стационарности для данной СМО необязательно, поскольку число допускаемых в обслуживающую систему заявок контролируется путем введения ограничения на длину очереди (которая не может превышать N - 1), а не соотношением между интенсивностями входного потока, т. е. не отношением
l/m = p
Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N - 1):

Рассмотрим пример одноканальной СМО с ожиданием.
Пример 3.2. Специализированный пост диагностики представляет собой одноканальную СМО. Число стоянок для автомобилей, ожидающих проведения диагностики, ограничено и равно 3 [(N - 1) = 3]. Если все стоянки заняты, т. е. в очереди уже находится три автомобиля, то очередной автомобиль, прибывший на диагностику, в очередь на обслуживание не становится. Поток автомобилей, прибывающих на диагностику, распределен по закону Пуассона и имеет интенсивность l = 0,85 (автомобиля в час). Время диагностики автомобиля распределено по показательному закону и в среднем равно 1,05 час.
Требуется определить вероятностные характеристики поста диагностики, работающего в стационарном режиме.
Решение
1. Параметр потока обслуживании автомобилей:

2. Приведенная интенсивность потока автомобилей определяется как отношение интенсивностей l и m, т. е.

3. Вычислим финальные вероятности системы:

P 1 =ρ·P 0 = 0.893·0.248 = 0.221
P 2 =ρ 2 ·P 0 = 0.893 2 ·0.248 = 0.198
P 3 =ρ 3 ·P 0 = 0.893 3 ·0.248 = 0.177
P 4 =ρ 4 ·P 0 = 0.893 2 ·0.248 = 0.158
4. Вероятность отказа в обслуживании автомобиля:
P отк =P 4 =ρ 4 ·P 0 ≈ 0.158
5. Относительная пропускная способность поста диагностики:
q=1-P отк = 1-0.158 = 0.842
6. Абсолютная пропускная способность поста диагностики
A=λ·q = 0.85·0.842 = 0.716 (автомобиля в час)
7. Среднее число автомобилей, находящихся на обслуживании и в очереди (т.е. в системе массового обслуживания):

8. Среднее время пребывания автомобиля в системе:
9. Средняя продолжительность пребывания заявки в очереди на обслуживание:
W q =W S -1/μ = 2.473-1/0.952 = 1.423 часа
10. Среднее число заявок в очереди (длина очереди): L q = А,(1 - P N) W q = 0,85
L q =λ(1-P N)·W q = 0.85·(1-0.158)·1.423 = 1.02
Работу рассмотренного поста диагностики можно считать удовлетворительной, так как пост диагностики не обслуживает автомобили в среднем в 15,8% случаев (Р отк = 0,158). В качестве показателей эффективности СМО с ожиданием, кроме уже известных показателей - абсолютной А и относительной Q пропускной способности, вероятности отказа P отк. , среднего числа занятых каналов (для многоканальной системы) будем рассматривать также следующие: L сист. - среднее число заявок системе; Т сист. - среднее время пребывания заявки в системе; L оч. - среднее число заявок в очереди (длина очереди); Т оч. - среднее время пребывания заявки в очереди; Р зан.. - вероятность того, что канал занят (степень загрузки канала).
Одноканальная система с неограниченной очередью
На практике часто встречаются одноканальные СМО с неограниченной очередью (например, телефон-автомат с одной будкой).
Рассмотрим задачу.
Имеется одноканальная СМО с очередью, на которую не наложены никакие ограничения (ни по длине очереди, ни по времени ожидания). Поток заявок, поступающих в СМО, имеет интенсивность λ, а поток обслуживании - интенсивность μ. Необходимо найти предельные вероятности состояний и показатели эффективности СМО.
Система может находиться в одном из состояний 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), сходится к сумме, равной . Поэтому
p 0 =1-ρ, (33)
и с учетом соотношений (17)
p 1 =ρ·p 0 ; p 2 =ρ 2 ·p 0 ; ... ; p k =ρ k ·p 0 ; ...
найдем предельные вероятности других состояний
p 1 =ρ·(1-ρ); p 2 =ρ 2 ·(1-ρ); ... ; p k =ρ k ·(1-ρ); ... (34)
Предельные вероятности p 0 , p 1 , p 2 , …, p k ,… образуют убывающую геометрическую профессию со знаменателем р < 1, следовательно, вероятность р 0 - наибольшая. Это означает, что если СМО справляется с потоком заявок (при ρ < 1), то наиболее вероятным будет отсутствие заявок в системе.
Среднее число заявок в системе L сист. определим по формуле математического ожидания, которая с учетом (34) примет вид
(35)
(суммирование от 1 до ∞, так как нулевой член 0·p 0 =0).
Можно показать, что формула (35) преобразуется (при ρ < 1) к виду
(36)
Найдем среднее число заявок в очереди L оч. Очевидно, что
L оч =L сист -L об (37)
где L об. - среднее число заявок, находящихся под обслуживанием.
Среднее число заявок под обслуживанием определим по формуле математического ожидания числа заявок под обслуживанием, принимающего значения 0 (если канал свободен) либо 1 (если канал занят):
L оч =0·p 0 +1·(1-p 0)
т.е. среднее число заявок под обслуживанием равно вероятности того, что канал занят:
L оч =P зан =1-p 0 , (38)
В силу (33)
L оч =P зан ρ, (39)
Теперь по формуле (37) с учетом (36) и (39)
(40)
Доказано, что при любом характере потока заявок, при любом распределении времени обслуживания, при любой дисциплине обслуживания среднее время пребывания заявки в системе (очереди) равна среднему числу заявок в системе (в очереди), деленному на интенсивность потока заявок, т.е.
(41)
(42)
Формулы (41) и (42) называются формулами Литтла. Они вытекают из того, что в предельном, стационарном режиме среднее число заявок, прибывающих в систему, равно среднему числу заявок, покидающих ее: оба потока заявок имеют одну и ту же интенсивность λ.
На основании формул (41) и (42) с учетом (36) и (40) среднее время пребывания заявки в системе определится по формуле:
(43)
а среднее время пребывания заявки в очереди
(44)
Одноканальная СМО с ожиданием без ограничения на вместимость блока ожидания
Стационарный режим функционирования данной СМО существует при t→∞ для любого п=0,1,2,… и когда l < m.Система алгебраических уравнений, описывающих работу СМО при t®¥ для любого n = 0, 1, 2...., имеет вид
Решение данной системы уравнений имеет вид
P n =(1-ρ)·ρ n , n=0,1,2,... (3.21)
где ρ=λ/μ < 1
Характеристики одноканальной СМО с ожиданием, без ограничения на длину очереди, следующие:
среднее число находящихся в системе клиентов (заявок) на обслуживание:
средняя продолжительность пребывания клиента в системе:

Пример 3.3. Вспомним о ситуации, рассмотренной в пример 3.2, где речь идет о функционировании поста диагностики. Пусть рассматриваемый пост диагностики располагает неограниченны» количеством площадок для стоянки прибывающих на обслуживание автомобилей, т. е. длина очереди не ограничена.
Требуется определить финальные значения следующих вероятностных характеристик:
вероятности состояний системы (поста диагностики);
среднее число автомобилей, находящихся в системе (на обслуживании и в очереди);
среднюю продолжительность пребывания автомобиля в системе (на обслуживании и в очереди);
среднее число автомобилей в очереди на обслуживании;
среднюю продолжительность пребывания автомобиля в очереди.

Решение
1. Параметр потока обслуживания m и приведенная интенсивность потока автомобилей р определены в примере 3.2:
m = 0,952; p = 0,893.
2. Вычислим предельные вероятности системы по формулам
P 0 =1-ρ = 1-0.893 = 0.107
P 1 =(1-ρ)·ρ = (1-0.893)·0.893 = 0.096
P 2 =(1-ρ)·ρ 2 = (1-0.893) 2 ·0.893 = 0.085
P 3 =(1-ρ)·ρ 3 = (1-0.893) 3 ·0.893 = 0.076
P 4 =(1-ρ)·ρ 4 = (1-0.893) 4 ·0.893 = 0.068
P 5 =(1-ρ)·ρ 5 = (1-0.893) 5 ·0.893 = 0.061
и т.д.
Следует отметить, что Р о определяет долю времени, в течение которого пост диагностики вынужденно бездействует (простаивает). В нашем примере она составляет 10,7%, так как Р о = 0,107.
3. Среднее число автомобилей, находящихся в системе (на обслуживании и в очереди):
4. Средняя продолжительность пребывания клиента в системе:

6. Средняя продолжительность пребывания автомобиля в очереди-
7. Относительная пропускная способность системы:
т. е. каждая заявка, пришедшая в систему, будет обслужена.
8. Абсолютная пропускная способность: А = lq = 0,85·1 = 0,85
Следует отметить, что предприятие, осуществляющее диагностику автомобилей, прежде всего интересует количество клиентов, которое посетит пост диагностики при снятии ограничения на длину очереди.
Допустим, в первоначальном варианте количество мест для стоянки прибывающих автомобилей было равно трем (см. пример 3.2). Частота m возникновения ситуаций, когда прибывающий на пост диагностики автомобиль не имеет возможности присоединиться к очереди:
т = l P N
В нашем примере при N = 3 + 1 = 4 и р = 0,893,
m = l Р о р 4 = 0,85·0,248·0,8934·0,134 автомобиля в час.
При 12-часовом режиме работы поста диагностики это эквивалентно тому, что пост диагностики в среднем за смену (день) будет терять 12·0,134 = 1,6 автомобиля.
Снятие ограничения на длину очереди позволяет увеличить количество обслуженных клиентов в нашем примере в среднем на 1,6 автомобиля за смену (12 ч. работы) поста диагностики. Ясно, что решение относительно расширения площади для стоянки автомобилей, прибывающих на пост диагностики, должно основываться на оценке экономического ущерба, который обусловлен потерей клиентов при наличии всего трех мест для стоянки этих автомобилей.
Многоканальная СМО с неограниченной очередью
Рассмотрим задачу. Имеется 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.
среднее число заявок в очереди
, (50)
среднее число заявок в системе
L сист =L оч +ρ, (51)
Среднее время пребывания заявки в очереди и среднее время пребывания заявки в системе, как и ранее, находятся по формулам Литтла (42) и (41).
Замечание. Для СМО с неограниченной очередью при r < 1 любая заявка, пришедшая в систему, будет обслужена, т.е. вероятность отказа P отк = 0, относительная пропускная способность Q =1, а абсолютная пропускная способность равна интенсивности входящего потока заявок, т.е. А =l.
СМО с ограниченной очередью
СМО с ограниченной очередью. СМО с ограниченной очередью отличаются от рассмотренных выше задач лишь тем, что число заявок в очереди ограничено (не может превосходить некоторого заданного т). Если новая заявка поступает в момент, когда все места в очереди заняты, она покидает СМО необслуженной, т.е. получает отказ.
Очевидно: для вычисления предельных вероятностей состояний и показателей эффективности таких СМО может быть использован тот же подход, что и выше, с той разницей, что суммировать надо не бесконечную прогрессию (как, например, мы делали при выводе формулы (33)), а конечную.
Среднее время пребывания заявки в очереди и в системе, как и ранее, определяем по формулам Литтла (44) и (43).
СМО с ограниченным временем ожидания. На практике часто встречаются СМО с так называемыми "нетерпеливыми" заявками. Такие заявки могут уйти из очереди, если время ожидания превышает некоторую величину. В частности, такого рода заявки возникают в различных технологических системах, в которых задержка с началом обслуживания может привести к потере качества продукции, в системах оперативного управления, когда срочные сообщения теряют ценность (или даже смысл), если они не поступают на обслуживание в течение определенного времени.
В простейших математических моделях таких систем предполагается, что заявка может находиться в очереди случайное время, распределенное по показательному закону с некоторым параметром υ, т.е. можно условно считать, что каждая заявка, стоящая в очереди на обслуживание, может покинуть систему с интенсивностью υ.
Соответствующие показатели эффективности СМО с ограниченным временем получаются на базе результатов, полученных для процесса гибели и размножения.
В заключение отметим, что на практике часто встречаются замкнутые системы обслуживания , у которых входящий поток заявок существенным образом зависит от состояния самой СМО. В качестве примера можно привести ситуацию, когда на ремонтную базу поступают с мест эксплуатации некоторые машины: понятно, что чем больше машин находится в состоянии ремонта, тем меньше их продолжает эксплуатироваться и тем меньше интенсивность потока вновь поступающих на ремонт машин. Для замкнутых СМО характерным является ограниченное число источников заявок, причем каждый источник "блокируется" на время обслуживания его заявки (т.е. он не выдает новых заявок). В подобных системах при конечном числе состояний СМО предельные вероятности будут существовать при любых значениях интенсивностей потоков заявок и обслуживании. Они могут быть вычислены, если вновь обратиться к процессу гибели и размножения.