Примеры решения задач систем массового обслуживания
Требуется решить задачи 1–3. Исходные данные приведены в табл. 2–4.
Некоторые обозначения, применяемые в теории массового обслуживания, для формул:
n – число каналов в СМО;
λ – интенсивность входящего потока заявок П вх;
v – интенсивность выходящего потока заявок П вых;
μ – интенсивность потока обслуживания П об;
ρ – показатель нагрузки системы (трафик);
m – максимальное число мест в очереди, ограничивающее длину очереди заявок;
i – число источников заявок;
p к – вероятность k-го состояния системы;
p о – вероятность простаивания всей системы, т. е. вероятность того, что все каналы свободны;
p сист – вероятность принятия заявки в систему;
p отк – вероятность отказа заявке в принятии ее в систему;
р об – вероятность того, что заявка будет обслужена;
А – абсолютная пропускная способность системы;
Q – относительная пропускная способность системы;
оч – среднее число заявок в очереди;
об – среднее число заявок под обслуживанием;
сист – среднее число заявок в системе;
оч – среднее время ожидания заявки в очереди;
об – среднее время обслуживания заявки, относящееся только к обслуженным заявкам;
сис – среднее время пребывания заявки в системе;
ож – среднее время, ограничивающее ожидание заявки в очереди;
– среднее число занятых каналов.
Абсолютная пропускная способность СМО А – среднее число заявок, ĸᴏᴛᴏᴩᴏᴇ может обслужить система за единицу времени.
Относительная пропускная способность СМО Q – отношение среднего числа заявок, обслуживаемых системой в единицу времени, к среднему числу поступающих за это время заявок.
При решении задач массового обслуживания крайне важно придерживаться нижеприведенной последовательности:
1) определение типа СМО по табл. 4.1;
2) выбор формул в соответствии с типом СМО;
3) решение задачи;
4) формулирование выводов по задаче.
1.Схема гибели и размножения. Мы знаем, что, имея в распоряжении размеченный граф состояний, можно легко написать уравнения Колмогорова для вероятностей состояний, а также написать и решить алгебраические уравнения для финальных вероятностей. Стоит сказать, что для некоторых случаев удается последние уравнения
решить заранее, в буквенном виде. В частности, это удается сделать, в случае если граф состояний системы представляет собой так называемую ʼʼсхему гибели и размноженияʼʼ.
Граф состояний для схемы гибели и размножения имеет вид, показанный на рис. 19.1. Особенность этого графа в том, что все состояния системы можно вытянуть в одну цепочку, в которой каждое из средних состояний (S 1 , S 2 ,…,S n-1) связано прямой и обратной стрелкой с каждым из соседних состояний - правым и левым, а крайние состояния (S 0 , S n) - только с одним соседним состоянием. Термин ʼʼсхема гибели и размноженияʼʼ ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции.
Схема гибели и размножения очень часто встречается в разных задачах практики, в частности - в теории массового обслуживания, в связи с этим полезно, один раз и навсегда, найти для нее финальные вероятности состояний.
Предположим, что все потоки событии, переводящие систему по стрелкам графа,- простейшие (для краткости будем называть и систему S и протекающий в ней процесс - простейшими).
Пользуясь графом рис. 19.1, составим и решим алгебраические уравнения для финальных вероятностей состоянии), существование вытекает из того, что из каждого состояния можно перейти в каждое другое, в число состояний конечно). Для первого состояния S 0 имеем:
(19.1)
Для второго состояния S 1:
В силу (19.1) последнее равенство приводится к виду
где k принимает все значения от 0 до п. Итак, финальные вероятности p 0 , p 1 , ..., р n удовлетворяют уравнениям
(19.2)
кроме того, нужно учесть нормировочное условие
p 0 + p 1 + p 2 +…+ p n =1. (19.3)
Решим эту систему уравнений. Из первого уравнения (19.2)выразим p 1 через р 0 :
p 1 = p 0. (19.4)
Из второго, с учетом (19.4), получим:
(19.5)
‣‣‣ из третьего, с учетом (19.5),
(19.6)
и вообще, для любого k (от 1 до n ):
(19.7)
Обратим внимание на формулу (19.7). В числителе стоит произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо (с начала и до данного состояния S k), а в знаменателе - произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево (с начала и до S k).
Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, все вероятности состояний р 0 , p 1 , ..., р n выражены через одну из них (р 0). Подставим эти выражения в нормировочное условие (19.3). Получим, вынося за скобку р 0:
отсюда получим выражение для р 0 :
(скобку мы возвели в степень -1, чтобы не писать двухэтажных дробей). Все остальные вероятности выражены через р 0 (см. формулы (19.4) - (19.7)). Заметим, что коэффициенты при р 0 в каждой из них представляют из себяне что иное, как последовательные члены ряда, стоящего после единицы в формуле (19.8). Значит, вычисляя р 0 , мы уже нашли все эти коэффициенты.
Полученные формулы очень полезны при решении простейших задач теории массового обслуживания.
^ 2. Формула Литтла. Теперь мы выведем одну важную формулу, связывающую (для предельного, стационарного режима) среднее число заявок L сист, находящихся в системе массового обслуживания (т. е. обслуживаемых или стоящих в очереди), и среднее время пребывания заявки в системе W сист.
Рассмотрим любую СМО (одноканальную, многоканальную, марковскую, немарковскую, с неограниченной или с ограниченной очередью) и связанные с нею два потока событий: поток заявок, прибывающих в СМО, и поток заявок, покидающих СМО. В случае если в системе установился предельный, стационарный режим, то среднее число заявок, прибывающих в СМО за единицу времени, равно среднему числу заявок, покидающих ее: оба потока имеют одну и ту же интенсивность λ.
Обозначим: X(t} - число заявок, прибывших в СМО до момента t. Y (t ) - число заявок покинувших СМО
до момента t. И та͵ и другая функции являются случайными и меняются скачком (увеличиваются на единицу) в моменты приходов заявок (X (t )) и уходов заявок (Y(t)). Вид функций X(t) и Y(t) показан на рис. 19.2; обе линии - ступенчатые, верхняя - X(t), нижняя-Y(t). Очевидно, что для любого момента t их разность Z (t ) = X(t) - Y(t) есть не что иное, как число заявок, находящихся в СМО. Когда линии X(t) и Y(t) сливаются, в системе нет заявок.
Рассмотрим очень большой промежуток времени Т (мысленно продолжив график далеко за пределы чертежа) и вычислим для него среднее число заявок, находящихся в СМО. Оно будет равно интегралу от функции Z(t) на этом промежутке, деленному на длину интервала Т:
L сист. = . (19.9) о
Но данный интеграл представляет собой не что иное, как площадь фигуры, заштрихованной на рис. 19.2. Разглядим хорошенько данный рисунок. Фигура состоит из прямоугольников, каждый из которых имеет высоту, равную единице, и основание, равное времени пребывания в системе соответствующей заявки (первой, второй и т. д.). Обозначим эти времена t 1 , t 2 ,... Правда, под конец промежутка Т некоторые прямоугольники войдут в заштрихованную фигуру не полностью, а частично, но при достаточно большом Т эти мелочи не будут играть роли. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, можно считать, что
(19.10)
где сумма распространяется на все заявки, пришедшие за время Т.
Разделим правую и левую часть (.19.10) на длину интервала Т. Получим, с учетом (19.9),
L сист. = . (19.11)
Разделим и умножим правую часть (19.11) на интенсивность X:
L сист. = .
Но величина Тλ есть не что иное, как среднее число заявок, пришедших за время ^ Т. В случае если мы разделим сумму всех времен t i на среднее число заявок, то получим среднее время пребывания заявки в системе W сист. Итак,
L сист. = λW сист. ,
W сист. = . (19.12)
Это и есть замечательная формула Литтла: для любой СМО, при любом характере потока заявок, при любом распределении времени обслуживания, при любой дисциплине обслуживания среднее время пребывания заявки в системе равно среднему числу заявок в системе, деленному на интенсивность потока заявок.
Точно таким же образом выводится вторая формула Литтла, связывающая среднее время пребывания заявки в очереди ^ W оч и среднее число заявок в очереди L оч:
W оч = . (19.13)
Для вывода достаточно вместо нижней линии на рис. 19.2 взять функцию U(t) - количество заявок, ушедших до момента t не из системы, а из очереди (если заявка, пришедшая в систему, не становится в очередь, а сразу идет под обслуживание, можно все же считать, что она становится в очередь, но находится в ней нулевое время).
Формулы Литтла (19.12) и (19.13) играют большую роль в теории массового обслуживания. К сожалению, в большинстве существующих руководств эти формулы (доказанные в общем виде сравнительно недавно) не приводятся 1).
§ 20. Простейшие системы массового обслуживания и их характеристики
В этом параграфе мы рассмотрим, некоторые простейшие СМО и выведем выражения для их характеристик (показателей эффективности). При этом мы продемонстрируем основные методические приемы, характерные для элементарной, ʼʼмарковскойʼʼ теории массового обслуживания. Мы не будем гнаться за количеством образцов СМО, для которых будут выведены конечные выражения характеристик; данная книга - не справочник по теории массового обслуживания (такую роль гораздо лучше выполняют специальные руководства). Наша цель - познакомить читателя с некоторыми ʼʼмаленькими хитростямиʼʼ, облегчающими путь сквозь теорию массового обслуживания, которая в ряде имеющихся (даже претендующих на популярность) книг может показаться бессвязным набором примеров.
Все потоки событий, переводящие СМО из состояния в состояние, в данном параграфе мы будем считать простейшими (не оговаривая это каждый раз специально). В их числе будет и так называемый ʼʼпоток обслуживанииʼʼ. Под ним разумеется поток заявок, обслуживаемых одним непрерывно занятым каналом. В этом потоке интервал между событиями, как и всегда в простейшем потоке, имеет показательное распределение (во многих руководствах вместо этого говорят: ʼʼвремя обслуживания - показательноеʼʼ, мы и сами в дальнейшем будем пользоваться таким термином).
1) В популярной книжке дан несколько иной, по сравнению с вышеизложенным, вывод формулы Литтла. Вообще, знакомство с этой книжкой (ʼʼБеседа втораяʼʼ) полезно для первоначального ознакомления с теорией массового обслуживания.
В данном параграфе показательное распределение времени обслуживания будет само собой разуметься, как всегда для ʼʼпростейшейʼʼ системы.
Характеристики эффективности рассматриваемых СМО мы будем вводить по ходу изложения.
^ 1. п -канальная СМО с отказами (задача Эрланга). Здесь мы рассмотрим одну из первых по времени, ʼʼклассическихʼʼ задач теории массового обслуживания;
эта задача возникла из практических нужд телефонии и была решена в начале нашего века датским математиком Эрлантом. Задача ставится так: имеется п каналов (линий связи), на которые поступает поток заявок с интенсивностью λ. Поток обслуживании имеет интенсивность μ (величина, обратная среднему времени обслуживания t об). Найти финальные вероятности состояний СМО, а также характеристики ее эффективности:
^ А - абсолютную пропускную способность, т. е. среднее число заявок, обслуживаемых в единицу времени;
Q - относительную пропускную способность, т. е. среднюю долю пришедших заявок, обслуживаемых системой;
^ Р отк - вероятность отказа, т. е. того, что заявка покинет СМО не обслуженной;
k - среднее число занятых каналов.
Решение. Состояния системы ^ S (СМО) будем нумеровать по числу заявок, находящихся в системе (в данном случае оно совпадает с числом занятых каналов):
S 0 - в СМО нет ни одной заявки,
S 1 - в СМО находится одна заявка (один канал занят, остальные свободны),
S k - в СМО находится k заявок (k каналов заняты, остальные свободны),
S n - в СМО находится п заявок (все n каналов заняты).
Граф состояний СМО соответствует схеме гибели в размножения (рис. 20.1). Разметим данный граф - проставим у стрелок интенсивности потоков событий. Из S 0 в S 1 систему переводит поток заявок с интенсивностью λ (как только приходит заявка, система перескакивает из S 0 в S 1). Тот же поток заявок переводит
систему из любого левого состояния в соседнее правое (см. верхние стрелки на рис. 20.1).
Проставим интенсивности у нижних стрелок. Пусть система находится в состоянии ^ S 1 (работает один канал). Он производит μ обслуживании в единицу времени. Проставляем у стрелки S 1 → S 0 интенсивность μ. Теперь представим себе, что система находится в состоянии S 2 (работают два канала). Чтобы ей перейти в S 1 , нужно, чтобы либо закончил обслуживание первый канал, либо второй; суммарная интенсивность их потоков обслуживании равна 2μ; проставляем ее у соответствующей стрелки. Суммарный поток обслуживании, даваемый тремя каналами, имеет интенсивность 3μ, k каналами - kμ. Проставляем эти интенсивности у нижних стрелок на рис. 20.1.
А теперь, зная все интенсивности, воспользуемся уже готовыми формулами (19.7), (19.8) для финальных вероятностей в схеме гибели и размножения. По формуле (19.8) получим:
Члены разложения 
будут представлять собой коэффициенты при р 0
в выражениях для p 1
Заметим, что в формулы (20.1), (20.2) интенсивности λ и μ входят не по отдельности, а только в виде отношения λ/μ. Обозначим
λ/μ = ρ (20.3)
и будем называть величину р ʼʼприведенной интенсивностью потока заявокʼʼ. Ее смысл-среднее число заявок, приходящее за среднее время обслуживания одной заявки. Пользуясь этим обозначением, перепишем формулы (20.1), (20.2) в виде:
Формулы (20.4), (20.5) для финальных вероятностей состояний называются формулами Эрланга - в честь основателя теории массового обслуживания. Большинство других формул этой теории (сегодня их больше, чем грибов в лесу) не носит никаких специальных имен.
Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, финальные вероятности найдены. По ним мы вычислим характеристики эффективности СМО. Сначала найдем ^ Р отк . - вероятность того, что пришедшая заявка получит отказ (не будет обслужена). Для этого нужно, чтобы все п каналов были заняты, значит,
Р отк = р n = . (20.6)
Отсюда находим относительную пропускную способность - вероятность того, что заявка будет обслужена:
Q = 1 – P отк. = 1 - (20.7)
Абсолютную пропускную способность получим, умножая интенсивность потока заявок λ, на Q:
A = λQ = λ. (20.8)
Осталось только найти среднее число занятых каналов k. Эту величину можно было бы найти ʼʼвпрямуюʼʼ, как математическое ожидание дискретной случайной величины с возможными значениями 0, 1, ..., п и вероятностями этих значений р 0 р 1 , ..., р n:
k = 0 · р 0 + 1 · p 1 + 2 · р 2 + ... + п · р n .
Подставляя сюда выражения (20.5) для р k , (k = 0, 1, ..., п) и выполняя соответствующие преобразования, мы, в конце концов, получили бы верную формулу для k. Но мы выведем ее гораздо проще (вот она, одна из ʼʼмаленьких хитростейʼʼ!) В самом деле, нам известна абсолютная пропускная способность А. Это - не что иное, как интенсивность потока обслуженных системой заявок. Каждый занятый i .шал в единицу времени обслуживает в среднем |л заявок. Значит, среднее число занятых каналов равно
k = A/μ, (20.9)
или, учитывая (20.8),
k = 
(20.10)
Рекомендуем читателю самостоятельно решить пример.
Размещено на реф.рф
Имеется станция связи с тремя каналами (n
= 3), интенсивность потока заявок λ = 1,5 (заявки в минуту); среднее время обслуживания одной заявки t
об = 2 (мин.), все потоки событий (как и во всем этом параграфе) - простейшие. Найти финальные вероятности состояний и характеристики эффективности СМО: А, Q, P
отк, k.
На всякий случай сообщаем ответы: p
0 = 1/13, p
1 = 3/13, p
2 = 9/26, р 3
= 9/26 ≈ 0,346,
А ≈ 0,981, Q ≈ 0,654, P отк ≈ 0,346, k ≈ 1,96.
Из ответов видно, между прочим, что наша СМО в значительной мере перегружена: из трех каналов занято в среднем около двух, а из поступающих заявок около 35% остаются не обслуженными. Предлагаем читателю, в случае если он любопытен и неленив, узнать: сколько потребуется каналов для того, чтобы удовлетворить не менее 80% поступающих заявок? И какая доля каналов при этом будет простаивать?
Тут уже проглядывает некоторый намек на оптимизацию. В самом деле, содержание каждого канала в единицу времени обходится в какую-то сумму. Вместе с тем, каждая обслуженная заявка приносит какой-то доход. Умножая данный доход на среднее число заявок А, обслуживаемых в единицу времени, мы получим средний доход от СМО в единицу времени. Естественно, при увеличении числа каналов данный доход растет, но растут и расходы, связанные с содержанием каналов. Что перевесит - увеличение доходов или расходов? Это зависит от условий операции, от ʼʼплаты за обслуживание заявкиʼʼ и от стоимости содержания канала. Зная эти величины, можно найти оптимальное число каналов, наиболее эффективное экономически. Мы такой задачи решать не будем, предоставляя все тому же ʼʼнеленивому и любопытному читателюʼʼ придумать пример и решить. Вообще, придумывание задач больше развивает, чем решение уже поставленных кем-то.
^ 2. Одноканальная СМО с неограниченной очередью. На практике довольно часто встречаются одноканальные СМО с очередью (врач, обслуживающий пациентов; телефон-автомат с одной будкой; ЭВМ, выполняющая заказы пользователей). В теории массового обслуживания одноканальные СМО с очередью также занимают особое место (именно к таким СМО относится большинство полученных до сих пор аналитических формул для немарковских систем). По этой причине мы уделим одноканальной СМО с очередью особое внимание.
Пусть имеется одноканальная СМО с очередью, на которую не наложено никаких ограничений (ни по длине очереди, ни по времени ожидания). На эту СМО поступает поток заявок с интенсивностью λ; поток обслуживании имеет интенсивность μ, обратную среднему времени обслуживания заявки t об. Требуется найти финальные вероятности состояний СМО, а также характеристики ее эффективности:
L сист. - среднее число заявок в системе,
W сист. - среднее время пребывания заявки в системе,
^ L оч - среднее число заявок в очереди,
W оч - среднее время пребывания заявки в очереди,
P зан - вероятность того, что канал занят (степень загрузки канала).
Что касается абсолютной пропускной способности А и относительной Q, то вычислять их нет нужнобности:
в силу того, что очередь неограниченна, каждая заявка рано или поздно будет обслужена, в связи с этим А = λ, по той же причине Q = 1.
Решение. Состояния системы, как и раньше, будем нумеровать по числу заявок, находящихся в СМО:
S 0 - канал свободен,
S 1 - канал занят (обслуживает заявку), очереди нет,
S 2 - канал занят, одна заявка стоит в очереди,
S k - канал занят, k - 1 заявок стоят в очереди,
Теоретически число состояний ничем не ограничено (бесконечно). Граф состоянии имеет вид, показанный на рис. 20.2. Это - схема гибели и размножения, но с бесконечным числом состояний. По всем стрелкам поток заявок с интенсивностью λ переводит систему слева направо, а справа налево - поток обслуживании с интенсивностью μ.
Прежде всего спросим себя, а существуют ли в данном случае финальные вероятности? Ведь число состояний системы бесконечно, и, в принципе, при t → ∞ очередь может неограниченно возрастать! Да, так оно и есть: финальные вероятности для такой СМО существуют не всегда, а только когда система не перегружена. Можно доказать, что если ρ строго меньше единицы (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t → ∞ растет неограниченно. Особенно ʼʼнепонятнымʼʼ кажется данный факт при ρ = 1. Казалось бы, к системе не предъявляется невыполнимых требований: за время обслуживания одной заявки приходит в среднем одна заявка, и все должно быть в порядке, а вот на деле - не так. При ρ = 1 СМО справляется с потоком заявок, только если поток данный - регулярен, и время обслуживания - тоже не случайное, равное интервалу между заявками. В этом ʼʼидеальномʼʼ случае очереди в СМО вообще не будет, канал будет непрерывно занят и будет регулярно выпускать обслуженные заявки. Но стоит только потоку заявок или потоку обслуживании стать хотя бы чуточку случайными - и очередь уже будет расти до бесконечности. На практике этого не происходит только потому, что ʼʼбесконечное число заявок в очередиʼʼ - абстракция. Вот к каким грубым ошибкам может привести замена случайных величин их математическими ожиданиями!
Но вернемся к нашей одноканальной СМО с неограниченной очередью. Строго говоря, формулы для финальных вероятностей в схеме гибели и размножения выводились нами только для случая конечного числа состояний, но позволим себе вольность - воспользуемся ими и для бесконечного числа состояний. Подсчитаем финальные вероятности состояний по формулам (19.8), (19.7). В нашем случае число слагаемых в формуле (19.8) будет бесконечным. Получим выражение для р 0:
p 0 = -1 =
= (1 + р + р 2 + ... + р k +… .) -1 . (20.11)
Ряд в формуле (20.11) представляет собой геометрическую прогрессию. Мы знаем, что при ρ < 1 ряд сходится - это бесконечно убывающая геометрическая прогрессия со знаменателем р.
Размещено на реф.рф
При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний р 0 , p 1 , ..., p k , ...
существуют только при р<1). Теперь предположим, что это условие выполнено, и ρ <1. Суммируя прогрессию в (20.11), имеем
1 + ρ + ρ 2 + ... + ρ k + ... = ,
p 0 = 1 - ρ. (20.12)
Вероятности р 1 , р 2 , ..., р k , ... найдутся по формулам:
p 1 = ρp 0 , p 2 = ρ 2 p 0 ,…,p k = ρp 0 , ...,
откуда, с учетом (20.12), найдем окончательно:
p 1 = ρ (1 - ρ), p 2 = ρ 2 (1 - ρ), . . . , p k = ρ k (1 - ρ), . . .(20.13)
Как видно, вероятности p 0
, p 1
, ..., p k , ...
образуют геометрическую прогрессию со знаменателем р.
Размещено на реф.рф
Как это ни странно, максимальная из них р 0 -
вероятность того, что канал будет вообще свободен. Как бы ни была нагружена система с очередью, в случае если только она вообще справляется с потоком заявок (ρ<1), самое вероятное число заявок в системе будет 0.
Найдем среднее число заявок в СМО ^ L сист . . Тут придется немного повозиться. Случайная величина Z - число заявок в системе - имеет возможные значения 0, 1, 2, .... k, ... с вероятностями p 0 , р 1 , р 2 , ..., p k , ... Ее математическое ожидание равно
L сист = 0 · p 0 + 1 · p 1 + 2 · p 2 +…+k · p k +…= (20.14)
(сумма берется не от 0 до ∞, а от 1 до ∞, так как нулевой член равен нулю).
Подставим в формулу (20.14) выражение для p k (20.13):
L
сист. = 
Теперь вынесем за знак суммы ρ (1-ρ):
L сист. = ρ (1-ρ)
Тут мы опять применим ʼʼмаленькую хитростьʼʼ: k ρ k -1 есть не что иное, как производная по ρ от выражения ρ k ; значит,
L сист. = ρ (1-ρ)
Меняя местами операции дифференцирования п суммирования, получим:
L сист. = ρ (1-ρ) (20.15)
Но сумма в формуле (20.15) есть не что иное, как сумма бесконечно убывающей геометрической прогрессии с первым членом ρ и знаменателем ρ; эта сумма
равна , а ее производная .Подставляя это выражение в (20.15), получим:
L сист = . (20.16)
Ну, а теперь применим формулу Литтла (19.12) и найдем среднее время пребывания заявки в системе:
W сист = (20.17)
Найдем среднее число заявок в очереди L оч. Будем рассуждать так: число заявок в очереди равно числу заявок в системе минус число заявок, находящихся под обслуживанием. Значит (по правилу сложения математических ожиданий), среднее число заявок в очереди L оч равно среднему числу заявок в системе L сист минус среднее число заявок под обслуживанием. Число заявок под обслуживанием должна быть либо нулем (если канал свободен), либо единицей (если он занят). Математическое ожидание такой случайной величины равно вероятности того, что канал занят (мы ее обозначили Р зан). Очевидно, Р зан равно единице минус вероятность р 0 того, что канал свободен:L внеш и среднее время этого ожидания W внеш (две последние величины связаны формулой Литтла). Наконец, найдите суммарный суточный штраф Ш, который придется заплатить станции за простои составов на внешних путях, в случае если за один час простоя одного состава станция платит штраф а (руб.). На всякий случай сообщаем ответы: L сист. = 2 (состава), W сист. = 1 (час), L оч = 4/3 (состава), W оч = 2/3 (часа), L внеш = 16/27 (состава), W внеш = 8/27 ≈ 0,297 (часа). Средний суточный штраф Ш за ожидание составов на внешних путях получим, перемножая среднее число составов, прибывающих на станцию за сутки, среднее время ожидания состава на внешних путях и часовой штраф а : Ш ≈ 14,2а .
^ 3. re-канальная СМО с неограниченной очередью. Совершенно аналогично задаче 2, но чуточку более сложно, решается задача об n -канальной СМО с неограниченной очередью. Нумерация состояний - опять по числу заявок, находящихся в системе:
N <1. В случае если ρ/n ≥ 1, очередь растет до бесконечности.
Предположим, что условие ρ/n < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для р 0 будет стоять ряд членов, содержащих факториалы, плюс сумма бесконечно убывающей геометрической прогрессии со знаменателем ρ/n . Суммируя ее, найдем
(20.22)
Теперь найдем характеристики эффективности СМО. Из них легче всего находится среднее число занятых каналов k == λ/μ, = ρ (это вообще справедливо для любой СМО с неограниченной очередью). Найдем среднее число заявок в системе L сист и среднее число заявок в очереди L оч. Из них легче вычислить второе, по формуле
L оч =
выполняя соответствующие преобразования по образцу задачи 2
(с дифференцированием ряда), получим:
L
оч = 
(20.23)
Прибавляя к нему среднее число заявок под обслуживанием (оно же - среднее число занятых каналов) k = ρ, получим:
L сист = L оч + ρ. (20.24)
Деля выражения для L оч и L сист на λ, по формуле Литтла получим средние времена пребывания заявки в очереди и в системе:
(20.25)
А теперь решим любопытный пример.
Размещено на реф.рф
Железнодорожная касса по продаже билетов с двумя окошками представляет собой двухканальную СМО с неограниченной очередью, устанавливающейся сразу к двум окошкам (если одно окошко освобождается, ближайший в очереди пассажир его занимает). Касса продает билеты в два пункта: А и В.
Интенсивность потока заявок (пассажиров, желающих купить билет) для обоих пунктов А и В
одинакова: λ А = λ В = 0,45 (пассажира в минуту), а в сумме они образуют общий поток заявок с интенсивностью λ А +
λ В = 0,9. Кассир тратит на обслуживание пассажира в среднем две минуты. Опыт показывает, что у кассы скапливаются очереди, пассажиры жалуются на медленность обслуживания, Поступило рационализаторское предложение: вместо одной кассы, продающей билеты и в А
и в В,
создать две специализированные кассы (по одному окошку в каждой), продающие билеты одна - только в пункт А
, другая - только в пункт В.
Разумность этого предложения вызывает споры - кое-кто утверждает, что очереди останутся прежними. Требуется проверить полезность предложения расчетом. Так как мы умеем считать характеристики только для простейших СМО, допустим, что все потоки событий - простейшие (на качественной стороне выводов это не скажется).
Ну, что же, возьмемся за дело. Рассмотрим два варианта организации продажи билетов - существующий и предлагаемый.
Вариант I (существующий). На двухканальную СМО поступает поток заявок с интенсивностью λ = 0,9; интенсивность потока обслуживании μ = 1/2 = 0,5; ρ = λ/μ = l,8. Так как ρ/2 = 0,9<1, финальные вероятности существуют. По первой формуле (20.22) находим р 0 ≈ 0,0525. Среднее, число заявок в очереди находим по формуле (20.23): L оч ≈ 7,68; среднее время, проводимое заявкой в очереди (по первой из формул (20.25)), равно W оч ≈ 8,54 (мин.).
Вариант II (предлагаемый). Надо рассмотреть две одноканальные СМО (два специализированных окошка); на каждую поступает поток заявок с интенсивностью λ = 0,45; μ. по-прежнему равно 0,5; ρ = λ/μ = 0,9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) L оч = 8,1.
Вот тебе и раз! Длина очереди, оказывается, не только не уменьшилась, а увеличилась! Может быть, уменьшилось среднее время ожидания в очереди? Посмотрим. Деля L оч на λ = 0,45, получим W оч ≈ 18 (минут).
Вот так рационализация! Вместо того чтобы уменьшиться, и средняя длина очереди, и среднее время ожидания в ней увеличились!
Давайте попробуем догадаться, почему так произошло? Пораскинув мозгами, приходим к выводу: произошло это потому, что в первом варианте (двухканальная СМО) меньше средняя доля времени, которую простаивае
Примеры решения задач систем массового обслуживания - понятие и виды. Классификация и особенности категории "Примеры решения задач систем массового обслуживания" 2017, 2018.
ВВЕДЕНИЕ
ГЛАВА I. ПОСТАНОВКА ЗАДАЧ МАССОВОГО ОБСЛУЖИВАНИЯ
1.1 Общие понятие теории массового обслуживания
1.2 Моделирование систем массового обслуживания
1.3 Графы состояний СМО
1.4 Случайные процессы
Глава II. УРАВНЕНИЯ, ОПИСЫВАЮЩИЕ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ
2.1 Уравнения Колмогорова
2.2 Процессы «рождения – гибели»
2.3 Экономико-математическая постановка задач массового обслуживания
Глава III. МОДЕЛИ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ
3.1 Одноканальная СМО с отказами в обслуживании
3.2 Многоканальная СМО с отказами в обслуживании
3.3 Модель многофазной системы обслуживания туристов
3.4 Одноканальная СМО с ограниченной длиной очереди
3.5 Одноканальная СМО с неограниченной очередью
3.6 Многоканальная СМО с ограниченной длиной очереди
3.7 Многоканальная СМО с неограниченной очередью
3.8 Анализ системы массового обслуживания супермаркета
ЗАКЛЮЧЕНИЕ
Введение
В настоящее время появилось большое количество литературы, посвященной непосредственно теории массового обслуживания, развитию ее математических аспектов, а также различных сфер ее приложения - военной, медицинской, транспортной, торговле, авиации и др.
Теория массового обслуживания опирается на теорию вероятностей и математическую статистику. Первоначальное развитие теории массового обслуживания связано с именем датского ученого А.К. Эрланга(1878-1929),с его трудами в области проектирования и эксплуатации телефонных станций.
Теория массового обслуживания - область прикладной математики, занимающаяся анализом процессов в системах производства, обслуживания, управления, в которых однородные события повторяются многократно, например, на предприятиях бытового обслуживания; в системах приема, переработки и передачи информации; автоматических линиях производства и др. Большой вклад в развитие этой теории внесли российские математики А.Я. Хинчин, Б.В. Гнеденко, А.Н. Колмогоров, Е.С. Вентцель и др.
Предметом теории массового обслуживания является установление зависимостей между характером потока заявок, числом каналов обслуживания, производительностью отдельного канала и эффективным обслуживанием с целью нахождения наилучших путей управления этими процессами. Задачи теории массового обслуживания носят оптимизационный характер и в конечном итоге включают экономический аспект по определению такого, варианта системы, при котором будет обеспечен минимум суммарных затрат от ожидания обслуживания, потерь времени и ресурсов на обслуживание и от простоев каналов обслуживания.
В коммерческой деятельности применение теории массового обслуживания пока не нашло желаемого распространения.
В основном это связано с трудностью постановки задач, необходимостью глубокого понимания содержания коммерческой деятельности, а также надежного и точного инструментария, позволяющего просчитывать в коммерческой деятельности различные варианты последствий управленческих решений.
Глава I . Постановка задач массового обслуживание
1.1 Общие понятие теории массового обслуживания
Природа массового обслуживания, в различных сферах, весьма тонка и сложна. Коммерческая деятельность связана с выполнением множества операций на этапах движения, например товарной массы из сферы производства в сферу потребления. Такими операциями являются погрузка товаров, перевозка, разгрузка, хранение, обработка, фасовка, реализация. Кроме таких основных операций процесс движения товаров сопровождается большим количеством предварительных, подготовительных, сопутствующих, параллельных и последующих операций с платежными документами, тарой, деньгами, автомашинами, клиентами и т.п.
Для перечисленных фрагментов коммерческой деятельности характерны массовость поступления товаров, денег, посетителей в случайные моменты времени, затем их последовательное обслуживание (удовлетворение требований, запросов, заявок) путем выполнения соответствующих операций, время выполнения которых носит также случайный характер. Все это создает неравномерность в работе, порождает недогрузки, простой и перегрузки в коммерческих операциях. Много неприятностей доставляют очереди, например, посетителей в кафе, столовых, ресторанах, или водителей автомобилей на товарных базах, ожидающих разгрузки, погрузки или оформления документов. В связи с этим возникают задачи анализа существующих вариантов выполнения всей совокупности операций, например, торгового зала супермаркета, ресторана или в цехах производства собственной продукции для целей оценки их работы, выявления слабых звеньев и резервов для разработки в конечном итоге рекомендаций, направленных на увеличение эффективности коммерческой деятельности.
Кроме того, возникают другие задачи, связанные с созданием, организацией и планированием нового экономичного, рационального варианта выполнения множества операций в пределах торгового зала, кондитерского цеха, всех звеньев обслуживания ресторана, кафе, столовой, планового отдела, бухгалтерии, отдела кадров и др.
Задачи организации массового обслуживания возникают практически во всех сферах человеческой деятельности, например обслуживание продавцами покупателей в магазинах, обслуживание посетителей на предприятиях общественного питания, обслуживание клиентов на предприятиях бытового обслуживания, обеспечение телефонных разговоров на телефонной станции, оказание медицинской помощи больным в поликлинике и т.д. Во всех приведенных примерах возникает необходимость в удовлетворении запросов большого числа потребителей.
Перечисленные задачи можно успешно решать с помощью методов и моделей специально созданной для этих целей теории массового обслуживания (ТМО). В этой теории поясняется, что обслуживать необходимо кого-либо или что-либо, что определяется понятием «заявка (требование) на обслуживание», а операции обслуживания выполняются кем-либо или чем-либо, называемыми каналами (узлами) обслуживания. Роль заявок в коммерческой деятельности выполняют товары, посетители, деньги, ревизоры, документы, а роль каналов обслуживания - продавцы, администраторы, повара, кондитеры, официанты, кассиры, товароведы, грузчики, торговое оборудование и др. Важно заметить, что в одном варианте, например, повар в процессе приготовления блюд является каналом обслуживания, а в другом - выступает в роли заявки на обслуживание, например к заведующему производством за получением товара.
Заявки в силу массовости поступления на обслуживание образуют потоки, которые до выполнения операций обслуживания называются входящими, а после возможного ожидания начала обслуживания, т.е. простоя в очереди, образуют потоки обслуживания в каналах, а затем формируется выходящий поток заявок. В целом совокупность элементов входящего потока заявок, очереди, каналов обслуживания и выходящего потока заявок образует простейшую одноканальную систему массового обслуживания - СМО.
Под системой понимается совокупность взаимосвязанных и. целенаправленно взаимодействующих частей (элементов). Примерами таких простейших СМО в коммерческой деятельности являются места приема и обработки товаров, узлы расчета с покупателями в магазинах, кафе, столовых, рабочие места экономист та, бухгалтера, коммерсанта, повара на раздаче и т.д.
Процедура обслуживания считается завершенной, когда заявка на обслуживание покидает систему. Продолжительность интервала времени, требуемого для реализации процедуры обслуживания, зависит в основном от характера запроса заявки на обслуживание, состояния самой обслуживающей системы и канала обслуживания.
Действительно, продолжительность пребывания покупателя в супермаркете зависит, с одной стороны, от личностных качеств покупателя, его запросов, от ассортимента товаров, который он собирается приобрести, а с другой - от формы организации обслуживания и обслуживающего персонала, что может значительно повлиять на время пребывания покупателя в супермаркете и интенсивность обслуживания. Например, овладение кассирами-контролерами работы «слепым» методом на кассовом аппарате позволило увеличить пропускную способность узлов расчета в 1,3 раза и сэкономить время, затрачиваемое на расчеты с покупателями по каждой кассе более чем на 1,5 ч в день. Внедрение единого узла расчета в супермаркете дает ощутимые преимущества покупателю. Так, если при традиционной форме расчетов время обслуживания одного покупателя составляло в среднем 1,5 мин, то при введении единого узла расчета - 67 с. Из них 44 с уходят на оформление покупки в секции и 23 с непосредственно на расчеты за покупки. Если покупатель делает несколько покупок в разных секциях, то потери времени сокращаются при приобретении двух покупок в 1,4 раза, трех - в 1,9, пяти - в 2,9 раза.
Под обслуживанием заявок будем понимать процесс удовлетворения потребности. Обслуживание имеет различный характер по своей природе. Однако, во всех примерах поступившие заявки нуждаются в обслуживании со стороны какого-либо устройства. В некоторых случаях обслуживание производится одним человеком (обслуживание покупателя одним продавцом, в некоторых - группой людей (обслуживание больного врачебной комиссией в поликлинике), а в некоторых случаях - техническими устройствами (продажа газированной воды, бутербродов автоматами). Совокупность средств, которые осуществляют обслуживание заявок, называется каналом обслуживания.
Если каналы обслуживания способны удовлетворить одинаковые заявки, то каналы обслуживания называются однородными. Совокупность однородных каналов обслуживания называется обслуживающей системой.
В систему массового обслуживания поступает большое количество заявок в случайные моменты времени, длительность обслуживания которых также является случайной величиной. Последовательное поступление заявок в систему обслуживания называется входящим потоком заявок, а последовательность заявок, покидающих систему обслуживания,- выходящим потоком.
Случайный характер распределения длительности выполнения операций обслуживания наряду со случайным характером поступления требований на обслуживание приводит к тому, что в каналах обслуживания протекает случайный процесс, который "может быть назван (по аналогии с входным потоком заявок) потоком обслуживания заявок или просто потоком обслуживания.
Заметим, что заявки, поступающие в систему обслуживания, могут покинуть ее и будучи не обслуженными. Например, если покупатель не найдет в магазине нужный товар, то он покидает магазин, будучи не обслуженным. Покупатель может покинуть магазин также, если нужный товар имеется, но большая очередь, а покупатель не располагает временем.
Теория массового обслуживания занимается изучением процессов, связанных с массовым обслуживанием, разработкой методов решения типичных задач массового обслуживания.
При исследовании эффективности работы системы обслуживания важную роль играют различные способы расположения в системе каналов обслуживания.
При параллельном расположении каналов обслуживания требование может быть обслужено любым свободным каналом. Примером такой системы обслуживания является расчетный узел в магазинах самообслуживания, где число каналов обслуживания совпадает с числом кассиров-контролеров.
На практике часто обслуживание одной заявки осуществляется последовательно несколькими каналами обслуживания. При этом очередной канал обслуживания начинает работу по обслуживанию заявки после того, как предыдущий канал закончил свою работу. В таких системах процесс обслуживания носит многофазовый характер, обслуживание заявки одним каналом называется фазой обслуживания. Например, если в магазине самообслуживания имеются отделы с продавцами, то покупатели сначала обслуживаются продавцами, а потом уже кассирами-контролерами.
Организация системы обслуживания зависит от воли человека. Под качеством функционирования системы в теории массового обслуживания понимают не то, насколько хорошо выполнено обслуживание, а то, насколько полно загружена система обслуживания, не простаивают ли каналы обслуживания, не образуется ли очередь.
В коммерческой деятельности заявки, поступающие в систему массового обслуживания, выступают с высокими претензиями еще и на качество обслуживания в целом, которое включает не только перечень характеристик, исторически сложившихся и рассматриваемых непосредственно в теории массового обслуживания, но и дополнительные характерные для специфики коммерческой деятельности, в частности отдельных процедур обслуживания, требования, к уровню которых к настоящему времени сильно возросли. В связи с этим необходимо учитывать еще и показатели коммерческой деятельности.
Работу системы обслуживания характеризуют такие показатели. Как время ожидания начала обслуживания, длина очереди, возможность получения отказа в обслуживании, возможность простоя каналов обслуживания, стоимость обслуживания и в конечном итоге удовлетворение качеством обслуживания, которое еще включает показатели коммерческой деятельности. Чтобы улучшить качество функционирования системы обслуживания, необходимо определить, каким образом распределить поступающие заявки между каналами обслуживания, какое количество каналов обслуживания необходимо иметь, как расположить или сгруппировать каналы обслуживания или обслуживающие аппараты для улучшения показателей коммерческой деятельности. Для решения перечисленных задач существует эффективный метод моделирования, включающий и объединяющий достижения разных наук, в том числе математики.
1.2 Моделирование систем массового обслуживания
Переходы СМО из одного состояния в другое происходят под воздействием вполне определенных событий - поступления заявок и их обслуживания. Последовательность появления событий, следующих одно за другим в случайные моменты времени, формирует так называемый поток событий. Примерами таких потоков в коммерческой деятельности являются потоки различной природы - товаров, денег, документов, транспорта, клиентов, покупателей, телефонных звонков, переговоров. Поведение системы обычно определяется не одним, а сразу несколькими потоками событий. Например, обслуживание покупателей в магазине определяется потоком покупателей и потоком обслуживания; в этих потоках случайными являются моменты появления покупателей, время ожидания в очереди и время, затрачиваемое на обслуживание каждого покупателя.
При этом основной характерной чертой потоков является вероятностное распределение времени между соседними событиями. Существуют различные потоки, которые отличаются своими характеристиками.
Поток событий называется регулярным, если в нем события следуют одно за другим через заранее заданные и строго определенные промежутки времени. Такой поток является идеальным и очень редко встречается на практике. Чаще встречаются нерегулярные потоки, не обладающие свойством регулярности.
Поток событий называется стационарным, если вероятность попадания любого числа событий на промежуток времени зависит только от длины этого промежутка и не зависит от того, как далеко расположен этот промежуток от начала отсчета времени. Стационарность потока означает независимость от времени его вероятностных характеристик, в частности, интенсивность такого потока есть среднее число событий в единицу времени и остается величиной постоянной. На практике обычно потоки могут считаться стационарными только на некотором ограниченном промежутке времени. Обычно поток покупателей, например, в магазине существенно меняется в течение рабочего дня. Однако можно выделить определенные временные интервалы, внутри которых этот поток допустимо рассматривать как стационарный, имеющий постоянную интенсивность.
Поток событий называется потоком без последствия, если число событий, попадающих на один из произвольно выбранных промежутков времени, не зависит от числа событий, попавших на другой, также произвольно выбранный промежуток, при условии, что эти промежутки не пересекаются между собой. В потоке без последствия события появляются в последовательные моменты времени независимо друг от друга. Например, поток покупателей, входящих в магазин, можно считать потоком без последствия потому, что причины, обусловившие приход каждого из них, не связаны с аналогичными причинами для других покупателей.
Поток событий называется ординарным, если вероятность попадания на очень малый отрезок времени сразу двух или более событий пренебрежимо мала по сравнению с вероятностью попадания только одного события. В ординарном потоке события происходят поодиночке, а не по два или более разу. Если поток одновременно обладает свойствами стационарности, ординарности и отсутствием последствия, то такой поток называется простейшим (или пуассоновским) потоком событий. Математическое описание воздействия такого потока на системы оказывается наиболее простым. Поэтому, в частности, простейший поток играет среди других существующих потоков особую роль.
Рассмотрим на оси времени некоторый промежуток времени t. Допустим, вероятность попадания случайного события на этот промежуток p, а полное число возможных событий - п. При наличии свойства ординарности потока событий вероятность р должна быть достаточно малой величиной, а я - достаточно большим числом, поскольку рассматриваются массовые явления. В этих условиях для вычисления вероятности попадания на промежуток времени t некоторого числа событий т можно воспользоваться формулой Пуассона:
P m, n = a m _e -a ; (m=0,n),
где величина а = пр - среднее число событий, попадающих на промежуток времени t, которое можно определить через интенсивность потока событий Xследующим образом: a= λ τ
Размерность интенсивности потока X есть среднее число событий в единицу времени. Между п и λ, р и τ имеется следующая связь:
где t- весь промежуток времени, на котором рассматривается действие потока событий.
Необходимо определить распределение интервала времени Т между событиями в таком потоке. Поскольку это случайная величина, найдем ее функцию распределения. Как известно из теории вероятностей, интегральная функция распределения F(t) есть вероятность того, что величина T будет меньше времени t.
По условию в течение времени T не должно произойти ни одного события, а на интервале времени t должно появиться хотя бы одно событие. Эта вероятность вычисляется с помощью вероятности противоположного события на промежутке времени (0; t), куда не попало ни одного события, т.е. m= 0, тогда
F(t)=1-P 0 =1-(a 0 *e -a)0!=1-e -Xt ,t≥0
Для малых ∆tможно получить приближенную формулу, получаемую заменой функции e - Xt , только двумя членами разложения в ряд по степеням ∆t, тогда вероятность попадания на малый промежуток времени ∆t хотя бы одного события составляет
P(T<∆t)=1-e - λ t ≈1- ≈ λΔt
Плотность распределения промежутка времени между двумя последовательными событиями получим, продифференцировав F(t) по времени,
f(t)= λe- λ t ,t≥0
Пользуясь полученной функцией плотности распределения, можно получить числовые характеристики случайной величины Т: математическое ожидание М (Т), дисперсию D(T) и среднее квадратическое отклонение σ(Т).
М(Т)= λ ∞ ∫ 0 t*e - λt *dt=1/ λ ; D(T)=1/ λ 2 ; σ(T)=1/ λ .
Отсюда можно сделать следующий вывод: средний интервал времени Т между любыми двумя соседними событиями в простейшем потоке в среднем равен 1/λ , и его среднее квадратическое отклонение также равно 1/λ, λ где, - интенсивность потока, т.е. среднее число событий, происходящих в единицу времени. Закон распределения случайной величины, обладающей такими свойствами М(Т) = Т, называется показательным (или экспоненциальным), а величина λ, является параметром этого показательного закона. Таким образом, для простейшего потока математическое ожидание интервала времени между соседними событиями равно его среднеквадратическому отклонению. В этом случае вероятность того, что число заявок, поступающих на обслуживание за промежуток времени t, равно к, определяется по закону Пуассона:
P k (t)=(λt) k / k! *e -λ t ,
где λ - интенсивность поступления потока заявок, среднее число событий в СМО за единицу времени, например[чел/мин; руб./час; чеков/час; докум./день; кг./час; т./год] .
Для такого потока заявок время между двумя соседними заявками Т распределено экспоненциально с плотностью вероятности:
ƒ(t)= λe - λ t .
Случайное время ожидания в очереди начала обслуживания t оч тоже можно считать распределенным экспоненциально:
ƒ (t оч)=V*e - v t оч,
где v - интенсивность потока прохода очереди, определяемая средним числом заявок, проходящих на обслуживание в единицу времени:
где Т оч - среднее время ожидания обслуживания в очереди.
Выходной поток заявок связан с потоком обслуживания в канале, где длительность обслуживания t обс является тоже случайной величиной и подчиняется во многих случаях показательному закону распределения с плотностью вероятности:
ƒ(t обс)=µ*е µ t обс,
где µ - интенсивность потока обслуживания, т.е. среднее число заявок, обслуживаемых в единицу времени:
µ=1/ t обс [чел/мин; руб./час; чеков/час; докум./день; кг./час; т./год] ,
где t обс - среднее время обслуживания заявок.
Важной характеристикой СМО, объединяющей показатели λи µ , является интенсивность нагрузки: ρ= λ/ µ, которая показывает степень согласования входного и выходного потоков заявок канала обслуживания и определяет устойчивость системы массового обслуживания.
Кроме понятия простейшего потока событий часто приходится пользоваться понятиями потоков других типов. Поток событий называется потоком Пальма, когда в этом потоке промежутки времени между последовательными событиями T 1 , T 2 , ..., Т k ..., Т n являются независимыми, одинаково распределенными, случайными величинами, нов отличие от простейшего потока не обязательно распределенными по показательному закону. Простейший поток является частным случаем потока Пальма.
Важным частным случаем потока Пальма является так называемый поток Эрланга.
Этот поток получается «прореживанием» простейшего потока. Такое «прореживание» производится путем отбора по определенному правилу событий из простейшего потока.
Например, условившись учитывать только каждое второе событие из образующих простейший поток, мы получим поток Эрланга второго порядка. Если брать только каждое третье событие, то образуется поток Эрланга третьего порядка и т.д.
Можно получить потоки Эрланга любого к-го порядка. Очевидно, простейший поток есть поток Эрланга первого порядка.
Любое исследование системы массового обслуживания начинается с изучения того, что необходимо обслуживать, следовательно, с изучения входящего потока заявок и его характеристик.
Поскольку моменты времени tи интервалы времени поступления заявок τ, затем продолжительность операций обслуживания t обс и время ожидания в очереди t оч, а также длина очереди l оч - случайные величины, то, следовательно, характеристики состояния СМО носят вероятностный характер, а для их описания следует применять методы и модели теории массового обслуживания.
Перечисленные выше характеристики к, τ, λ, L оч, Т оч, v, t обс, µ, р, Р k являются наиболее общими для СМО, которые являются обычно лишь некоторой частью целевой функции, поскольку необходимо учитывать еще и показатели коммерческой деятельности.
1.3 Графы состояний СМО
При анализе случайных процессов с дискретными состояниями и непрерывным временем удобно пользоваться вариантом схематичного изображения возможных состояний СMO (рис. 6.2.1) в виде графа с разметкой его возможных фиксированных состояний. Состояния СМО изображаются обычно либо прямоугольниками, либо кружками, а возможные направления переходов из одного состояния в другое ориентированы стрелками, соединяющими эти состояния. Например, размеченный граф состояний одноканальной системы случайного процесса обслуживания в газетном киоске приведен на рис. 1.3.
Рис. 1.3. Размеченный граф состояний СМО
Система может находиться в одном из трех состояний: S 0 -канал свободен, простаивает, S 1 - канал занят обслуживанием, S 2 - канал занят обслуживанием и одна заявка в очереди. Переход системы из состояния S 0 в S l происходит под воздействием простейшего потока заявок интенсивностью λ 01 а из состояния S l в состояние S 0 систему переводит поток обслуживания с интенсивностью λ 01 . Граф состояний системы обслуживания с проставленными интенсивностями потоков у стрелок называется размеченным. Поскольку пребывание системы в том или ином состоянии носит вероятностный характер, то вероятность:p i (t) того, что система будет находиться в состоянии S i в момент времени t, называется вероятностью i-го состояния СМО и определяется числом поступивших заявок k на обслуживание.
Случайный процесс, происходящий в системе, заключается в том, что в случайные моменты времени t 0 , t 1, t 2 ,..., t k ,..., t n система оказывается в том или другом заранее известном дискретном состоянии последовательно. Такая. случайная последовательность событий называется Марковской цепью, если для каждого шага вероятность перехода из одного состояния S t в любое другое Sjне зависит от того, когда и как система перешла в состояние S t . Описывается марковская цепь с помощью вероятности состояний, причем они образуют полную группу событий, поэтому их сумма равна единице. Если вероятность перехода не зависит от номера к, то марковская цепь называется однородной. Зная начальное состояние системы обслуживания, можно найти вероятности состояний для любого значения к-числа заявок поступивших на обслуживание.
1.4 Случайные процессы
Переход СМО из одного состояния в другое происходит случайным образом и представляет собой случайный процесс. Работа СМО - случайный процесс с дискретными состояниями, поскольку его возможные состояния во времени можно заранее перечислить. Причем переход из одного состояния в другое, происходит скачкообразно, в случайные моменты времени, по этому он называется процессом с непрерывным временем. Таким образом, работа СМО представляет собой случайный процесс с дискретными состояниями и непрерывным; временем. Например, в процессе обслуживания оптовых покупателей на фирме «Кристалл» в Москве можно фиксировать заранее все возможные состояния простейших. СМО, которые входят в весь цикл, коммерческого обслуживания от момента заключения договора на поставку ликероводочной продукции, ее оплаты, оформления документов, отпуска и получения продукции, догрузки и вывоза со склада готовой продукции.
Из множества разновидностей случайных процессов наибольшее распространение в коммерческой деятельности получили такие процессы, для которых в любой момент времени характеристики процесса в будущем зависят только от его состояния в настоящий момент и не зависят от предыстории - от прошлого. Например, возможность получения с завода «Кристалл» ликероводочной продукции зависит от наличия ее на складе готовой продукции, т.е. его состояния в данный момент, и не зависит от того, когда и как получали и увозили в прошлом эту продукцию другие покупатели.
Такие случайные процессы называются процессами без последствия, или марковскими, в которых при фиксированном настоящем будущее состояние СМО не зависит от прошлого. Случайный процесс, протекающий в системе, называется марковским случайным процессом, или «процессом без последствия», если он обладает следующим свойством: для каждого момента времени t 0 вероятность любого состояния t > t 0 системы S i , - в будущем (t>t Q) зависит только от ее состояния в настоящем (при t = t 0) и не зависит от того, когда и каким образом система пришла в это состояние, т.е. оттого, как развивался процесс в прошлом.
Марковские случайные процессы делятся на два класса: процессы с дискретными и непрерывными состояниями. Процесс с дискретными состояниями возникает в сиcтемах, обладающих только некоторыми фиксированными состояниями, между которыми возможны скачкообразные переходы в некоторые, заранее не известные моменты времени. Рассмотрим пример процесса с дискретными состояниями. В офисе фирмы имеются два телефона. Возможны следующие состояния у этой системы обслуживания: S o -телефоны свободны; S l - один из телефонов занят; S 2 - оба телефона заняты.
Процесс, протекающий в этой системе, состоит в том, что система случайным образом переходит скачком из одного дискретного состояния в другое.
Процессы с непрерывными состояниями отличаются непрерывным плавным переходом из одного состояния в другое. Эти процессы более характерны для технических устройств, нежели для экономических объектов, где обычно лишь приближенно можно говорить о непрерывности процесса (например, непрерывном расходовании запаса товара), тогда как фактически всегда процесс имеет дискретный характер. Поэтому далее мы будем рассматривать только процессы с дискретными состояниями.
Марковские случайные процессы с дискретными состояниями в свою очередь подразделяются на процессы с дискретным временем и процессы с непрерывным временем. В первом случае переходы из одного состояния в другое происходят только в определенные, заранее фиксированные моменты времени, тогда как в промежутки между этими моментами система сохраняет свое состояние. Во втором случае переход системы из состояния в состояние может происходить в любой случайный момент времени.
На практике процессы с непрерывным временем встречаются значительно чаще, поскольку переходы системы из одного состояния в другое обычно происходят не в какие-то фиксированные моменты времени, а в любые случайные моменты времени.
Для описания процессов с непрерывным временем используется модель в виде так называемой марковской цепи с дискретными состояниями системы, или непрерывной марковской цепью.
Глава II . Уравнения описывающие системы массового обслуживания
2.1 Уравнения Колмогорова
Рассмотрим математическое описание марковского случайного процесса с дискретными состояниями системы S o , S l , S 2 (см. рис. 6.2.1) и непрерывным временем. Полагаем, что все переходы системы массового обслуживания из состояния S i в состояние Sjпроисходят под воздействием простейших потоков событий с интенсивностями λ ij , а обратный переход под воздействием другого потока λ ij ,. Введем обозначение p i как вероятность того, что в момент времени t система находится в состоянии S i . Для любого момента времени tсправедливо записать нормировочное условие-сумма вероятностей всех состояний равна 1:
Σp i (t)=p 0 (t)+ p 1 (t)+ p 2 (t)=1
Проведем анализ системы в момент времени t, задав малое приращение времени Δt, и найдем вероятность р 1 (t+ Δt) того, что система в момент времени (t+ Δt) будет находиться в состоянии S 1 которое достигается разными вариантами:
а) система в момент t с вероятностью p 1 (t) находилась в состоянии S 1 и за малое приращение времени Δt так и не перешла в другое соседнее состояние - ни в S 0 , ни bS 2 . Вывести систему из состояния S 1 можно суммарным простейшим потоком c интенсивностью (λ 10 +λ 12), поскольку суперпозиция простейших потоков также является простейшим потоком. На этом основании вероятность выхода из состояния S 1 за малый промежуток времени Δtприближенно равна (λ 10 +λ 12)* Δt. Тогда вероятность невыхода из этого состояния равна .Bсоответствии с этим вероятность того, что система останется в состоянии Siна основании теоремы умножения вероятностей, равна:
p 1 (t) ;
б)система находилась в соседнем состоянии S o и за малое время Δt перешла в состояние S o Переход системы происходит под воздействием потока λ 01 с вероятностью, приближенно равной λ 01 Δt
Вероятность того, что система будет находиться в состоянии S 1 , в этом варианте равна p o (t)λ 01 Δt;
в) система находилась в состоянии S 2 и за время Δt перешла в состояние S 1 под воздействием потока интенсивностью λ 21 с вероятностью, приближенно равной λ 21 Δt. Вероятность того, что система будет находиться в состоянии S 1 , равна p 2 (t) λ 21 Δt.
Применяя теорему сложения вероятностей для этих вариантов, получим выражение:
p 2 (t+Δt)= p 1 (t) + p o (t)λ 01 Δt+p 2 (t) λ 21 Δt ,
которое можно записать иначе:
p 2 (t+Δt)-p 1 (t)/ Δt= p o (t)λ 01 + p 2 (t) λ 21 - p 1 (t) (λ 10 +λ 12) .
Переходя к пределу при Δt-> 0, приближенные равенства перейдут в точные, и тогда получим производную первого порядка
dp 2 /dt= p 0 λ 01 +p 2 λ 21 -p 1 (λ 10 +λ 12) ,
что является дифференциальным уравнением.
Проводя рассуждения аналогичным образом для всех других состояний системы, получим систему дифференциальных уравнений, которые называются уравнениями А.Н. Колмогорова:
dp 0 /dt= p 1 λ 10 ,
dp 1 /dt= p 0 λ 01 +p 2 λ 21 -p 1 (λ 10 +λ 12) ,
dp 2 /dt= p 1 λ 12 +p 2 λ 21 .
Для составления уравнений Колмогорова существуют общие правила.
Уравнения Колмогорова позволяют вычислить все вероятности состояний СМО S i в функции времени p i (t). В теории случайных процессов показано, что если число состояний системы конечно, а из каждого из них можно перейти в любое другое состояние, то существуют предельные (финальные) вероятности состояний, которые показывают на среднюю относительную величину времени пребывания системы, в этом состоянии. Если предельная вероятность состояния S 0 – равна p 0 = 0,2, то, следовательно, в среднем 20% времени, или 1/5 рабочего времени, система находится в состоянии S o . Например, при отсутствии заявок на обслуживание к = 0, р 0 = 0,2,; следовательно, в среднем 2 ч в день система находится в состоянии S o и простаивает, если продолжительность рабочего дня составляет 10 ч.
Поскольку предельные вероятности системы постоянны, то заменив в уравнениях Колмогорова соответствующие производные нулевыми значениями, получим систему линейных алгебраических уравнений, описывающих стационарный режим СМО. Такую систему уравнений составляют по размеченному графу состояний СМО по следующим правилам: слева от знака равенства в уравнении стоит предельная вероятность р i рассматриваемого состояния Siумноженная на суммарную интенсивность всех потоков, выводящих (выходящие стрелки) изданного состояния S i систему, а справа от знака равенства - сумма произведений интенсивности всех потоков, входящих (входящие стрелки) в состояние Siсистему, на вероятность тех состояний, из которых эти потоки исходят. Для решения подобной системы необходимо добавить еще одно уравнение, определяющее нормировочное условие, поскольку сумма вероятностей всех состояний СМО равна 1: n
Например, для СМО, имеющей размеченный граф из трех состояний S o , S 1 , S 2 рис. 6.2.1, система уравнений Колмогорова, составленная на основе изложенного правила, имеет следующий вид:
Для состояния S o → p 0 λ 01 = p 1 λ 10
Для состояния S 1 →p 1 (λ 10 +λ 12) = p 0 λ 01 +p 2 λ 21
Для состояния S 2 → p 2 λ 21 = p 1 λ 12
p 0 +p 1 +p 2 =1
dp 4 (t)/dt=λ 34 p 3 (t) - λ 43 p 4 (t) ,
p 1 (t)+ p 2 (t)+ p 3 (t)+ p 4 (t)=1 .
К этим уравнениям надо добавить еще начальные условия. Например, если при t = 0 система S находится в состоянии S 1, то начальные условия можно записать так:
p 1 (0)=1, p 2 (0)= p 3 (0)= p 4 (0)=0 .
Переходы между состояниями СМО происходит под воздействием поступления заявок и их обслуживания. Вероятность перехода в случае, если поток событий простейший, определяется вероятностью появления события в течение времени Δt, т.е. величиной элемента вероятности перехода λ ij Δt, где λ ij - интенсивность потока событий, переводящих систему из состояния i в состояние i (по соответствующей стрелке на графе состояний).
Если все потоки событий, переводящие систему из одного состояния в другое, простейшие, то процесс, протекающий в системе, будет марковским случайным процессом, т.е. процессом без последствия. В этом случае поведение системы достаточно просто, определяется, если известны интенсивность всех этих простейших потоков событий. Например, если в системе протекает марковский случайный процесс с непрерывным временем, то, записав систему уравнений Колмогорова для вероятностей состояний и проинтегрировав эту систему при заданных начальных условиях, получим все вероятности состояний как функции времени:
p i (t), p 2 (t),…., p n (t) .
Во многих случаях на практике оказывается, что вероятности состояний как функции времени ведут себя таким образом, что существует
lim p i (t) = p i (i=1,2,…,n) ; t→∞
независимо от вида начальных условий. В этом случае говорят, что существуют предельные вероятности состояний системы при t->∞ и в системе устанавливается некоторый предельный стационарный режим. При этом система случайным образом меняет свои, состояния, но каждое из этих состояний осуществляется с некоторой постоянной вероятностью, определяемой средним временем пребывания системы в каждом из состояний.
Вычислить предельные вероятности состояния р i можно, если в системе положить все производные равными 0, поскольку в уравнениях Колмогорова при t-> ∞ зависимость от времени пропадает. Тогда система дифференциальных уравнений превращается в систему Обычных линейных алгебраических уравнений, которая совместно с нормировочным условием позволяет вычислить все предельные вероятности состояний.
2.2 Процессы «рождения – гибели»
Среди однородных марковских процессов существует класс случайных процессов, имеющих широкое применение при построении математических моделей в областях демографии, биологии, медицины (эпидемиологии), экономики, коммерческой деятельности. Это так называемые процессы «рождения - гибели», марковские процессы со стохастическими графами состояний следующего вида:
| S 3 |
| kjlS n |
μ 0 μ 1 μ 3 μ 4 μ n-1
Рис. 2.1 Размеченный граф процесса «рождения - гибели»
Этот граф воспроизводит известную биологическую интерпретацию: величина λ k отображает интенсивность рождения нового представителя некоторой популяции, например, кроликов, причем текущий объем популяции равен k; величина μ является интенсивностью гибели (продажи) одного представителя этой популяции, если текущий объем популяции равен k. В частности, популяция может быть неограниченной (число n состояний марковского процесса является бесконечным, но счетным), интенсивность λ может быть равна нулю (популяция без возможности возрождения), например, при прекращении воспроизводства кроликов.
Для Марковского процесса «рождения - гибели», описанного стохастическим графом, приведенным на рис. 2.1, найдем финальное распределение. Пользуясь правилами составления уравнений для конечнего числа n предельных вероятностей состояния системы S 1 , S 2 , S 3 ,… S k ,…, S n , составим соответствующие уравнения для каждого состояния:
для состояния S 0 -λ 0 p 0 =μ 0 p 1 ;
для состояния S 1 -(λ 1 +μ 0)p 1 = λ 0 p 0 +μ 1 p 2 , которое с учетом предыдущего уравнения для состояния S 0 можно преобразовать к виду λ 1 р 1 = μ 1 p 2 .
Аналогично можно составить уравнения для остальных состояний системы S 2 , S 3 ,…, S k ,…, S n . В результате получим следующую систему уравнений:
Решая эту систему уравнений, можно получить выражения, определяющие финальные состояния системы массового обслуживания:
Следует заметить, что в формулы определения финальных вероятностей состояний р 1 , р 2 , р 3 ,…, р n , входят слагаемые, являющиеся составной частью суммы выражения, определяющей р 0 . В числителях этих слагаемых находятся произведения всех интенсивностей, стоящих у стрелок графа состояний, ведущих слева на право до рассматриваемого состояния S k , а знаменатели представляют собой произведения всех интенсивностей, стоящих у стрелок, ведущих справа на лево до рассматриваемого состояния S k , т.е. μ 0 , μ 1 , μ 2 , μ 3 ,… μ k . В связи с этим запишем эти модели в более компактном виде:
к=1,n
2.3 Экономико-математическая постановка задач массового обслуживания
Правильная или наиболее удачная экономико-математическая постановка задачи в значительной степени определяет полезность рекомендаций по совершенствованию систем массового обслуживания в коммерческой деятельности.
В связи с этим необходимо тщательно проводить наблюдение за процессом в системе, поиска и выявления существенных связей, формирования проблемы, выделения цели, определения показателей и выделения экономических критериев оценки работы СМО. В этом случае в качестве наиболее общего, интегрального показателя могут выступать затраты, с одной стороны, СМО коммерческой деятельности как обслуживающей системы, а с другой – затраты заявок, которые могут иметь разную по своему физическому содержанию природу.
Повышение эффективности в любой сфере деятельности К. Маркс в конечном счете рассматривал как экономию времени и усматривал в этом один из важнейших экономических законов. Он писал, что экономия времени, равно как и планомерное распределение рабочего времени по различным отраслям производства, остается первым экономическим законом на основе коллективного производства. Этот закон проявляется во всех сферах общественной деятельности.
Для товаров, в том числе и денежных средств, поступающих в коммерческую сферу, критерий эффективности связан со временем и скоростью обращения товаров и определяет интенсивность поступления денежных средств в банк. Время и скорость обращения, являясь экономическими показателями коммерческой деятельности, характеризирует эффективность использования средств, вложенных в товарные запасы. Товарооборачиваемость отражает среднюю скорость реализации среднего товарного запаса. Показатели товарооборачиваемости и уровня запасов тесно связаны известным моделями. Таким образом, можно проследить и установить взаимосвязь этих и других показателей коммерческой деятельности с временными характеристиками.
Следовательно, эффективность работы коммерческого предприятия или организации складывается из совокупности времени выполнения отдельных операций обслуживания, в то же время для населения затраты времени включают время на дорогу, посещение магазина, столовой, кафе, ресторана, ожидание начало обслуживания, ознакомление с меню, выбор продукции, расчет и т.д. Проведенные исследования структуры затрат времени населения свидетельствует о том, что значительная его часть расходуется нерационально. Заметим, что коммерческая деятельность в конечном счете направлена на удовлетворение потребности человека. Поэтому усилия моделирования СМО должны включать анализ затрат времени по каждой элементарной операции обслуживания. С помощью соответствующих методов следует создавать модели связи показателей СМО. Это обусловливает необходимость наиболее общие и известные экономические показатели, такие как товарооборот, прибыль, издержки обращения, рентабельность и другие, увязывать в экономико-математических моделях с дополнительно возникающей группой показателей, определяемых спецификой обслуживающих систем и вносимых собственно спецификой теории массового обслуживания.
Например, особенностями показателей СМО с отказами являются: время ожидания заявок в очереди Т оч
=0, поскольку по своей природе в таких системах существование очереди невозможно, то L оч
=0 и, следовательно, вероятность ее образования Р оч
=0. По числу заявок k определятся режим работы системы, ее состояние: при k=0 – простой каналов, при 1
Для СМО с неограниченным ожиданием характерно, что вероятность обслуживания заявки Р обс
=1, поскольку длина очереди и время ожидания начала обслуживания не ограничены, т.е. формально L оч
→∞ и Т оч
→∞. В системах возможны следующие режимы работы: при k=0 наблюдается простой каналов обслуживания, при 1
В СМО с ожиданием с ограничением на длину очереди, если число заявок в системе k=0, то наблюдается простой каналов, при 1
Таким образом, перечень характеристик систем массового обслуживания можно представить следующим образом: среднее время обслуживания – t обс; среднее время ожидания в очереди – Т оч; среднее пребывания В СМО – Т смо; средняя длина очереди - L оч; среднее число заявок в СМО- L смо; количество каналов обслуживания – n; интенсивность входного потока заявок – λ; интенсивность обслуживания – μ; интенсивность нагрузки – ρ; коэффициент нагрузки – α; относительная пропускная способность – Q; абсалютная пропускная способность – А; доля времени простоя в СМО – Р 0 ; доля обслуженных заявок – Р обс; доля потерянных заявок – Р отк, среднее число занятых каналов – n з; среднее число свободных каналов - n св; коэффициент загрузки каналов – К з; среднее время простоя каналов - t пр.
Следует заметить что, иногда достаточно использовать до десяти основных показателей, чтобы выявить слабые места и разработать рекомендации по совершенствованию СМО.
Это часто связано с решением вопросов согласованной рабоиы цепочки или совокупностей СМО.
Например, в коммерческой деятельности необходимо учитывать еще и экономические показатели СМО: общие затраты – С; издержки обращения – С ио, издержки потребления – С ип, затраты на обслуживание одной заявки – С 1 , убытки, связанные с уходом заявки, - С у1 , затраты на эксплуатацию канала – С к, затраты простоя канала – С пр, капитальные вложения – С кап, приведенные годовые затраты – С пр, текущие затраты – С тек, доход СМО в единицу времени – Д 1
В процессе постановки задач необходимо раскрыть взаимосвязи показателей СМО, которые по своей базовой принадлежности можно разделить на две группы: первая связана с издержками обращения С ио, которые определяются числом занятых обслуживанием каналов, затратами на содержание СМО, интенсивностью обслуживания, степенью загрузки каналов, эффективностью их использования, пропускной способностью СМО и др.; вторая группа показателей определяется издержками собственно заявок С ип, поступающих на обслуживание, которые образуют входящий поток, ощущают эффективность обслуживания и связаны с такими показателями, как длина очереди, время ожидания обслуживания, вероятность отказа в обслуживании, время пребывания заявки в СМО и др.
Эти группы показателей противоречивы в том смысле, что улучшение показателей одной группы, например, сокращение длины очереди или времени ожидания в очереди путем увлечения числа каналов обслуживания (официантов, поваров, грузчиков, кассиров), связано с ухудшением показателей группы, поскольку это может привести к увеличению времени простоев каналов обслуживания, затрат на их содержание и т.д. В связи с этим формализации задач обслуживания вполне естественно стремление построить СМО таким образом, чтобы установить разумный компромисс между показателями собственно заявок и полнотой использования возможностей системы. С этой целью необходимо выбрать обобщенный, интегральный показатель эффективности СМО, включающий одновременно претензии и возможности обеих групп. В качестве такого показателя может быть выбран критерий экономической эффективности, включающий как издержки обращения С ио, так и издержки заявок С ип, которые будут иметь оптимальное значение при минимуме общих затрат С. На этом осонвании целевую функцию задачи можно записать так:
С= (С ио +С ип) →min
Поскольку издержки обращения включают затраты, связанные с эксплуатацией СМО – С экс и простоем каналов обслуживания - С пр, а издержки заявок включают потери, связанные с уходом не обслуженных заявок – С нз, и с пребыванием в очереди – С оч, тогда целевую функцию можно переписать с учетом этих показателей таким образом:
С={(С пр n св +С экз n з)+С оч Р обс λ(Т оч +t обс)+С из Р отк λ}→min.
В зависимости от поставленной задачи в качестве варьируемых, т.е управляемых, показателей могут быть: количество каналов обслуживания, организация каналов обслуживания (параллельно, последовательно, смешанным образом), дисциплина очереди, приоритетность обслуживания заявок, взаимопомощь между каналами и др. Часть показателей в задаче фигурирует в качестве неуправляемых, которые обычно являются исходными данными. В качестве критерия эффективности в целевой функции могут быть так же товарооборот, прибыль, или доход, например, рентабельность, тогда оптимальные значения управляемых показателей СМО находятся очевидно, уже при максимизации, как в предыдущем варианте.
В некоторых случаях следует пользоваться другим вариантом записи целевой функции:
С={С экз n з +C пр (n-n з)+C отк *Р отк *λ+С сист * n з }→min
В качестве общего критерия может быть выбран, например, уровень культуры обслуживания покупателей на предприятиях, тогда целевая функция может быть представлена следующей моделью:
К об =[(З пу *К у)+(З пв *К в)+(З пд *К д)+(З пз *К з)+(З по *К 0)+(З кт *К кт)]*К мп,
где З пу – значимость показателя устойчивости ассортимента товаров;
К у - коэффициент устойчивости ассортимента товаров;
З пв – значимость показателя внедрения прогрессивных методов продажи товаров;
К в – коэффициент внедрения прогрессивных методов продажи товаров;
З пд – значимость показателя дополнительного обслуживания;
К д - коэффициент дополнительного обслуживания;
З пз - значимость показателя завершенности покупки;
К з - коэффициент завершенности покупки;
З по - значимость показателя затрат времени на ожидание в обслуживании;
К о – показатель затрат времени на ожидание обслуживания;
З кт – значимость показателя качества труда коллектива;
К кт – коэффициент качества труда коллектива;
К мп – показатель культуры обслуживания по мнению покупателей;
Для анализа СМО можно выбирать и другие критерии оценки эффективности работы СМО. Например, в качестве такого критерия для систем с отказами можно выбирать вероятность отказа Р отк, значение которого не превышало бы заранее заданной величины. Например, требование Р отк <0,1 означает, что не менее чем в 90% случаев система должна справляться с обслуживанием потока заявок при заданной интенсивности λ. Можно ограничить среднее время пребывания заявки в очереди или в системе. В качестве показателей, подлежащих определению, могут выступать: либо число каналов n при заданной интенсивности обслуживания μ, либо интенсивность μ при заданном числе каналов.
После построения целевой функции необходимо определить условия решения задачи, найти ограничения, установить исходные значения показателей, выделить неуправляемые показатели, построить или подобрать совокупность моделей взаимосвязи всех показателей для анализируемого типа СМО, чтобы в конечном итоге найти оптимальные значения управляемых показателей, например количество поваров, официантов, кассиров, грузчиков, объемы складских помещений и др
Глава III . Модели систем массового обслуживания
3.1 Одноканальная СМО с отказами в обслуживании
Проведем анализ простой одноканальной СМО с отказами в обслуживании, на которую поступает пуассоновский поток заявок с интенсивностью λ, а обслуживание происходит под действием пуассоновского потока с интенсивностью μ.
Работу одноканальной СМО n=1 можно представить в виде размеченного графа состояний (3.1).
Переходы СМО из одного состояния S 0 в другое S 1 происходят под действием входного потока заявок с интенсивностью λ, а обратный переход – под действием потока обслуживания с интенсивностью μ.
| S 0 |
| S 1 |
S 0 – канал обслуживания свободен; S 1 – канал занят обслуживанием;
Рис. 3.1 Размеченный граф состояний одноканальной СМО
Запишем систему дифференциальных уравнений Колмогорова для вероятностей состояния по изложенным выше правилам:
Откуда получим дифференциальное уравнение для определения вероятности р 0 (t) состояния S 0:
Это уравнение можно решить при начальных условиях в предположении, что система в момент t=0 находилась в состоянии S 0 , тогда р 0 (0)=1, р 1 (0)=0.
В этом случае решение дифференциального уровнения позволяет определить вероятность того, что канал свободен и не занят обслуживанием:
Тогда нетрудно получить выражение для вероятности определения вероятности занятости канала:
Вероятность р 0 (t) уменьшается с течением времени и в пределе при t→∞ стремится к величине
а вероятность р 1 (t) в то же время увеличивается от 0, стремясь в пределе при t→∞ к величине
Эти пределы вероятностей могут быть получены непосредственно из уравнений Колмогорова при условии
Функции р 0 (t) и р 1 (t) определяют переходный процесс в одноканальной СМО и описывают процесс экспоненциального приближения СМО к своему предельному состоянию с постоянной времени характерной для рассматриваемой системы.
С достаточной для практики точностью можно считать, что переходный процесс в СМО заканчивается в течение времени, равно 3τ.
Вероятность р 0 (t) определяет относительную пропускную способность СМО, которая определяет долю обслуживаемых заявок по отношению к полному числу поступающих заявок, в единицу времени.
Действительно, р 0 (t) есть вероятность того, что заявка, пришедшая в момент t, будет принята к обслуживанию. Всего в единицу времени приходит в среднем λ заявок и из них обслуживается λр 0 заявок.
Тогда доля обслуживаемых заявок по отношению ко всему потоку заявок определятся величиной
В пределе при t→∞ практически уже при t>3τ значение относительной пропускной способности будет равно
Абсолютная пропускная способность, определяющая число заявок, обслуживаемых в единицу времени в пределе при t→∞, равна:
Соответственно доля заявок, получивших отказ, составляет в этих же предельных условиях:
а общее число не обслуженных заявок равно
Примерами одноканальных СМО с отказами в обслуживании являются: стол заказов в магазине, диспетчерская автотранспортного предприятия, контора склада, офис управления коммерческой фирмы, с которыми устанавливается связь по телефону.
3.2 Многоканальная СМО с отказами в обслуживании
В коммерческой деятельности примерами многоканальных СМО являются офисы коммерческих предприятий с несколькими телефонными каналами, бесплатная справочная служба по наличию в авто магазинах самых дешевых автомобилей в Москве имеет 7 телефонных номеров, а дозвониться и получить справку, как известно, очень трудно.
Следовательно, авто магазины теряют клиентов, возможность увеличить количество проданных автомобилей и выручку от продаж, товарооборот, прибыль.
Туристические фирмы по продаже путевок имеют два, три, четыре и более каналов, как, например, фирма Express-Line.
Рассмотрим многоканальную СМО с отказами в обслуживании на рис. 3.2, на вход которой поступает пуассоновский поток заявок с интенсивностью λ.
| S 0 |
| S 1 |
| S k |
| S n |
μ 2μkμ (k+1)μ nμ
Рис. 3.2. Размеченный граф состояний многоканальной СМО с отказами
Поток обслуживания в каждом канале имеет интенсивность μ. По числу заявок СМО определяются ее состояния S k , представленные в виде размеченного графа:
S 0 – все каналы свободны k=0,
S 1 – занят только один канал, k=1,
S 2 – заняты только два канала, k=2,
S k – заняты k каналов,
S n – заняты все n каналов, k= n.
Состояния многоканальной СМО меняются скачкообразно в случайные моменты времени. Переход из одного состояния, например S 0 в S 1 , происходит под воздействием входного потока заявок с интенсивностью λ, а обратно – под воздействием потока обслуживания заявок с интенсивностью μ. Для перехода системы из состояния S k в S k -1 безразлично, какой именно из каналов освободиться, поэтому поток событий, переводящий СМО, имеет интенсивность kμ, следовательно, поток событий, переводящий систему из S n в S n -1 , имеет интенсивность nμ. Так формулируется классическая задача Эрланга, названная по имени датского инженера – математика- основателя теории массового обслуживания.
Случайный процесс, протекающий в СМО, представляет собой частный случай процесса «рождения- гибели» и описывается системой дифференциальных уравнений Эрланга, которые позволяют получить выражения для предельных вероятностей состояния рассматриваемой системы, называемые формулами Эрланга:
.
Вычислив все вероятности состояний n – канальной СМО с отказами р 0 , р 1 , р 2 , …,р k ,…, р n , можно найти характеристики системы обслуживания.
Вероятность отказа в обслуживании определяется вероятностью того, что поступившая заявка на обслуживание найдет все n каналов занятыми, система будет находиться в состоянии S n:
k=n.
В системах с отказами события отказа и обслуживания составляют полную группу событий, поэтому
Р отк +Р обс =1
На этом основании относительная пропускная способность опредляется по формуле
Q = P обс = 1-Р отк =1-Р n
Абсолютную пропускную способность СМО можно определить по формуле
Вероятность обслуживания, или доля обслуженных заявок, определяет относительную пропускную способность СМО, которая может быть определена и по другой формуле:
Из этого выражения можно определить среднее число заявок, находящихся под обслуживанием, или, что же самое, среднее число занятых обслуживанием каналов
Коэффициент занятости каналов обслуживанием определятся отношением среднего числа занятых каналов к их общему числу
Вероятность занятости каналов обслуживанием, которая учитывает среднее время занятости t зан и простоя t пр каналов, определяется следующим образом:
Из этого выражения можно определить среднее время простоя каналов
Среднее время пребывания заявки в системе в установившемся режиме определятся формулой Литтла
Т смо = n з /λ.
3.3 Модель многофазной системы обслуживания туристов
В реальной жизни система обслуживания туристов выглядит значительно сложнее, поэтому необходимо детализировать постановку задачи, учитывая запросы, требования как со стороны клиентов, так и турфирмы.
Для увеличения эффективности работы турфирмы необходимо смоделировать в целом поведение потенциального клиента от начала операции до ее завершения. Структура взаимосвязи основных систем массового обслуживания фактически состоит из СМО разного вида (рис. 3.3).
Поиск Выбор Выбор Решение
|
референт |
Оплата Перелет Исход
Рис. 3.3 Модель многофазной системы обслуживания туристов
Проблема с позиции массового обслуживания туристов, уезжающих на отдых, заключается в определении точного места отдыха (тура), адекватного требованиям претендента, соответствующего его здоровью и финансовым возможностям и представлениям об отдыхе в целом. В этом ему могут способствовать турфирмы, поиск которых осуществляется обычно из рекламных сообщений СМО р, затем после выбора фирмы происходит получение консультаций по телефону СМО т, после удовлетворительного разговора приезд в турфирму и получение более детальных консультаций лично с референтом, затем оплата путевки и получение обслуживания от авиакомпании по перелету СМО а и в конечном счете обслуживания в отеле СМ0 0 . Дальнейшее развитие рекомендаций по улучшению работы СМО фирмы связано с изменением профессионального содержания переговоров с клиентами по телефону. Для этого необходимо углубить анализ, связанный с детализацией диалога референта с клиентами, поскольку далеко не каждый переговоры по телефону приводит к заключению договора на приобретение путевки. Проведение формализации задачи обслуживания указало на необходимость формирования полного (необходимого и достаточного) перечня характеристик и их точных значений предмета коммерческой сделки. Затем проводятся ранжирование этих характеристик, например методом парных сравнений, и расположения в диалоге по степени их значимости, например: время года (зима), месяц (январь), климат (сухой), температура воздуха (+25"С), влажность (40%), географическое место (ближе к экватору), время авиаперелета (до 5 часов), трансферт, страна (Египет), город (Хургада), море (Красное), температура воды в море (+23°С), ранг отеля (4 звезды, работающий кондиционер, гарантия наличия шампуня в номере), удаленность от моря (до 300 м), удаленность от магазинов (рядом), удаленность от дискотек и других источников шума (подальше, тишина в течение сна в отеле), питание (шведский стол - завтрак, ужин, частота изменения меню за неделю), отели (Princes, Marlin-In, Hour-Palace), экскурсии (Каир, Луксор, коралловые острова, подводное плавание), увеселительные шоу, спортивные игры, цена путевки, форма оплаты, содержание страховки, что брать с собой, что купить на месте, гарантии, штрафные санкции.
Есть еще один очень существенный показатель, выгодный для клиента, установить который предлагается самостоятельно въедливому читателю. Затем можно, используя метод опарного сравнения перечисленных характеристик х i , сформировать матрицу п х п сравнения, элементы которой заполняются последовательно по строкам по следующему правилу:
0, если характеристика менее значима,
а ij = 1, если характеристика равнозначима,
2, если характеристика доминирует.
После этого определяются значения сумм оценок по каждому показателю строки S i =∑a ij , вес каждой характеристики M i = S i /n 2 и соответственно интегральный критерий, на основе которого можно провести выбор турфирмы, тура или отеля, по формуле
F = ∑ M i * x i -» max.
С целью исключения возможных ошибок в этой процедуре вводят, например, 5-балльную шкалу оценок с градацией характеристик Б i (х i) по принципу хуже (Б i = 1 балл) - лучше (Б i = 5 баллов). Например, чем дороже тур, тем хуже, чем он дешевле, тем лучше. На этом основании целевая функция будет иметь другой вид:
F b = ∑ M i * Б i * x i -> max.
Таким образом, можно на основе применения математических методов и моделей, используя преимущества формализации, точнее и более объективно сформулировать постановку задач и значительно улучшить показатели СМО в коммерческой деятельности для достижения поставленных целей.
3.4 Одноканальная СМО с ограниченной длиной очереди
В коммерческой деятельности чаще встречаются СМО с ожиданием (очередью).
Рассмотрим простую одноканальную СМО с ограниченной очередью, в которой число мест в очереди т - фиксированная величина. Следовательно, заявка, поступившая в тот момент, когда все места в очереди заняты, не принимается к обслуживанию, не встает в очередь и.покидает систему.
Граф этой СМО представлен на рис. 3.4 и совпадает с графом рис. 2.1 описывающим процесс «рождения-гибели», с тем отличием, что при наличии только одного канала.
|
|
|
|
|
μ μμμ... μ
Рис. 3.4. Размеченный граф процесса «рождения - гибели» обслуживания все интенсивности потоков обслуживания равны
Состояния СМО можно представить следующим образом:
S 0 - канал обслуживания свободен,
S, - канал обслуживания занят, но очереди нет,
S 2 - канал обслуживания занят, в очереди стоит одна заявка,
S 3 - канал обслуживания занят, в очереди стоят две заявки,
S m +1 - канал обслуживания занят, в очереди все т мест заняты, любая следующая заявка получает отказ.
Для описания случайного процесса СМО можно воспользоваться изложенными ранее правилами и формулами. Напишем выражения, определяющие предельные вероятности состояний:
p 1 = ρ * ρ о
p 2 =ρ 2 * ρ 0
p k =ρ k * ρ 0
P m+1 = p m=1 * ρ 0
p 0 = -1
Выражение для р 0 можно в аанном случае записать проще, пользуясь тем, что в знаменателе стоит геометрическая прогрессия относительно р, тогда после соответствующих преобразований получаем:
ρ= (1- ρ )
Эта формула справедлива для всех р, отличных от 1, если же р = 1, то р 0 = 1/(т + 2), а все остальные вероятности также равны 1/(т + 2). Если предположить т = 0, то мы переходим от рассмотрения одноканальной СМО с ожиданием к уже рассмотренной одноканальной СМО с отказами в обслуживании. Действительно, выражение для предельной вероятности р 0 в случае т = 0 имеет вид:
p о = μ / (λ+μ)
И в случае λ = μ имеет величину р 0 = 1 / 2.
Определим основные характеристики одноканальной СМО с ожиданием: относительную и абсолютную пропускную способность, вероятность отказа, а также среднюю длину очереди и среднее время ожидания заявки в очереди.
Заявка получает отказ, если она поступает в момент времени, когда СМО уже находится в состоянии S m +1 и, следовательно, все места в очереди да заняты и один канал обслуживает Поэтому вероятность отказа определяется вероятностью появлением
Состояния S m +1:
P отк = p m +1 = ρ m +1 * p 0
Относительная пропускная способность, или доля обслуживаемых заявок, поступающих в единицу времени, определяется выражением
Q = 1- p отк = 1- ρ m+1 * p 0
абсолютная пропускная способность равна:
Среднее число заявок L оч стоящих в очереди на обслуживание, определяется математическим ожиданием случайной величины к - числа заявок, стоящих в очереди
случайная величина кпринимает следующие только целочисленные значения:
1 - в очереди стоит одна заявка,
2 - в очереди две заявки,
т-в очереди все места заняты
Вероятности этих значений определяются соответствующими вероятностями состояний, начиная с состояния S 2 . Закон распределения дискретной случайной величины к изображается следующим образом:
| k | 1 | 2 | m |
| p i | p 2 | p 3 | p m+1 |
Математическое ожидание этой случайной величины равно:
L оч = 1* p 2 +2* p 3 +...+ m* p m +1
В общем случае при p ≠1 эту сумму можно преобразовать, пользуясь моделями геометрической прогрессии, к более удобному виду:
L оч = p 2 * 1- p m * (m-m*p+1) * p 0
В частном случае при р = 1, когда все вероятности p k оказываются равными, можно воспользоваться выражением для суммы членов числового ряда
1+2+3+ m = m ( m +1)
Тогда получим формулу
L’ оч = m(m+1) * p 0 = m(m+1) (p=1).
Применяя аналогичные рассуждения и преобразования, можно показать, что среднее время ожидания обслуживания заявки а очереди определяется формулами Литтла
Т оч = L оч /А (при р ≠ 1) и Т 1 оч = L’ оч /А(при р = 1).
Такой результат, когда оказывается, что Т оч ~ 1/ λ, может показаться странным: с увеличением интенсивности потока заявок как будто бы должна возрастать длина очереди и уменьшается среднее время ожидания. Однако следует иметь в виду, что, во-первых, величина L оч является функцией от λ и μ и, во-вторых, рассматриваемая СМО имеет ограниченную длину очереди не более mзаявок.
Заявка, поступившая в СМО в момент времени, когда все каналы заняты, получает отказ, и, следовательно, время ее «ожидания» в СМО равно нулю. Это приводит в общем случае (при р ≠ 1) к уменьшению Т оч ростом λ, поскольку доля таких заявок с ростом λ увеличивается.
Если отказаться от ограничения на длину очереди, т.е. устремить m-> →∞, то случаи р < 1 и р ≥1 начинают существенно различаться. Записанные выше формулы для вероятностей состояний преобразуются в случае р < 1 к виду
p k =р k *(1 - р)
При достаточно большом к вероятность p k стремится к нулю. Поэтому относительная пропускная способность будет Q= 1, а абсолютная пропускная способность станет равной А -λ Q - λ следовательно, обслуживаются все поступившие заявки, причем средняя длина очереди окажется равной:
L оч =p 2 1-p
а среднее время ожидания по формуле Литтла
Т оч = L оч /А
В пределе р << 1 получаем Т оч = ρ / μт.е. среднее время ожидания быстро уменьшается с увеличением интенсивности потока обслуживания. В противном случае при р ≥ 1 оказывается, что в СМО отсутствует установившийся режим. Обслуживание не успевает за потоком заявок, и очередь неограниченно растет со временем (при t → ∞). Предельные вероятности состояний поэтому не могут быть определены: при Q= 1 они равны нулю. Фактически СМО не выполняет своих функций, поскольку она не в состоянии обслужить все поступающие заявки. Нетрудно определить, что доля обслуживаемых заявок и абсолютная пропускная способность соответственно составляют в среднем ρ и μ, однако неограниченное увеличение очереди, а следовательно, и времени ожидания в ней приводит к тому, что через некоторое время заявки начинают накапливаться в очереди на неограниченно долгое время.
В качестве одной из характеристик СМО используют среднее время Т смо пребывания заявки в СМО, включающее среднее время пребывания в очереди и среднее время обслуживания. Эта величина вычисляется по формулам Литтла: если длина очереди ограничена - среднее число заявок, находящихся в очереди, равно:
L смо= m +1 ;2
Т смо= L смо; при p ≠1
Aтогда среднее время пребывания заявки в системе массового обслуживания (как в очереди, так и под обслуживанием) равно:
Т смо= m +1 при p ≠1 2μ
3.5 Одноканальная СМО с неограниченной очередью
В коммерческой деятельности в качестве одноканальной СМО с неограниченным ожиданием является, например, коммерческий директор, поскольку он, как правило, вынужден выполнять обслуживание заявок различной природы: документы, переговоры по телефону, встречи и беседы с подчиненными, представителями налоговой инспекции, милиции, товароведами, маркетологами, поставщиками продукции и решать задачи в товарно-финансовой сфере с высокой степенью финансовой ответственности, что связано с обязательным выполнением запросов, которые ожидают иногда нетерпеливо выполнения своих требований, а ошибки неправильного обслуживания, как правило, экономически весьма ощутимы.
В то же время товары, завезенные для продажи (обслуживания), находясь на складе, образуют очередь на обслуживание (продажу).
Длину очереди составляет количество товаров, предназначенных для продажи. В этой ситуации продавцы выступают в роли каналов, обслуживающих товары. Если количество товаров, предназначенных для продажи, велико, то в этом случае мы имеем дело с типичным случаем СМО с ожиданием.
Рассмотрим простейшую одноканальную СМО с ожиданием обслуживания, на которую поступает пуассоновский поток заявок с интенсивностью λ и интенсивностью обслуживания µ.
Причем заявка, поступившая в момент, когда канал занят обслуживанием, ставится в очередь и ожидает обслуживания.
Размеченный граф состояний такой системы приведен на рис. 3.5
Количество возможных состояний ее бесконечно:
Канал свободен, очереди нет, ;
Канал занят обслуживанием, очереди нет, ;
Канал занят, одна заявка в очереди, ;
Канал занят , заявка в очереди.
Модели оценки вероятности состояний СМО с неограниченной очередью можно получить из формул, выделенных для СМО с неограниченной очередью, путем перехода к пределу при m→∞:
Рис. 3.5 Граф состояний одноканальной СМО с неограниченной очередью.
Следует заметить, что для СМО с ограниченной длиной очереди в формуле
имеет место геометрическая прогрессия с первым членом 1 и знаменателем . Такая последовательность представляет собой сумму бесконечного числа членов при . Эта сумма сходится, если прогрессия, бесконечно убывающая при , что определяет установившийся режим работы СМО, с при очередь при с течением времени может расти до бесконечности.
Поскольку в рассматриваемой СМО ограничение на длину очереди отсутствует, то любая заявка может быть обслужена, поэтому , следовательно, относительная пропускная способность , соответственно , а абсолютная пропускная способность
Вероятность пребывания в очереди k заявок равна:
;
Среднее число заявок в очереди –
Среднее число заявок в системе –
;
Среднее время пребывания заявки в системе –
;
Среднее время пребывания заявки с системе –
.
Если в одноканальной СМО с ожиданием интенсивность поступления заявок больше интенсивности обслуживания , то очередь будет постоянно увеличиваться. В связи с этим наибольший интерес представляет анализ устойчивых СМО, работающих в стационарном режиме при .
3.6 Многоканальная СМО с ограниченной длиной очереди
Рассмотрим многоканальную СМО , на вход которой поступает пуассоновский поток заявок с интенсивностью , а интенсивность обслуживания каждого канала составляет , максимально возможное число мест в очереди ограничено величиной m. Дискретные состояния СМО определяются количеством заявок, поступивших в систему, которые можно записать.
Все каналы свободны, ;
Занят только один канал (любой), ;
Заняты только два канала (любых), ;
Заняты все каналов, .
Пока СМО находится в любом из этих состояний, очереди нет. После того как заняты все каналы обслуживания, последующие заявки образуют очередь, тем самым, определяя дальнейшие состояние системы:
Заняты все каналов и одна заявка стоит в очереди,
Заняты все каналов и две заявки стоят в очереди,
Заняты все каналов и все мест в очереди,
Граф состояний n-канальной СМО с очередью, ограниченной m местами на рис.3.6
Рис. 3.6 Граф состояний n-канальной СМО с ограничением на длину очереди m
Переход СМО в состояние с большими номерами определяется потоком поступающих заявок с интенсивностью , тогда как по условию в обслуживании этих заявок принимают участие одинаковых каналов с интенсивностью потока обслуживания равного для каждого канала. При этом полная интенсивность потока обслуживания возрастает с подключением новых каналов вплоть до такого состояния , когда все n каналов окажутся занятыми. С появлением очереди интенсивность обслуживания более увеличивается, так как она уже достигла максимального значения, равного .
Запишем выражения для предельных вероятностей состояний:
Выражение для можно преобразовать, используя формулу геометрической прогрессии для суммы членов со знаменателем :
Образование очереди возможно, когда вновь поступившая заявка застанет в системе не менее требований, т.е. когда в системе будет находиться требований. Эти события независимы, поэтому вероятность того, что все каналы заняты, равна сумме соответствующих вероятностей Поэтому вероятность образования очереди равна:
Вероятность отказа в обслуживании наступает тогда, когда все каналов и все мест в очереди заняты:
Относительная пропускная способность будет равна:
Абсолютная пропускная способность –
Среднее число занятых каналов –
Среднее число простаивающих каналов –
Коэффициент занятости (использования) каналов –
Коэффициент простоя каналов –
Среднее число заявок, находящихся в очередях –
В случае если , эта формула принимает другой вид –
Среднее время ожидания в очереди определяется формулами Литтла –
Среднее время пребывания заявки в СМО, как и для одноканальной СМО, больше среднего времени ожидания в очереди на среднее время обслуживания, равное , поскольку заявка всегда обслуживается только одним каналом:
3.7 Многоканальная СМО с неограниченной очередью
Рассмотрим многоканальную СМО с ожиданием и неограниченной длиной очереди, на которую поступает поток заявок с интенсивностью и которая имеет интенсивность обслуживания каждого канала . Размеченный граф состояний представлен на рис 3.7 Он имеет бесконечное число состояний:
S - все каналы свободны, k=0;
S - занят один канал, остальные свободны, k=1;
S - заняты два канала, остальные свободны, k=2;
S - заняты все n каналов, k=n, очереди нет;
S - заняты все n каналов, одна заявка в очереди, k=n+1,
S - заняты все n каналов, r заявок в очереди, k=n+r,
Вероятности состояний получим из формул для многоканальной СМО с ограниченной очередью при переходе к пределу при m. Следует заметить, что сумма геометрической прогрессии в выражении для p расходится при уровне загрузки p/n>1, очередь будет бесконечно возрастать, а при p/n<1 ряд сходится, что определяет установившийся стационарный режим работы СМО.
Очереди нет
| … | … |
Рис.3.7 Размеченный граф состояний многоканальной СМО
с неограниченной очередью
для которого и определим выражения для предельных вероятностей состояний:
Поскольку отказа в обслуживании в таких системах не может быть, то характеристики пропускной способности равны:
среднее число заявок в очереди –
среднее время ожидания в очереди –
среднее число заявок в СМО –
Вероятность того, что СМО находится в состоянии , когда нет заявок и не занято ни одного канала, определяется выражением
Эта вероятность определяет среднюю долю времени простоя канала обслуживания. Вероятность занятости обслуживанием k заявок –
На этом основании можно определить вероятность, или долю времени занятости всех каналов обслуживанием
Если же все каналы уже заняты обслуживанием, то вероятность состояния определяется выражением
Вероятность оказаться в очереди равна вероятности застать все каналы уже занятыми обслуживанием
Среднее число заявок, находящихся в очереди и ожидающих обслуживания, равно:
Среднее время ожидания заявки в очереди по формуле Литтла: и в системе
среднее число занятых каналов обслуживанием:
среднее число свободных каналов:
коэффициент занятости каналов обслуживанием:
Важно заметить, что параметр характеризует степень согласования входного потока, например покупателей в магазине с интенсивностью потока обслуживания. Процесс обслуживания будет стабилен при Если же в системе будут возрастать средняя длина очереди и среднее время ожидания покупателями начала обслуживания и, следовательно, СМО будет работать неустойчиво.
3.8 Анализ системы массового обслуживания супермаркета
Одной из важных задач коммерческой деятельности является рациональная организация торгово-технологического процесса массового обслуживания, например в универсаме. В частности, определение мощности кассового узла торгового предприятия является непростой задачей. Такие экономико-организационные показатели, как нагрузка товарооборота на 1м 2 торговой площади, пропускная способность предприятия, время пребывания покупателей в магазине, а также показатели уровня технологического решения торгового зала: соотношение площадей зон самообслуживания и расчетного узла, коэффициенты установочной и выставочной площадей, во многом определяются пропускной способностью кассового узла. В этом случае пропускную способность двух зон (фаз) обслуживания: зоны самообслуживания и зоны расчетного узла (рис.4.1).
| СМО | СМО |
Интенсивность входного потока покупателей;
Интенсивность прихода покупателей зоны самообслуживания;
Интенсивность прихода покупателей в расчетный узел;
Интенсивность потока обслуживания.
Рис.4.1. Модель двухфазной СМО торгового зала универсама
Основная функция расчетного узла состоит в обеспечении высокой пропускной способности покупателей в торговом зале и создании комфортного обслуживания покупателей. Факторы, влияющие на пропускную способность расчетного узла, можно разделить на две группы:
1) экономико-организационные факторы: система материальной ответственности в универсаме; средняя стоимость и структура одной покупки;
2) организационная структура кассового узла;
3) технико-технологические факторы: применяемые типы кассовых аппаратов и кассовых кабин; применяемая контролером-кассиром технология обслуживания покупателей; соответствие мощности кассового узла интенсивности покупательских потоков.
Из перечисленных групп факторов наибольшее влияние оказывают организационное построение кассового узла и соответствие мощности кассового узла интенсивности покупательских потоков.
Рассмотрим обе фазы системы обслуживания:
1) выбор покупателями товаров в зоне самообслуживания;
2) обслуживание покупателей в зоне расчетного узла. Входящий поток покупателей попадает в фазу самообслуживания, и покупатель самостоятельно отбирает нужные ему товарные единицы, формируя их в единую покупку. Причем время этой фазы зависит от того, как взаиморазмещены товарные зоны, какой фронт они имеют, сколько времени тратит покупатель на выбор конкретного товара, какова структура покупки и т.д.
Выходящий поток покупателей из зоны самообслуживания одновременно является входящим потоком в зону кассового узла, который последовательно включает ожидание покупателя в очереди и затем обслуживание его контролером-кассиром. Кассовый узел можно рассматривать как систему обслуживания с потерями или как систему обслуживания с ожиданием.
Однако ни первая, ни вторая рассмотренные системы не позволяют реально описать процесс обслуживания в кассовом узле универсама по следующим причинам:
в первом варианте кассовый узел, мощность которого будет рассчитана на систему с потерями, требует значительных как капитальных вложений, так и текущих затрат на содержание контролеров-кассиров;
во втором варианте кассовый узел, мощность которого будет рассчитана на систему с ожиданиями, приводит к большим затратам времени покупателей в ожидании обслуживания. При этом в часы пик зона расчетного узла «переполняется» и очередь покупателей «перетекает» в зону самообслуживания, что нарушает нормальные условия для выбора товара другими покупателями.
В связи с этим целесообразно рассматривать вторую фазу обслуживания как систему с ограниченной очереди, промежуточную между системой с ожиданием и системой с потерями. При этом предполагается, что одновременно в системе могут находиться не более L, причем L=n+m, где n-количество обслуживаемых клиентов в кассах, m-количество покупателей, стоящих в очереди, причем любая m+1- заявка покидает систему необслуженной.
Это условие позволяет, с одной стороны, ограничить площадь зоны расчетного узла с учетом максимально допустимой длины очереди, а с другой – ввести ограничение на время ожидания покупателями обслуживания в кассовом узле, т.е. учитывать издержки потребления покупателей.
Правомерность постановки задачи в таком виде подтверждается проведенными обследованиями потоков покупателей в универсамах, результаты которых приведены в табл. 4.1, анализ которых выявил тесную связь между средней длинной очереди в кассовом узле и количеством покупателей, не совершивших покупок.
| Часы работы | День недели | ||||||||
| пятница | суббота | воскресенье | |||||||
оче-редь, |
количество покупателей без покупок |
оче-редь, |
количество покупателей без покупок |
оче-редь, |
количество покупателей без покупок |
||||
| чел. | % | чел. | % | чел. | % | ||||
| с 9 до 10 | 2 | 38 | 5 | 5 | 60 | 5,4 | 7 | 64 | 4,2 |
| с 10 до 11 | 3 | 44 | 5,3 | 5 | 67 | 5 | 6 | 62 | 3,7 |
| с 11 до 12 | 3 | 54 | 6,5 | 4 | 60 | 5,8 | 7 | 121 | 8,8 |
| с 12 до 13 | 2 | 43 | 4,9 | 4 | 63 | 5,5 | 8 | 156 | 10 |
| с 14 до 15 | 2 | 48 | 5,5 | 6 | 79 | 6,7 | 7 | 125 | 6,5 |
| с 15 до 16 | 3 | 61 | 7,3 | 6 | 97 | 6,4 | 5 | 85 | 7,2 |
| с 16 до 17 | 4 | 77 | 7,1 | 8 | 140 | 9,7 | 5 | 76 | 6 |
| с 17 до 18 | 5 | 91 | 6,8 | 7 | 92 | 8,4 | 4 | 83 | 7,2 |
| с 18 до 19 | 5 | 130 | 7,3 | 6 | 88 | 5,9 | 7 | 132 | 8 |
| с 19 до 20 | 6 | 105 | 7,6 | 6 | 77 | 6 | |||
| с 20 до 21 | 6 | 58 | 7 | 5 | 39 | 4,4 | |||
| Итого | 749 | 6,5 | 862 | 6,3 | 904 | 4,5 | |||
В организации работы кассового узла универсама имеется еще одна важная особенность, которая значительно влияет на его пропускную способность: наличие экспресс-касс (одной-двух покупок). Изучение структуры потока покупателей в универсамах по типу кассового обслуживания показывает, что поток оборот составляет 12,9% (табл. 4.2).
| Дни недели | Потоки покупателей | Товарооборот | ||||
| всего | по экспресс-кассам | % к дневномупотоку | всего | по экспресс-кассам | % к дневному товарообороту | |
| Летний период | ||||||
| Понедельник | 11182 | 3856 | 34,5 | 39669,2 | 3128,39 | 7,9 |
| Вторник | 10207 | 1627 | 15,9 | 38526,6 | 1842,25 | 4,8 |
| Среда | 10175 | 2435 | 24 | 33945 | 2047,37 | 6 |
| Четверг | 10318 | 2202 | 21,3 | 36355,6 | 1778,9 | 4,9 |
| Пятница | 11377 | 2469 | 21,7 | 43250,9 | 5572,46 | 12,9 |
| Суббота | 10962 | 1561 | 14,2 | 39873 | 1307,62 | 3,3 |
| Воскресенье | 10894 | 2043 | 18,8 | 35237,6 | 1883,38 | 5,1 |
| Зимний период | ||||||
| Понедельник | 10269 | 1857 | 18,1 | 37121,6 | 2429,73 | 6,5 |
| Вторник | 10784 | 1665 | 15,4 | 38460,9 | 1950,41 | 5,1 |
| Среда | 11167 | 3729 | 33,4 | 39440,3 | 4912,99 | 12,49,4 |
| Четверг | 11521 | 2451 | 21,3 | 40000,7 | 3764,58 | 9,4 |
| Пятница | 11485 | 1878 | 16,4 | 43669,5 | 2900,73 | 6,6 |
| Суббота | 13689 | 2498 | 18,2 | 52336,9 | 4752,77 | 9,1 |
| Воскресенье | 13436 | 4471 | 33,3 | 47679,9 | 6051,93 | 12,7 |
Для окончательного построение математической модели процесса обслуживания с учетом перечисленных выше факторов необходимо определить функции распределения случайных величин, а также случайные процессы, описывающие входящие и выходящие потоки покупателей:
1) функцию распределения времени покупателей на выбор товаров в зоне самообслуживания;
2) функцию распределения времени работы контролера-кассира для обычных касс и экспресс-касс;
3) случайный процесс, описывающий входящий поток покупателей в первую фазу обслуживания;
4) случайный процесс, описывающий входящий поток во вторую фазу обслуживания для обычных касс и экспресс-касс.
Моделями для расчета характеристик системы массового обслуживания удобно пользоваться в том случае, если входящий поток требований в систему обслуживания является простейшим пуассоновским потоком, а время обслуживания заявок распределено по экспоненциальному закону.
Исследование потока покупателей в зоне кассового узла показало, что для него может быть принят пуассоновский поток.
Функция распределения времени обслуживания покупателей контролерами-кассирами является экспоненциальной, такое допущение не приводит к большим ошибкам.
Безусловный интерес представляет анализ характеристик обслуживания потока покупателей в кассовом узле универсама, рассчитанных для трех систем: с потерями, с ожиданием и смешанного типа.
Расчеты параметров процесса обслуживания покупателей в кассовом узле проведены для коммерческого предприятия торговой площадью S=650на основе следующих данных.
Целевая функция может быть записана в общем виде связи (критерия) выручки от реализации от характеристик СМО:
где - кассовый узел состоит из =7 касс обычного типа и =2 экспресс-касс,
Интенсивность обслуживания покупателей в зоне обычных касс – 0,823 чел./мин;
Интенсивность нагрузки кассовых аппаратов в зоне обычных касс – 6,65,
Интенсивность обслуживания покупателей в зоне экспресс-касс – 2,18 чел./мин;
Интенсивность входящего потока в зону обычных касс – 5,47 чел./мин
Интенсивность нагрузки кассовых аппаратов в зоне экспресс-касс – 1,63,
Интенсивность входящего потока в зону экспресс-касс – 3,55 чел./мин;
Для модели СМО с ограничением на длину очереди в соответствии с проектируемой зоной кассового узла максимально допустимое число покупателей, стоящих в очереди в одну кассу, принимается равным m=10 покупателей.
Следует заметить, что для получения сравнительно небольших по абсолютной величине значений вероятности потерь заявок и времени ожидания покупателей в кассовом узле необходимо соблюдать следующие условия: 
В табл.6.6.3 приведены результаты характеристик качества функционирования СМО в зоне расчетного узла.
Расчеты проведены для наиболее напряженного периода времени рабочего дня с 17 до 21 часа. Именно на этот период, как показали результаты обследований, приходится около 50% однодневного потока покупателей.
Из приведенных данных в табл. 4.3 следует, что если бы для расчета была выбрана:
1) модель с отказами, то 22,6% потока покупателей, обслуживаемых обычными кассами, и соответственно 33,6% потока покупателей, обслуживаемых экспресс-кассами, должны были бы уйти без покупок;
2) модель с ожиданием, то потерь заявок в расчетном узле не должно бы быть;
Табл. 4.3 Характеристики системы массового обслуживания покупателей в зоне расчетного узла
| Тип кассы | Количество касс в узле | Тип СМО | Характеристики СМО | ||
| Среднее число занятых касс, | среднее время ожидания обслуживания, | Вероятность потери заявок, | |||
| Обычные кассы | 7 | с отказами с ожиданием с ограничением |
|||
| Экспресс-кассы | 2 | с отказами с ожиданием с ограничением |
|||
3) модель с ограничением на длину очереди, то только 0,12% потока покупателей, обслуживаемых обычными кассами, и 1,8% потока покупателей, обслуживаемых экспресс-кассами, покинут торговый зал без покупок. Следовательно, модель с ограничением на длину очереди позволяет более точно и реально описать процесс обслуживания покупателей в зоне кассового узла.
Интерес представляет сравнительный расчет мощности кассового узла как с учетом экспресс-касс, так и без них. В табл. 4.4 приведены характеристики системы обслуживания кассового узла трех типоразмеров универсамов, рассчитанные по моделям для СМО с ограничением на длину очереди на наиболее напряженный период рабочего дня с 17 до 21 часа.
Анализ данных этой таблицы показывает, что не учет фактора «Структура потока покупателей по типу кассового обслуживания» на стадии технологического проектирования может привести к увеличению зоны расчетного узла на 22-33%, а отсюда соответственно и к уменьшению установочных и выставочных площадей торгово-технологического оборудования и товарной массы, размещаемой в торговом зале.
Проблема определения мощности кассового узла представляет собой цепочку взаимосвязанных характеристик. Так, увеличение его мощности сокращает время покупателей на ожидание обслуживания, уменьшает вероятность потери требований и, следовательно, потери товарооборота. Наряду с этим необходимо соответственно уменьшить зону самообслуживания, фронт торгово-технологического оборудования, товарную массу в торговом зале. В то же время увеличивается затраты на заработную плату контролеров-кассиров и оборудование дополнительных рабочих мест. Поэтому
| № п/п | Характеристики СМО | Единица измерения | Обозначение | Показатели, рассчитанные по типам универсамов торговой площади, кв. м | ||||||||||||||||
| Без экспресс-касс | С учетом экспресс-касс | |||||||||||||||||||
| 650 | 1000 | 2000 | 650 | 1000 | 2000 | |||||||||||||||
| Обычные кассы | Экспресс-кассы | Обычные кассы | экспресс-кассы | Обычные кассы | экспресс-кассы | |||||||||||||||
| 1 | Количество покупателей | чел. | k | 2310 | 3340 | 6680 | 1460 | 850 | 2040 | 1300 | 4080 | 2600 | ||||||||
| 2 | Интенсивность входящего потока | λ | 9,64 | 13,9 | 27,9 | 6,08 | 3,55 | 8,55 | 5,41 | 17,1 | 10,8 | |||||||||
| 3 | Интенсивность обслуживания | чел./мин | μ | 0,823 | 0,823 | 0,823 | 0,823 | 2,18 | 0,823 | 2,18 | 0,823 | 2,18 | ||||||||
| 4 | Интенсивность нагрузки | - | ρ | 11,7 | 16,95 | 33,8 | 6,65 | 1,63 | 10,35 | 2,48 | 20,7 | 4,95 | ||||||||
| 5 | Количество кассовых аппаратов | шт. | n | 12 | 17 | 34 | 7 | 2 | 11 | 3 | 21 | 5 | ||||||||
| 6 | Общее количество касс расчетного узла | шт. | ∑n | 12 | 17 | 34 | 9 | 14 | 26 | |||||||||||
необходимо проводить оптимизационные расчеты. Рассмотрим характеристики системы обслуживания в кассовом узле универсама торговой площади 650м, рассчитанные по моделям СМО с ограниченной длиной очереди для различных мощностей его кассового узла в табл. 4.5.
На основе анализа данных табл. 4.5 можно сделать вывод, что по мере увеличения количества касс время ожидания покупателей в очереди растет, а затем после определенного момента резко падает. Характер изменения графика времени ожидания покупателей понятен, если параллельно рассматривать изменение вероятности потери требования Вполне очевидно, что когда мощность кассового узла чрезмерно мала, то более 85% покупателей будут уходить необслуженными, а оставшаяся часть покупателей будет обслужена за очень короткое время. Чем больше мощность кассового узла, тем вероятность потери требований будет дожидаться своего обслуживания, а значит, и время их ожидания в очереди соответственно будет расти. После того как ожидания и вероятность потерь будут резко уменьшаться.
Для универсама торговой площадью 650 этот предел для зоны обычных касс лежит между 6 и 7 кассовыми аппаратами. При 7 кассовых аппаратах соответственно среднее время ожидания – 2,66 мин, а вероятность потери заявок очень мала – 0,1%. Таким образом, которая позволит получить минимальные совокупные затраты на массовое обслуживание покупателей.
| Тип кассового обслуживания | Количество кассовых аппаратов в узле n, шт. | Характеристики системы обслуживания | Средняя выручка за 1 ч. руб. | Средняя потеря выручки за 1 ч. руб | Число покупателей в зоне расчетного узла | Площадь зоны расчетного узла, Sy, м | Удель ный вес площади зоны узла 650/ Sy | |
| Среднее время ожидания, Т,мин | Вероятность потери заявок | |||||||
| Зоны Обычных касс | ||||||||
| Зоны экспресс-касс | ||||||||
Заключение
На основе анализа данных табл. 4.5 можно сделать вывод, что по мере увеличения количество касс время ожидания покупателей в очереди растет. А затем после определенного момента резко падает. Характер изменения графика времени ожидания покупателей понятен, если параллельно рассматривать изменение вероятности потери требований Вполне очевидно, что когда мощность кассового узла чрезмерно мала, то более 85% покупателей будут уходить необслуженными, а оставшаяся часть покупателей будет обслужена за очень короткое время. Чем больше мощность кассового узла. Тем вероятность потери требований будет уменьшаться и соответственно тем большее число покупателей будет дожидаться своего обслуживания, а значит, и время их ожидания в очереди соответственно будет расти. После того как расчетный узел превысит оптимальный мощность, время ожидания и вероятность потерь будут резко уменьшаться.
Для универсама торговой площадью 650 кв. метров этот предел для зоны обычных касс лежит между 6-8 кассовыми аппаратами. При 7 кассовых аппаратах соответственно среднее время ожидания- 2,66 мин, а вероятность потери заявок очень мало - 0,1 % . Таким образом, задача состоит в выборе такой мощности кассового узла, которая позволит получит минимальные совокупные затраты на массовое обслуживание покупателей.
В связи с этим следующим этапом решения поставленной задачи является оптимизация мощности кассового узла на базе применения моделей СМО разных типов с учетом совокупных затрат и перечисленных выше факторов.
Примеры решения задач систем массового обслуживания
Требуется решить задачи 1–3. Исходные данные приведены в табл. 2–4.
Некоторые обозначения, применяемые в теории массового обслуживания, для формул:
n – число каналов в СМО;
λ – интенсивность входящего потока заявок П вх;
v – интенсивность выходящего потока заявок П вых;
μ – интенсивность потока обслуживания П об;
ρ – показатель нагрузки системы (трафик);
m – максимальное число мест в очереди, ограничивающее длину очереди заявок;
i – число источников заявок;
p к – вероятность k-го состояния системы;
p о – вероятность простаивания всей системы, т. е. вероятность того, что все каналы свободны;
p сист – вероятность принятия заявки в систему;
p отк – вероятность отказа заявке в принятии ее в систему;
р об – вероятность того, что заявка будет обслужена;
А – абсолютная пропускная способность системы;
Q – относительная пропускная способность системы;
Оч – среднее число заявок в очереди;
Об – среднее число заявок под обслуживанием;
Сист – среднее число заявок в системе;
Оч – среднее время ожидания заявки в очереди;
Об – среднее время обслуживания заявки, относящееся только к обслуженным заявкам;
Сис – среднее время пребывания заявки в системе;
Ож – среднее время, ограничивающее ожидание заявки в очереди;
– среднее число занятых каналов.
Абсолютная пропускная способность СМО А – среднее число заявок, которое может обслужить система за единицу времени.
Относительная пропускная способность СМО Q – отношение среднего числа заявок, обслуживаемых системой в единицу времени, к среднему числу поступающих за это время заявок.
При решении задач массового обслуживания необходимо придерживаться нижеприведенной последовательности:
1) определение типа СМО по табл. 4.1;
2) выбор формул в соответствии с типом СМО;
3) решение задачи;
4) формулирование выводов по задаче.
1.Схема гибели и размножения. Мы знаем, что, имея в распоряжении размеченный граф состояний, можно легко написать уравнения Колмогорова для вероятностей состояний, а также написать и решить алгебраические уравнения для финальных вероятностей. Для некоторых случаев удается последние уравнения
решить заранее, в буквенном виде. В частности, это удается сделать, если граф состояний системы представляет собой так называемую «схему гибели и размножения».
Граф состояний для схемы гибели и размножения имеет вид, показанный на рис. 19.1. Особенность этого графа в том, что все состояния системы можно вытянуть в одну цепочку, в которой каждое из средних состояний (S 1 , S 2 ,…,S n-1) связано прямой и обратной стрелкой с каждым из соседних состояний - правым и левым, а крайние состояния (S 0 , S n) - только с одним соседним состоянием. Термин «схема гибели и размножения» ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции.
Схема гибели и размножения очень часто встречается в разных задачах практики, в частности - в теории массового обслуживания, поэтому полезно, один раз и навсегда, найти для нее финальные вероятности состояний.
Предположим, что все потоки событии, переводящие систему по стрелкам графа,- простейшие (для краткости будем называть и систему S и протекающий в ней процесс - простейшими).
Пользуясь графом рис. 19.1, составим и решим алгебраические уравнения для финальных вероятностей состоянии), существование вытекает из того, что из каждого состояния можно перейти в каждое другое, в число состояний конечно). Для первого состояния S 0 имеем:
(19.1)
Для второго состояния S 1:
В силу (19.1) последнее равенство приводится к виду
где k принимает все значения от 0 до п. Итак, финальные вероятности p 0 , p 1 , ..., р n удовлетворяют уравнениям
(19.2)
кроме того, надо учесть нормировочное условие
p 0 + p 1 + p 2 +…+ p n =1. (19.3)
Решим эту систему уравнений. Из первого уравнения (19.2)выразим p 1 через р 0 :
p 1 = p 0. (19.4)
Из второго, с учетом (19.4), получим:
(19.5)
Из третьего, с учетом (19.5),
(19.6)
и вообще, для любого k (от 1 до n ):
(19.7)
Обратим внимание на формулу (19.7). В числителе стоит произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо (с начала и до данного состояния S k), а в знаменателе - произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево (с начала и до S k).
Таким образом, все вероятности состояний р 0 , p 1 , ..., р n выражены через одну из них (р 0). Подставим эти выражения в нормировочное условие (19.3). Получим, вынося за скобку р 0:
отсюда получим выражение для р 0 :
(скобку мы возвели в степень -1, чтобы не писать двухэтажных дробей). Все остальные вероятности выражены через р 0 (см. формулы (19.4) - (19.7)). Заметим, что коэффициенты при р 0 в каждой из них представляют собой не что иное, как последовательные члены ряда, стоящего после единицы в формуле (19.8). Значит, вычисляя р 0 , мы уже нашли все эти коэффициенты.
Полученные формулы очень полезны при решении простейших задач теории массового обслуживания.
^ 2. Формула Литтла. Теперь мы выведем одну важную формулу, связывающую (для предельного, стационарного режима) среднее число заявок L сист, находящихся в системе массового обслуживания (т. е. обслуживаемых или стоящих в очереди), и среднее время пребывания заявки в системе W сист.
Рассмотрим любую СМО (одноканальную, многоканальную, марковскую, немарковскую, с неограниченной или с ограниченной очередью) и связанные с нею два потока событий: поток заявок, прибывающих в СМО, и поток заявок, покидающих СМО. Если в системе установился предельный, стационарный режим, то среднее число заявок, прибывающих в СМО за единицу времени, равно среднему числу заявок, покидающих ее: оба потока имеют одну и ту же интенсивность λ.
Обозначим: X(t} - число заявок, прибывших в СМО до момента t. Y (t ) - число заявок покинувших СМО
до момента t. И та, и другая функции являются случайными и меняются скачком (увеличиваются на единицу) в моменты приходов заявок (X (t )) и уходов заявок (Y(t)). Вид функций X(t) и Y(t) показан на рис. 19.2; обе линии - ступенчатые, верхняя - X(t), нижняя-Y(t). Очевидно, что для любого момента t их разность Z (t ) = X(t) - Y(t) есть не что иное, как число заявок, находящихся в СМО. Когда линии X(t) и Y(t) сливаются, в системе нет заявок.
Рассмотрим очень большой промежуток времени Т (мысленно продолжив график далеко за пределы чертежа) и вычислим для него среднее число заявок, находящихся в СМО. Оно будет равно интегралу от функции Z(t) на этом промежутке, деленному на длину интервала Т:
L сист. = . (19.9) о
Но этот интеграл представляет собой не что иное, как площадь фигуры, заштрихованной на рис. 19.2. Разглядим хорошенько этот рисунок. Фигура состоит из прямоугольников, каждый из которых имеет высоту, равную единице, и основание, равное времени пребывания в системе соответствующей заявки (первой, второй и т. д.). Обозначим эти времена t 1 , t 2 ,... Правда, под конец промежутка Т некоторые прямоугольники войдут в заштрихованную фигуру не полностью, а частично, но при достаточно большом Т эти мелочи не будут играть роли. Таким образом, можно считать, что
(19.10)
где сумма распространяется на все заявки, пришедшие за время Т.
Разделим правую и левую часть (.19.10) на длину интервала Т. Получим, с учетом (19.9),
L сист. = . (19.11)
Разделим и умножим правую часть (19.11) на интенсивность X:
L сист. = .
Но величина Тλ есть не что иное, как среднее число заявок, пришедших за время ^ Т. Если мы разделим сумму всех времен t i на среднее число заявок, то получим среднее время пребывания заявки в системе W сист. Итак,
L сист. = λW сист. ,
W сист. = . (19.12)
Это и есть замечательная формула Литтла: для любой СМО, при любом характере потока заявок, при любом распределении времени обслуживания, при любой дисциплине обслуживания среднее время пребывания заявки в системе равно среднему числу заявок в системе, деленному на интенсивность потока заявок.
Точно таким же образом выводится вторая формула Литтла, связывающая среднее время пребывания заявки в очереди ^ W оч и среднее число заявок в очереди L оч:
W оч = . (19.13)
Для вывода достаточно вместо нижней линии на рис. 19.2 взять функцию U(t) - количество заявок, ушедших до момента t не из системы, а из очереди (если заявка, пришедшая в систему, не становится в очередь, а сразу идет под обслуживание, можно все же считать, что она становится в очередь, но находится в ней нулевое время).
Формулы Литтла (19.12) и (19.13) играют большую роль в теории массового обслуживания. К сожалению, в большинстве существующих руководств эти формулы (доказанные в общем виде сравнительно недавно) не приводятся 1).
§ 20. Простейшие системы массового обслуживания и их характеристики
В этом параграфе мы рассмотрим, некоторые простейшие СМО и выведем выражения для их характеристик (показателей эффективности). При этом мы продемонстрируем основные методические приемы, характерные для элементарной, «марковской» теории массового обслуживания. Мы не будем гнаться за количеством образцов СМО, для которых будут выведены конечные выражения характеристик; данная книга - не справочник по теории массового обслуживания (такую роль гораздо лучше выполняют специальные руководства). Наша цель - познакомить читателя с некоторыми «маленькими хитростями», облегчающими путь сквозь теорию массового обслуживания, которая в ряде имеющихся (даже претендующих на популярность) книг может показаться бессвязным набором примеров.
Все потоки событий, переводящие СМО из состояния в состояние, в данном параграфе мы будем считать простейшими (не оговаривая это каждый раз специально). В их числе будет и так называемый «поток обслуживании». Под ним разумеется поток заявок, обслуживаемых одним непрерывно занятым каналом. В этом потоке интервал между событиями, как и всегда в простейшем потоке, имеет показательное распределение (во многих руководствах вместо этого говорят: «время обслуживания - показательное», мы и сами в дальнейшем будем пользоваться таким термином).
1) В популярной книжке дан несколько иной, по сравнению с вышеизложенным, вывод формулы Литтла. Вообще, знакомство с этой книжкой («Беседа вторая») полезно для первоначального ознакомления с теорией массового обслуживания.
В данном параграфе показательное распределение времени обслуживания будет само собой разуметься, как всегда для «простейшей» системы.
Характеристики эффективности рассматриваемых СМО мы будем вводить по ходу изложения.
^ 1. п -канальная СМО с отказами (задача Эрланга). Здесь мы рассмотрим одну из первых по времени, «классических» задач теории массового обслуживания;
эта задача возникла из практических нужд телефонии и была решена в начале нашего века датским математиком Эрлантом. Задача ставится так: имеется п каналов (линий связи), на которые поступает поток заявок с интенсивностью λ. Поток обслуживании имеет интенсивность μ (величина, обратная среднему времени обслуживания t об). Найти финальные вероятности состояний СМО, а также характеристики ее эффективности:
^ А - абсолютную пропускную способность, т. е. среднее число заявок, обслуживаемых в единицу времени;
Q - относительную пропускную способность, т. е. среднюю долю пришедших заявок, обслуживаемых системой;
^ Р отк - вероятность отказа, т. е. того, что заявка покинет СМО не обслуженной;
k - среднее число занятых каналов.
Решение. Состояния системы ^ S (СМО) будем нумеровать по числу заявок, находящихся в системе (в данном случае оно совпадает с числом занятых каналов):
S 0 - в СМО нет ни одной заявки,
S 1 - в СМО находится одна заявка (один канал занят, остальные свободны),
S k - в СМО находится k заявок (k каналов заняты, остальные свободны),
S n - в СМО находится п заявок (все n каналов заняты).
Граф состояний СМО соответствует схеме гибели в размножения (рис. 20.1). Разметим этот граф - проставим у стрелок интенсивности потоков событий. Из S 0 в S 1 систему переводит поток заявок с интенсивностью λ (как только приходит заявка, система перескакивает из S 0 в S 1). Тот же поток заявок переводит
Систему из любого левого состояния в соседнее правое (см. верхние стрелки на рис. 20.1).
Проставим интенсивности у нижних стрелок. Пусть система находится в состоянии ^ S 1 (работает один канал). Он производит μ обслуживании в единицу времени. Проставляем у стрелки S 1 → S 0 интенсивность μ. Теперь представим себе, что система находится в состоянии S 2 (работают два канала). Чтобы ей перейти в S 1 , нужно, чтобы либо закончил обслуживание первый канал, либо второй; суммарная интенсивность их потоков обслуживании равна 2μ; проставляем ее у соответствующей стрелки. Суммарный поток обслуживании, даваемый тремя каналами, имеет интенсивность 3μ, k каналами - kμ. Проставляем эти интенсивности у нижних стрелок на рис. 20.1.
А теперь, зная все интенсивности, воспользуемся уже готовыми формулами (19.7), (19.8) для финальных вероятностей в схеме гибели и размножения. По формуле (19.8) получим:
Члены разложения 
будут представлять собой коэффициенты при р 0
в выражениях для p 1
Заметим, что в формулы (20.1), (20.2) интенсивности λ и μ входят не по отдельности, а только в виде отношения λ/μ. Обозначим
λ/μ = ρ (20.3)
И будем называть величину р «приведенной интенсивностью потока заявок». Ее смысл-среднее число заявок, приходящее за среднее время обслуживания одной заявки. Пользуясь этим обозначением, перепишем формулы (20.1), (20.2) в виде:
Формулы (20.4), (20.5) для финальных вероятностей состояний называются формулами Эрланга - в честь основателя теории массового обслуживания. Большинство других формул этой теории (сегодня их больше, чем грибов в лесу) не носит никаких специальных имен.
Таким образом, финальные вероятности найдены. По ним мы вычислим характеристики эффективности СМО. Сначала найдем ^ Р отк . - вероятность того, что пришедшая заявка получит отказ (не будет обслужена). Для этого нужно, чтобы все п каналов были заняты, значит,
Р отк = р n = . (20.6)
Отсюда находим относительную пропускную способность - вероятность того, что заявка будет обслужена:
Q = 1 – P отк. = 1 - (20.7)
Абсолютную пропускную способность получим, умножая интенсивность потока заявок λ, на Q:
A = λQ = λ . (20.8)
Осталось только найти среднее число занятых каналов k. Эту величину можно было бы найти «впрямую», как математическое ожидание дискретной случайной величины с возможными значениями 0, 1, ..., п и вероятностями этих значений р 0 р 1 , ..., р n:
k = 0 · р 0 + 1 · p 1 + 2 · р 2 + ... + п · р n .
Подставляя сюда выражения (20.5) для р k , (k = 0, 1, ..., п) и выполняя соответствующие преобразования, мы, в конце концов, получили бы верную формулу для k. Но мы выведем ее гораздо проще (вот она, одна из «маленьких хитростей»!) В самом деле, нам известна абсолютная пропускная способность А. Это - не что иное, как интенсивность потока обслуженных системой заявок. Каждый занятый i .шал в единицу времени обслуживает в среднем |л заявок. Значит, среднее число занятых каналов равно
k = A/μ, (20.9)
или, учитывая (20.8),
k = 
(20.10)
Рекомендуем читателю самостоятельно решить пример. Имеется станция связи с тремя каналами (n = 3), интенсивность потока заявок λ = 1,5 (заявки в минуту); среднее время обслуживания одной заявки t об = 2 (мин.), все потоки событий (как и во всем этом параграфе) - простейшие. Найти финальные вероятности состояний и характеристики эффективности СМО: А, Q, P отк, k. На всякий случай сообщаем ответы: p 0 = 1/13, p 1 = 3/13, p 2 = 9/26, р 3 = 9/26 ≈ 0,346,
А ≈ 0,981, Q ≈ 0,654, P отк ≈ 0,346, k ≈ 1,96.
Из ответов видно, между прочим, что наша СМО в значительной мере перегружена: из трех каналов занято в среднем около двух, а из поступающих заявок около 35% остаются не обслуженными. Предлагаем читателю, если он любопытен и неленив, выяснить: сколько потребуется каналов для того, чтобы удовлетворить не менее 80% поступающих заявок? И какая доля каналов при этом будет простаивать?
Тут уже проглядывает некоторый намек на оптимизацию. В самом деле, содержание каждого канала в единицу времени обходится в какую-то сумму. Вместе с тем, каждая обслуженная заявка приносит какой-то доход. Умножая этот доход на среднее число заявок А, обслуживаемых в единицу времени, мы получим средний доход от СМО в единицу времени. Естественно, при увеличении числа каналов этот доход растет, но растут и расходы, связанные с содержанием каналов. Что перевесит - увеличение доходов или расходов? Это зависит от условий операции, от «платы за обслуживание заявки» и от стоимости содержания канала. Зная эти величины, можно найти оптимальное число каналов, наиболее эффективное экономически. Мы такой задачи решать не будем, предоставляя все тому же «неленивому и любопытному читателю» придумать пример и решить. Вообще, придумывание задач больше развивает, чем решение уже поставленных кем-то.
^ 2. Одноканальная СМО с неограниченной очередью. На практике довольно часто встречаются одноканальные СМО с очередью (врач, обслуживающий пациентов; телефон-автомат с одной будкой; ЭВМ, выполняющая заказы пользователей). В теории массового обслуживания одноканальные СМО с очередью также занимают особое место (именно к таким СМО относится большинство полученных до сих пор аналитических формул для немарковских систем). Поэтому мы уделим одноканальной СМО с очередью особое внимание.
Пусть имеется одноканальная СМО с очередью, на которую не наложено никаких ограничений (ни по длине очереди, ни по времени ожидания). На эту СМО поступает поток заявок с интенсивностью λ; поток обслуживании имеет интенсивность μ, обратную среднему времени обслуживания заявки t об. Требуется найти финальные вероятности состояний СМО, а также характеристики ее эффективности:
L сист. - среднее число заявок в системе,
W сист. - среднее время пребывания заявки в системе,
^ L оч - среднее число заявок в очереди,
W оч - среднее время пребывания заявки в очереди,
P зан - вероятность того, что канал занят (степень загрузки канала).
Что касается абсолютной пропускной способности А и относительной Q, то вычислять их нет надобности:
в силу того, что очередь неограниченна, каждая заявка рано или поздно будет обслужена, поэтому А = λ, по той же причине Q = 1.
Решение. Состояния системы, как и раньше, будем нумеровать по числу заявок, находящихся в СМО:
S 0 - канал свободен,
S 1 - канал занят (обслуживает заявку), очереди нет,
S 2 - канал занят, одна заявка стоит в очереди,
S k - канал занят, k - 1 заявок стоят в очереди,
Теоретически число состояний ничем не ограничено (бесконечно). Граф состоянии имеет вид, показанный на рис. 20.2. Это - схема гибели и размножения, но с бесконечным числом состояний. По всем стрелкам поток заявок с интенсивностью λ переводит систему слева направо, а справа налево - поток обслуживании с интенсивностью μ.
Прежде всего спросим себя, а существуют ли в этом случае финальные вероятности? Ведь число состояний системы бесконечно, и, в принципе, при t → ∞ очередь может неограниченно возрастать! Да, так оно и есть: финальные вероятности для такой СМО существуют не всегда, а только когда система не перегружена. Можно доказать, что если ρ строго меньше единицы (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t → ∞ растет неограниченно. Особенно «непонятным» кажется этот факт при ρ = 1. Казалось бы, к системе не предъявляется невыполнимых требований: за время обслуживания одной заявки приходит в среднем одна заявка, и все должно быть в порядке, а вот на деле - не так. При ρ = 1 СМО справляется с потоком заявок, только если поток этот - регулярен, и время обслуживания - тоже не случайное, равное интервалу между заявками. В этом «идеальном» случае очереди в СМО вообще не будет, канал будет непрерывно занят и будет регулярно выпускать обслуженные заявки. Но стоит только потоку заявок или потоку обслуживании стать хотя бы чуточку случайными - и очередь уже будет расти до бесконечности. На практике этого не происходит только потому, что «бесконечное число заявок в очереди» - абстракция. Вот к каким грубым ошибкам может привести замена случайных величин их математическими ожиданиями!
Но вернемся к нашей одноканальной СМО с неограниченной очередью. Строго говоря, формулы для финальных вероятностей в схеме гибели и размножения выводились нами только для случая конечного числа состояний, но позволим себе вольность - воспользуемся ими и для бесконечного числа состояний. Подсчитаем финальные вероятности состояний по формулам (19.8), (19.7). В нашем случае число слагаемых в формуле (19.8) будет бесконечным. Получим выражение для р 0:
p 0 = -1 =
= (1 + р + р 2 + ... + р k +… .) -1 . (20.11)
Ряд в формуле (20.11) представляет собой геометрическую прогрессию. Мы знаем, что при ρ < 1 ряд сходится - это бесконечно убывающая геометрическая прогрессия со знаменателем р. При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний р 0 , p 1 , ..., p k , ... существуют только при р<1). Теперь предположим, что это условие выполнено, и ρ <1. Суммируя прогрессию в (20.11), имеем
1 + ρ + ρ 2 + ... + ρ k + ... = ,
p 0 = 1 - ρ. (20.12)
Вероятности р 1 , р 2 , ..., р k , ... найдутся по формулам:
p 1 = ρp 0 , p 2 = ρ 2 p 0 ,…,p k = ρp 0 , ...,
Откуда, с учетом (20.12), найдем окончательно:
p 1 = ρ (1 - ρ), p 2 = ρ 2 (1 - ρ), . . . , p k = ρ k (1 - ρ), . . .(20.13)
Как видно, вероятности p 0 , p 1 , ..., p k , ... образуют геометрическую прогрессию со знаменателем р. Как это ни странно, максимальная из них р 0 - вероятность того, что канал будет вообще свободен. Как бы ни была нагружена система с очередью, если только она вообще справляется с потоком заявок (ρ<1), самое вероятное число заявок в системе будет 0.
Найдем среднее число заявок в СМО ^ L сист . . Тут придется немного повозиться. Случайная величина Z - число заявок в системе - имеет возможные значения 0, 1, 2, .... k, ... с вероятностями p 0 , р 1 , р 2 , ..., p k , ... Ее математическое ожидание равно
L сист = 0 · p 0 + 1 · p 1 + 2 · p 2 +…+k · p k +…= (20.14)
(сумма берется не от 0 до ∞, а от 1 до ∞, так как нулевой член равен нулю).
Подставим в формулу (20.14) выражение для p k (20.13):
L
сист. = 
Теперь вынесем за знак суммы ρ (1-ρ):
L сист. = ρ (1-ρ)
Тут мы опять применим «маленькую хитрость»: k ρ k -1 есть не что иное, как производная по ρ от выражения ρ k ; значит,
L сист. = ρ (1-ρ)
Меняя местами операции дифференцирования п суммирования, получим:
L сист. = ρ (1-ρ) (20.15)
Но сумма в формуле (20.15) есть не что иное, как сумма бесконечно убывающей геометрической прогрессии с первым членом ρ и знаменателем ρ; эта сумма
равна , а ее производная .Подставляя это выражение в (20.15), получим:
L сист = . (20.16)
Ну, а теперь применим формулу Литтла (19.12) и найдем среднее время пребывания заявки в системе:
W сист = (20.17)
Найдем среднее число заявок в очереди L оч. Будем рассуждать так: число заявок в очереди равно числу заявок в системе минус число заявок, находящихся под обслуживанием. Значит (по правилу сложения математических ожиданий), среднее число заявок в очереди L оч равно среднему числу заявок в системе L сист минус среднее число заявок под обслуживанием. Число заявок под обслуживанием может быть либо нулем (если канал свободен), либо единицей (если он занят). Математическое ожидание такой случайной величины равно вероятности того, что канал занят (мы ее обозначили Р зан). Очевидно, Р зан равно единице минус вероятность р 0 того, что канал свободен:
Р зан = 1 - р 0 = ρ. (20.18)
Следовательно, среднее число заявок под обслуживанием равно
^ L об = ρ, (20.19)
L оч = L сист – ρ =
и окончательно
L оч = (20.20)
По формуле Литтла (19.13) найдем среднее время пребывания заявки в очереди:
(20.21)
Таким образом, все характеристики эффективности СМО найдены.
Предложим читателю самостоятельно решить пример: одноканальная СМО представляет собой железнодорожную сортировочную станцию, на которую поступает простейший поток составов с интенсивностью λ = 2 (состава в час). Обслуживание (расформирование)
состава длится случайное (показательное) время со средним значением t об = 20 (мин.). В парке прибытия станции имеются два пути, на которых могут ожидать обслуживания прибывающие составы; если оба пути заняты, составы вынуждены ждать на внешних путях. Требуется найти (для предельного, стационарного режима работы станции): среднее, число составов l сист, связанных со станцией, среднее время W сист пребывания состава при станции (на внутренних путях, на внешних путях и под обслуживанием), среднее число L оч составов, ожидающих очереди на расформирование (все равно, на каких путях), среднее время W оч пребывания состава на очереди. Кроме того, попытайтесь найти среднее число составов, ожидающих расформирования на внешних путях L внеш и среднее время этого ожидания W внеш (две последние величины связаны формулой Литтла). Наконец, найдите суммарный суточный штраф Ш, который придется заплатить станции за простои составов на внешних путях, если за один час простоя одного состава станция платит штраф а (руб.). На всякий случай сообщаем ответы: L сист. = 2 (состава), W сист. = 1 (час), L оч = 4/3 (состава), W оч = 2/3 (часа), L внеш = 16/27 (состава), W внеш = 8/27 ≈ 0,297 (часа). Средний суточный штраф Ш за ожидание составов на внешних путях получим, перемножая среднее число составов, прибывающих на станцию за сутки, среднее время ожидания состава на внешних путях и часовой штраф а : Ш ≈ 14,2а .
^ 3. re-канальная СМО с неограниченной очередью. Совершенно аналогично задаче 2, но чуточку более сложно, решается задача об n -канальной СМО с неограниченной очередью. Нумерация состояний - опять по числу заявок, находящихся в системе:
S 0 - в СМО заявок нет (все каналы свободны),
S 1 - занят один канал, остальные свободны,
S 2 - занято два канала, остальные свободны,
S k - занято k каналов, остальные свободны,
S n - заняты все п каналов (очереди нет),
S n+1 - заняты все n каналов, одна заявка стоит в очереди,
S n+r - заняты вес п каналов, r заявок стоит в очереди,
Граф состояний показан на рис. 20.3. Предлагаем читателю самому обдумать и обосновать значения интенсивностей, проставленных у стрелок. Граф рис. 20.3
λ λ λ λ λ λ λ λ λ
μ 2μ kμ (k+1)μ nμ nμ nμ nμ nμ
есть схема гибели и размножения, но с бесконечным числом состояний. Сообщим без доказательства естественное условие существования финальных вероятностей: ρ/n <1. Если ρ/n ≥ 1, очередь растет до бесконечности.
Предположим, что условие ρ/n < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для р 0 будет стоять ряд членов, содержащих факториалы, плюс сумма бесконечно убывающей геометрической прогрессии со знаменателем ρ/n . Суммируя ее, найдем
(20.22)
Теперь найдем характеристики эффективности СМО. Из них легче всего находится среднее число занятых каналов k == λ/μ, = ρ (это вообще справедливо для любой СМО с неограниченной очередью). Найдем среднее число заявок в системе L сист и среднее число заявок в очереди L оч. Из них легче вычислить второе, по формуле
L оч =
выполняя соответствующие преобразования по образцу задачи 2
(с дифференцированием ряда), получим:
L
оч = 
(20.23)
Прибавляя к нему среднее число заявок под обслуживанием (оно же - среднее число занятых каналов) k = ρ, получим:
L сист = L оч + ρ. (20.24)
Деля выражения для L оч и L сист на λ, по формуле Литтла получим средние времена пребывания заявки в очереди и в системе:
(20.25)
А теперь решим любопытный пример. Железнодорожная касса по продаже билетов с двумя окошками представляет собой двухканальную СМО с неограниченной очередью, устанавливающейся сразу к двум окошкам (если одно окошко освобождается, ближайший в очереди пассажир его занимает). Касса продает билеты в два пункта: А и В. Интенсивность потока заявок (пассажиров, желающих купить билет) для обоих пунктов А и В одинакова: λ А = λ В = 0,45 (пассажира в минуту), а в сумме они образуют общий поток заявок с интенсивностью λ А + λ В = 0,9. Кассир тратит на обслуживание пассажира в среднем две минуты. Опыт показывает, что у кассы скапливаются очереди, пассажиры жалуются на медленность обслуживания, Поступило рационализаторское предложение: вместо одной кассы, продающей билеты и в А и в В, создать две специализированные кассы (по одному окошку в каждой), продающие билеты одна - только в пункт А , другая - только в пункт В. Разумность этого предложения вызывает споры - кое-кто утверждает, что очереди останутся прежними. Требуется проверить полезность предложения расчетом. Так как мы умеем считать характеристики только для простейших СМО, допустим, что все потоки событий - простейшие (на качественной стороне выводов это не скажется).
Ну, что же, возьмемся за дело. Рассмотрим два варианта организации продажи билетов - существующий и предлагаемый.
Вариант I (существующий). На двухканальную СМО поступает поток заявок с интенсивностью λ = 0,9; интенсивность потока обслуживании μ = 1/2 = 0,5; ρ = λ/μ = l,8. Так как ρ/2 = 0,9<1, финальные вероятности существуют. По первой формуле (20.22) находим р 0 ≈ 0,0525. Среднее, число заявок в очереди находим по формуле (20.23): L оч ≈ 7,68; среднее время, проводимое заявкой в очереди (по первой из формул (20.25)), равно W оч ≈ 8,54 (мин.).
Вариант II (предлагаемый). Надо рассмотреть две одноканальные СМО (два специализированных окошка); на каждую поступает поток заявок с интенсивностью λ = 0,45; μ. по-прежнему равно 0,5; ρ = λ/μ = 0,9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) L оч = 8,1.
Вот тебе и раз! Длина очереди, оказывается, не только не уменьшилась, а увеличилась! Может быть, уменьшилось среднее время ожидания в очереди? Посмотрим. Деля L оч на λ = 0,45, получим W оч ≈ 18 (минут).
Вот так рационализация! Вместо того чтобы уменьшиться, и средняя длина очереди, и среднее время ожидания в ней увеличились!
Давайте попробуем догадаться, почему так произошло? Пораскинув мозгами, приходим к выводу: произошло это потому, что в первом варианте (двухканальная СМО) меньше средняя доля времени, которую простаивает каждый из двух кассиров: если он не занят обслуживанием пассажира, покупающего билет в пункт А, он может заняться обслуживанием пассажира, покупающего билет в пункт В, и наоборот. Во втором варианте такой взаимозаменяемости нет: незанятый кассир просто сидит, сложа руки...
Ну, ладно,- готов согласиться читатель,- увеличение можно объяснить, но почему оно такое существенное? Нет ли тут ошибки в расчете?
И на этот вопрос мы ответим. Ошибки нет. Дело в том, что в нашем примере обе СМО работают на пределе своих возможностей; стоит немного увеличить время обслуживания (т. е. уменьшить μ), как они уже перестанут справляться с потоком пассажиров, и очередь начнет неограниченно возрастать. А «лишние простои» кассира в каком-то смысле равносильны уменьшению его производительности μ.
Таким образом, кажущийся сначала парадоксальным (или даже просто неверным) результат вычислений оказывается на поверку правильным и объяснимым.
Такого рода парадоксальными выводами, причина которых отнюдь не очевидна, богата теория массового обслуживания. Автору самому неоднократно приходилось «удивляться» результатам расчетов, которые потом оказывались правильными.
Размышляя над последней задачей, читатель может поставить вопрос так: ведь если касса продает билеты только в один пункт, то, естественно, время обслуживания должно уменьшиться, ну, не вдвое, а хоть сколько-нибудь, а мы считали, что оно по-прежнему в среднем равно 2 (мин.). Предлагаем такому придирчивому читателю ответить на вопрос: а насколько надо его уменьшить, чтобы «рационализаторское предложение» стало выгодным? Снова мы встречаемся хотя и с элементарной, но все же задачей оптимизации. С помощью ориентировочных расчетов даже на самых простых, марковских моделях удается прояснить качественную сторону явления - как выгодно поступать, а как - невыгодно. В следующем параграфе мы познакомимся с некоторыми элементарными немарковскими моделями, которые еще расширят наши возможности.
После того, как читатель ознакомился с приемами вычисления финальных вероятностей состояний и характеристик эффективности для простейших СМО (овладел схемой гибели и размножения и формулой Литтла), ему можно предложить для самостоятельного рассмотрения еще две простейшие СМО.
^ 4. Одноканальная СМО с ограниченной очередью. Задача отличается от задачи 2 только тем, что число заявок в очереди ограничено (не может превосходить некоторого заданного т). Если новая заявка приходит в момент, когда все места в очереди заняты, она покидает СМО не обслуженной (получает отказ).
Надо найти финальные вероятности состояний (кстати, они в этой задаче существуют при любом ρ - ведь число состояний конечно), вероятность отказа Р отк, абсолютную пропускную способность А, вероятность того, что канал занят Р зан, среднюю длину очереди L оч, среднее число заявок в СМО L сист , среднее время ожидания в очереди W оч , среднее время пребывания заявки в СМО W сист. При вычислении характеристик очереди можно пользоваться тем же приемом, какой мы применяли в задаче 2, с той разницей, что суммировать надо не бесконечную прогрессию, а конечную.
^ 5. Замкнутая СМО с одним каналом и m источниками заявок. Для конкретности поставим задачу в следующей форме: один рабочий обслуживает т станков, каждый из которых время от времени требует наладки (исправления). Интенсивность потока требований каждого работающего станка равна λ. Если станок вышел из строя в момент, когда рабочий свободен, он сразу же поступает на обслуживание. Если он вышел из строя в момент, когда рабочий занят, он становится в очередь и ждет, пока рабочий освободится. Среднее время наладки станка t об = 1/μ. Интенсивность потока заявок, поступающих к рабочему, зависит от того, сколько станков работает. Если работает k станков, она равна k λ. Найти финальные вероятности состояний, среднее число работающих станков и вероятность того, что рабочий будет занят.
Заметим, что и в этой СМО финальные вероятности
будут существовать при любых значениях λ и μ = 1/t об, так как число состояний системы конечно.
ТЕОРИЯ МАССОВОГО ОБСЛУЖИВАНИЯ
Введение
Теория массового обслуживания является важным разделом системного анализа и исследования операций. Она богата разнообразными приложениями: от задач. связанных с эксплуатацией телефонных сетей, до научной организации производства. Эта теория используется там, где имеются вызовы и клиенты, сигналы и изделия массового производства, а также там, где изделия обслуживаются, обрабатываются, передаются.
Идеи и методы теории массового обслуживания (ТМО) получают всё большее распространение. Многие задачи техники, экономики, военного дела, естествознания могут быть поставлены и решены в терминах ТМО.
Своим возникновением ТМО обязана, в первую очередь, прикладным вопросам телефонии, в которых из-за большого числа независимых или слабо зависимых источников (абонентов телефонных станций) потоки заявок (вызовов) имеют четко выраженный случайный характер. Случайные колебания (флуктуации) около некоторого среднего являются в данном случае не результатом какого-то отклонения от нормы, а закономерностью, свойственной всему процессу. С другой стороны, стабильность работы телефонных станций, возможность получения хороших статистических данных создали предпосылки для выявления основных характеристик, свойственных данному процессу обслуживания.
Впервые на это обратил внимание и провёл исследования датчанин А.К. Эрланг. Основные его работы в данной области относятся к 1908 - 1921 годам. С этого времени, интерес к проблемам, выдвинутым Эрлангом, необычайно возрос. В 1927 - 1928 годах появляются работы Молина и Фрайя, позже в 1930 - 1932 годах - интересные работы Поллачека, А.Н. Колмогорова, А.Я. Хинчина.
Нужно сказать, что первые задачи ТМО были достаточно простыми и допускали получение окончательных аналитических зависимостей. О, развитие шло как по линии увеличения сферы приложения ТМО, так и по линии усложнения стоящих перед ней задач. Оказалось, что задачи типа телефонных, возникают в самых разнообразных направлениях исследований: в естествознании. в технике, на транспорте, в военном деле, в организации производства и т.д.
23. Системы массового обслуживания
Во многих областях практической деятельности человека мы сталкиваемся с необходимостью пребывания в состоянии ожидания. Подобные ситуации возникают в очередях в билетных кассах, в крупных аэропортах, при ожидании обслуживающим персоналом самолетов разрешения на взлет или посадку, на телефонных станциях в ожидании освобождения линии абонента, в ремонтных цехах в ожидании ремонта станков и оборудования, на складах снабженческо-сбытовых организаций в ожидании разгрузки или погрузки транспортных средств. Во всех перечисленных случаях имеем дело с массовостью и обслуживанием. Изучением таких ситуаций занимается теория массового обслуживания.
Теория массового обслуживания – область прикладной математики, занимающаяся анализом процессов в системах производства, обслуживания, управления, в которых однородные события повторяются многократно, например, на предприятиях бытового обслуживания; в системах приема, переработки и передачи информации; автоматических линиях производства и др.
Предметом теории массового обслуживания является установление зависимостей между характером потока заявок, числом каналов обслуживания, производительностью отдельного канала и эффективным обслуживанием с целью нахождения наилучших путей управления этими процессами.
23.1. Понятие смо
В теории систем массового обслуживания (СМО) обслуживаемый объект называют требованием. В общем случае под требованием обычно понимают запрос на удовлетворение некоторой потребности, например, разговор с абонентом, посадка самолета, покупка билета, получение материалов на складе.
Средства, обслуживающие требования, называютсяобслуживающими устройствами иликаналами обслуживания . Например, к ним относятся каналы телефонной связи, посадочные полосы, мастера-ремонтники, билетные кассиры, погрузочно-разгрузочные точки на базах и складах.
Совокупность однотипных обслуживающих устройств называется системой массового обслуживания . Такими системами могут быть телефонные станции, аэродромы, билетные кассы, ремонтные мастерские, склады и базы снабженческо-сбытовых организаций и т.д.
Основной задачей теории СМО является изучение режима функционирования обслуживающей системы и исследование явлений, возникающих в процессе обслуживания. Так, одной из характеристик обслуживающей системы является время пребывания требования в очереди. Очевидно, что это время можно сократить за счет увеличения количества обслуживающих устройств. Однако каждое дополнительное устройство требует определенных материальных затрат, при этом увеличивается время бездействия обслуживающего устройства из-за отсутствия требований на обслуживание, что также является негативным явлением. Следовательно, в теории СМО возникают задачи оптимизации: каким образом достичь определенного уровня обслуживания (максимального сокращения очереди или потерь требований) при минимальных затратах, связанных с простоем обслуживающих устройств.
Источник. Источник определяется как устройство или множество, из которого требования поступают в систему для обслуживания. Источник называют бесконечным или конечным в зависимости от того, бесконечное или конечное число требований содержится в нем. Будем всегда предполагать, что источник, генерирующий требования, неисчерпаем. Например, хотя абонентов некоторого телефонного узла конечное число, предполагаем, что они образують бесконечный источник.
Входящий поток. Требования, поступающие из источника на обслуживание, образуют входящий поток. Само требование можно рассматривать как запрос на удовлетворение какой-то потребности. Примеров входящих потоков можно привести множество. Это - поток информации, поступающей на обработку в ЭВМ; поток заявок на АТС; поток клиентов, приходящих в ателье, и больных в поликлинику, поток прибывающих в порт судов; налетающие на объект удара самолеты и ракеты противника и т. д.
Обслуживающая система. Под обслуживающей системой понимают множество технических средств или производственного персонала (различного рода установки, приборы, устройства, тоннели, взлетно-посадочные полосы, линии связи, продавцы, бригады рабочих или служащих, кассиры и т. д.), выполняющих функции обслуживания. Все перечисленное выше, как уже говорилось, объединяется одним названием «канал обслуживания» (обслуживающий прибор). Состав системы определяется количеством каналов (приборов, линий). По количеству каналов системы можно подразделить на одноканальные и многоканальные.
Выходящий поток. Выходящий поток - это поток требований, покидающих систему после обслуживания. Сюда могут входить и требования, которые покинули систему, не пройдя обслуживания.
Входящий поток, функционирование обслуживающей системы как результат обслуживания, выходящий поток подлежат количественному описанию. Для того чтобы проводить математические исследование процесса массового обслуживания, необходимо полно определить систему обслуживания. Обычно это означает:
- задание входящего потока. Здесь имеются в виду как средняя интенсивность поступления требований, так и статистическая модель их поступления (т. е. закон распределения моментов поступления требований в систему);
- задание механизма обслуживания. Это означает указание того, когда обслуживание допустимо, сколько требований может обслуживаться одновременно и как долго длится обслуживание. Последнее свойство обычно характеризуют статистическим распределением длительности обслуживания (закон распределения времени обслуживания);
- задание дисциплины обслуживания. Это означает указание способа, по которому происходит отбор одного требования из очереди (если она есть) на обслуживание. В простейшем варианте дисциплина обслуживания заключается в обслуживании требований в порядке их поступления (справедливый принцип), однако существует и много других возможностей.
Задание системы предполагает также известное описание взаимодействия между отдельными ее частями.
Когда система достаточно полно определена, появляется основание для построения математической модели. Если математическая модель более или менее адекватно отображает реальную систему, то она позволяет получить основные характеристики функционирования системы. Разумеется, модель значительно упрощает практическую ситуацию, но это не умаляет математических методов теории массового обслуживания и положение дел не отличается от положения дел в других областях прикладной математики.
Модели теории массового обслуживания
Теория массового обслуживания представляет собой область прикладной математики, использующую методы теории случайных процессов и теории вероятностей для исследования различной природы сложных систем. Теория массового обслуживания непосредственно не связана с оптимизацией. Назначение ее состоит в том, чтобы на основе результатов наблюдений за «входом» в систему предсказать ее возможности и организовать наилучшее обслуживание для конкретной ситуации и понять, как последнее отразится на стоимости системы в целом.
Модели теории массового обслуживания описывают процессы массового спроса на обслуживание с учетом случайного характера поступления требований и продолжительности обслуживания.
Назначение моделей теории массового обслуживания состоит в том, чтобы на основе информации о входящем случайном потоке требований предсказать возможности системы обслуживания, организовать наилучшее выполнение требований для конкретной ситуации и оценить, как это отразится на ее стоимости.
Система массового обслуживания (СМО) возникает тогда, когда происходит массовое появление заявок (требований) на обслуживание и их последующее удовлетворение.
Особенностью СМО является случайный характер исследуемых явлений. Типичный пример СМО - телефонная сеть (снятием трубки с рычага телефонного аппарата абонент дает заявку на обслуживание разговора по одной из линий телефонной сети).
Основными элементами СМО являются:
Входящий поток заявок (требований) на обслуживание;
Очередь заявок на обслуживание;
Приборы (каналы) обслуживания;
Выходящий поток обслуженных заявок (рисунок 8.5).
Такой элемент СМО как очередь может отсутствовать в некоторых системах, но в тоже время СМО может иметь и другие элементы, например, выходящий поток не обслуженных заявок.
Для систем, относящихся к системам массового обслуживания, существует определенный класс задач, решение которых позволяет ответить, например, на следующие вопросы:
Рисунок 8.5 - Обобщенная схема СМО
С какой интенсивностью должно проходить обслуживание или должен выполняться процесс при заданной интенсивности и других параметрах входящего потока требований, чтобы минимизировать очередь или задержку в подготовке документа или другого вида информации?
Каковы вероятность появления задержки или очереди и ее величина? Сколько времени требование находится в очереди и каким образом минимизировать его задержку?
Какова вероятность потери требования (клиента)?
Какова должна быть оптимальная загрузка обслуживающих каналов? При каких параметрах системы достигаются минимальные потери прибыли?
К этому перечню можно добавить еще целый ряд задач.
Как системы массового обслуживания могут быть представлены следующие работы и процессы: посадка самолетов в аэропорту, обслуживание автомобилей на автозаправочных станциях, разгрузка судов на причалах, обслуживание покупателей в магазинах, прием больных в поликлинике, обслуживание клиентов в ремонтной мастерской и др.
Часто входной поток заявок представляется в виде простейшего потока, обладающего свойством стационарности, отсутствия последствия и ординарности.
Поток является стационарным, если вероятный режим не зависит от времени. Ординарность потока наступает, если вероятность появления двух и более заявок за промежуток времени τ является бесконечно малой величиной по сравнению с τ. Поток обладает свойством отсутствия последствия, если поступление заявок не зависит от предистории процесса.
Для простейшего потока поступление заявок в СМО описывается законом распределения Пуассона
Р к (τ
) 
,
где Р к (τ ) -вероятность поступления к заявок за время τ ;
λ - интенсивность входного потока.
Важное для исследования свойство, которым обладает пуассоновский поток, заключается в том, что процедура разделения и объединения дает снова пуассоновские потоки. Тогда, если входной поток формируется из N независимых источников, каждый из которых порождает пуассоновский поток интенсивностью λ i (i = 1, 2, ..., N), то его интенсивность будет определяться по формуле
λ = λ l + λ 2 +...+ λ N .
В случае разделения пуассоновского потока на N независимых потоков получим, что интенсивность потока λ i будет равна r i λ ,где r i - доля i-го потока во входном потоке требований.
Очередью является множество заявок (требований), ожидающих обслуживание.
В зависимости от допустимости и характера формирования очереди системы массового обслуживания подразделяются:
1. СМО с отказами - формирование очереди не разрешено, поэтому заявка, пришедшая в момент, когда все каналы заняты, получает отказ и теряется. Пример: АТС (выполнение заказов к определенному сроку), система ПВО объекта (цель в зоне обстрела пребывает мало времени).
2. СМО с неограниченным ожиданием - поступившая заявка, застав все обслуживающие приборы занятыми, становится в очередь и дожидается обслуживания. Число мест для ожидания (длина очереди) не ограничено. Не ограничивается и время ожидания. Пример: предприятия бытового обслуживания, такие как мастерские по ремонту часов, обуви.
3. СМО смешанного типа. В этих системах имеется очередь,
на которую накладываются ограничения. Например: на максимальную длину очереди (I тип – с ограниченной ДО) или на время ожидания заявки в очереди (П тип – с ограниченным ВО). Примерами СМО I-го типа являются мастерские по ремонту радиоаппаратуры с ограниченными площадями для ее хранения. Торговые точки по продаже фруктов, овощей, которые могут храниться ограниченное время, являются смешанными СМО II -го типа.
Порядок поступления заявок на обслуживание называется дисциплиной обслуживания.
В СМО с очередью могут быть следующие варианты дисциплины обслуживания:
а) в порядке поступления заявок (первым пришел – первым обслужился) - магазины, предприятия бытового обслуживания;
б) в порядке обратном поступлению, т. е. последняя заявка обслуживается первой (последним пришел - первым обслужился) - выемка заготовок из бункера;
в) в соответствии с приоритетом (участники ВОВ в поликлинике);
г) в случайном порядке (в системе ПВО объекта при отражении воздушного налета противника).
Основным параметром процесса обслуживания считается время обслуживания заявки каналом (обслуживающим прибором j) – t j (j=1,2,…,m).
Величина t j в каждом конкретном случае определяется рядом факторов: интенсивностью поступления заявок, квалификацией исполнителя, технологией работ, окружающей средой и т.д. Законы распределения случайной величины t j могут быть самыми различными, но наибольшее распространение в практических приложениях получил экспоненциальный закон распределения. Функция распределения случайной величины t j имеет вид:
F(t) = l – e - μt ,
где m - положительный параметр, определяющий интенсивность обслуживания требований;
где Е (t) - математическое ожидание случайной величины обслуживания требования t j .
Важнейшее свойство экспоненциального распределения заключается в следующем. При наличии нескольких однотипных каналов обслуживания и равной вероятности их выбора при поступлении заявки распределение времени обслуживания всеми m каналами будет показательной функцией вида:
Если СМО состоит из неоднородных каналов, то , если
же все каналы однородные, то .
По количеству обслуживающих приборов (каналов) СМО делятся на:
Одноканальные;
Многоканальные.
Структура СМО и характеристика ее элементов приведены на рисунке 8.6.
Исследование СМО заключается в нахождении показателей, характеризующих качество и условия работы обслуживающей системы и показателей, отражающих экономические последствия принятых решений.
Важнейшим понятием в анализе СМО является понятие состояния системы. Состояние есть некоторое описание системы, на основании которого можно предсказать ее будущее поведение.
Рисунок 8.6 – Структура и характеристика элементов СМО
При анализе СМО определяют усредненные показатели обслуживания. В зависимости от решаемой задачи ими могут быть:
средняя длина очереди,
среднее время ожидания в очереди,
средний процент обслуживаемых (или получивших отказ) заявок, среднее число занятых (или простаивающих) каналов,
среднее время пребывания в СМО и др.
В качестве критерия оптимизации применяют:
Максимум прибыли от эксплуатации СМО;
Минимум суммарных потерь, связанных с простоем каналов, простоем заявок в очереди и уходом необслуженных заявок;
Обеспечение заданной пропускной способности.
Варьируемыми параметрами обычно являются: количество каналов, их производительность, длина и дисциплина очереди, приоритетность обслуживания.
Вопросы для самопроверки
1. Понятие о математических моделях и моделировании.
2. Что представляет собой экономико-статистическая модель и производственная функция?
3. Применение графических и графоаналитических моделей в управлении.
4. Использование корреляционного анализа для выявления связи между параметрами
5. Виды и методы построения регрессионных моделей.
6. Статистическое исследование причинно-следственных связей.
7. Классификация математических моделей по четырем аспектам детализации (по В.А. Кардашу).
8. Классификация моделей по применяемому математическому аппарату. Понятие о балансовых моделях.
9. Этапы моделирования. Проверка модели на адекватность.
10. Понятие о системах массового обслуживания (СМО). Составные части СМО.
11. СМО с отказами и с очередью. Разновидности очередей.
12. Одноканальные и многоканальные СМО. Дисциплины обслуживания
13. Моделирование СМО. Показатели, получаемые при экспериментах на модели СМО.
14. Критерии оптимизации систем массового обслуживания.