Одноканальные и многоканальные смо с неограниченной очередью. Одноканальная смо с ожиданием. по дисциплине «Математические методы»

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

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

L СИСТ – среднее число заявок в систем;

W СИСТ – среднее время пребывания заявки в системе;

L ОЧ – среднее число заявок в очереди;

W ОЧ – среднее время пребывания заявки в очереди;

P ЗАН - вероятность того, что канал занят (степень загрузки канала).

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

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

- S 0 – канал свободен;

- S 1 – канал занят (обслуживает заявку), очереди нет;

- S 2 – канал занят, одна заявка стоит в очереди;

- S k – канал занят, k-1 заявок стоят в очереди.

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

Ряд в формуле (17) представляет собой геометрическую прогрессию. Мы знаем, что при ряд сходится – это бесконечно убывающая прогрессия со знаменателем r. При ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний p о , p 1 , …, p k ,… существуют только при ). Тогда:

Найдем среднее число заявок в СМО L СИСТ . Случайная величина Z – число заявок в системе – имеет возможные значения 0, 1, 2, …, k, … с вероятностями p о , p 1 , …, p k ,… Ее математическое ожидание равно:

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

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

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

По формуле Литтла (9) найдем среднее время пребывания заявки в очереди.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение

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

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

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

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

Решение

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

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

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

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

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

В примере .

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

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

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

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

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

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

Решение

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

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

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

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

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

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

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

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

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

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

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

Размеченный граф состояний такой системы приведен на рис. 3.5

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

Канал свободен, очереди нет, ;

Канал занят обслуживанием, очереди нет, ;

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

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

Рис. 3.5

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

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

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

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

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

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

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

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

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

В коммерческой деятельности чаще встречаются СМО с ожиданием (очередью).

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

Граф этой СМО представлен на рис. 3.4 и совпадает с графом рис. 2.1 описывающим процесс «рождения--гибели», с тем отличием, что при наличии только одного канала.

Размеченный граф процесса «рождения - гибели» обслуживания все интенсивности потоков обслуживания равны

Состояния СМО можно представить следующим образом:

S0 - канал обслуживания свободен,

S, - канал обслуживания занят, но очереди нет,

S2- канал обслуживания занят, в очереди стоит одна заявка,

S3- канал обслуживания занят, в очереди стоят две заявки,

Sm+1 - канал обслуживания занят, в очереди все т мест заняты, любая следующая заявка получает отказ.

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

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

с= (1- с)

Эта формула справедлива для всех р, отличных от 1, если же р = 1, то р0 = 1/(т + 2), а все остальные вероятности также равны 1/(т + 2).

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

Действительно, выражение для предельной вероятности р0в случае т = 0 имеет вид:

pо = м / (л+м)

И в случае л =м имеет величину р0= 1 / 2.

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

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

Поэтому вероятность отказа определяется вероятностью появлением

Состояния Sm+1:

Pотк = pm+1 = сm+1 * p0

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

Q = 1- pотк = 1- сm+1 * p0

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

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

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

• 1 - в очереди стоит одна заявка,
• 2 - в очереди две заявки,

т-в очереди все места заняты

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

Таблица 1. Закон распределения дискретной случайной величины

Математическое ожидание этой случайной величины равно:

Lоч = 1* p2 +2* p3 +...+ m* pm+1

В общем случае при p ?1 эту сумму можно преобразовать, пользуясь моделями геометрической прогрессии, к более удобному виду:

Lоч = p2 * 1- pm * (m-m*p+1) * p0

В частном случае при р = 1, когда все вероятности pkоказываются равными, можно воспользоваться выражением для суммы членов числового ряда

1+2+3+ m = m(m+1)

Тогда получим формулу

L"оч= m(m+1) * p0 = m(m+1) (p=1).

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

Точ = Lоч/А (при р? 1) и Т1оч= L"оч /А(при р = 1).

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

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

Если отказаться от ограничения на длину очереди, т.е. устремить m--> >?, то случаи р < 1 и р?1 начинают существенно различаться. Записанные выше формулы для вероятностей состояний преобразуются в случае р < 1 к виду

При достаточно большом к вероятностьpk стремится к нулю. Поэтому относительная пропускная способность будет Q= 1, а абсолютная пропускная способность станет равной А --л Q -- л следовательно, обслуживаются все поступившие заявки, причем средняя длина очереди окажется равной:

Lоч =p2 1-p

а среднее время ожидания по формуле Литтла

Точ = Lоч/А

В пределе р << 1 получаем Точ = с / м т.е. среднее время ожидания быстро уменьшается с увеличением интенсивности потока обслуживания. В противном случае при р? 1 оказывается, что в СМО отсутствует установившийся режим. Обслуживание не успевает за потоком заявок, и очередь неограниченно растет со временем (при t > ?). Предельные вероятности состояний поэтому не могут быть определены: при Q= 1 они равны нулю. Фактически СМО не выполняет своих функций, поскольку она не в состоянии обслужить все поступающие заявки.

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

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

Lсмо= m+1 ;2

Тсмо= Lсмо; при p ?1

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

Тсмо= m+1 при p ?1 2м

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

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

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

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

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

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

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

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

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

S0 - канал свободен,

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

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

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

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

Рис. 4.11. Граф состояний СМО в виде схемы гибели и размножения с бесконечным числом состояний

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

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

Вероятности р1, р2, ..., рk, ... найдутся по формулам:

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

p 1 = ρ(1 - ρ), = ρ2(1- ρ), . . ., pk = ρ4(1- ρ), . . . (4.39)

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

Найдем среднее число заявок в СМО Lсист. Случайная величина Z - число заявок в системе - имеет возможные значения 0, 1, 2, ..., k, ... с вероятностями р0, р1, p2, ..., рk, ... Ее математическое ожидание равно

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

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

Теперь вынесем за знак суммы р (1 - р):

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

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

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

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

и окончательно

Таким образом, все характеристики эффективности СМО найдены.

Предложим читателю самостоятельно решить пример: одноканальная СМО представляет собой железнодорожную сортировочную станцию, на которую поступает простейший поток составов с интенсивностью λ = 2 (состава в час). Обслуживание (расформирование) состава длится случайное (показательное) время со средним значением tоб = 20 (мин.). В парке прибытия станции имеются два пути, на которых могут ожидать обслуживания прибывающие составы; если оба пути заняты, составы вынуждены ждать на внешних путях. Требуется найти (для предельного, стационарного режима работы станции): среднее число составов Lсист, связанных со станцией, среднее время Wсист пребывания состава при станции (на внутренних путях, на внешних путях и под обслуживанием), среднее число Lоч составов, ожидающих очереди на расформирование (все равно, на каких путях), среднее время Wоч пребывания состава на очереди. Кроме того, попытайтесь найти среднее число составов, ожидающих расформирования на внешних путях Lвнеш и среднее время этого ожидания Wвнеш (две последние величины связаны формулой Литтла). Наконец, найдите суммарный суточный штраф Ш, который придется заплатить станции за простои составов на внешних путях, если за один час простоя одного состава станция платит штраф а (руб.). На всякий случай сообщаем ответы: Lcист = 2 (состава), Wсист = i (час), Lоч = 4/3 (состава), Wоч = 2/3 (часа), Lвнеш = 16/27 (состава), Wвнеш = 8/27 ≈ 0,297 (часа). Средний суточный штраф Ш за ожидание составов на внешних путях получим, перемножая среднее число составов, прибывающих на станцию за сутки, среднее время ожидания состава на внешних путях и часовой штраф а: Ш ≈ 14,2а.