Главная > Математика > Исследование операций: задачи, принципы, методология
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 20. Простейшие системы массового обслуживания и их характеристики

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

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

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

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

1. n-канальная СМО с отказами (задача Эрланга).

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

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

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

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

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

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

— в СМО нет ни одной заявки,

— в СМО находится одна заявка (один канал занят, остальные свободны),

— в СМО находится к заявок каналов заняты, остальные свободны),

— в СМО находится заявок (все каналов заняты).

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

Рис. 20.1.,

Тот же поток заявок переводит систему из любого левого состояния в соседнее, правое (см. верхние стрелки на рис. 20.1).

Проставим интенсивности у нижних стрелок. Пусть система находится в состоянии (работает один канал). Он производит обслуживании в единицу времени. Проставляем у стрелки интенсивность Теперь представим себе, что система находится в состоянии (работают два канала). Чтобы ей перейти в нужно, чтобы либо закончил обслуживание первый канал, либо второй; суммарная интенсивность их потоков обслуживаний равна проставляем ее у соответствующей стрелки. Суммарный поток обслуживаний, даваемый тремя каналами, имеет интенсивность к каналами — Проставляем эти интенсивности у нижних стрелок на рис. 20.1.

А теперь, зная все интенсивности, воспользуемся уже готовыми формулами (19.7), (19.8) для финальных вероятностей в схеме гибели и размножения. По формуле (19.8) получим:

Члены разложения будут представлять собой коэффициенты при в выражениях для

Заметим, что в формулы (20.1), (20.2) интенсивности Яиц входят не по отдельности, а только в виде отношения Обозначим

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

Формулы (20.4), (20.5) для финальных вероятностей состояний называются формулами Эрланга — в честь основателя теории массового обслуживания. Большинство других формул этой теории (сегодня их больше, чем грибов в лесу) не носит никаких специальных имен.

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

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

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

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

Подставляя сюда выражения (20.5) для и выполняя соответствующие преобразования, мы, в конце концов, получили бы верную формулу для к. Но мы выведем ее гораздо проще (вот она, одна из «маленьких хитростей»!) В самом деле, нам известна абсолютная пропускная способность А. Это — не что иное, как интенсивность потока обслуженных системой заявок. Каждый занятый канал в единицу времени обслуживает в среднем заявок. Значит, среднее число занятых каналов равно

или, учитывая (20.8),

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

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

И какая доля каналов при этом будет простаивать?

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

<< Предыдущий параграф Следующий параграф >>
Оглавление