<<
>>

ГЛАВА 11 теория массового обслуживания

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

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

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

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

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

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

Аналитическое исследование СМО является наиболее простым, если все потоки событий, переводящие ее из состояния в состояние, — простейшие (стационарные пуассоновские).

Это значит, что интервалы времени между событиями в потоках имеют показательное распределение с параметром, равным интенсивности соответствующего потока. Для СМО это допущение означает, что как поток заявок, так и поток обслуживании — простейшие. Под потоком обслуживаний понимается поток заявок, обслуживаемых одна за другой одним непрерывно занятым каналом. Этот поток оказывается простейшим, только если время обслуживания заявки Тобсл представляет собой случайную величину, имеющую показательное распределение. Параметр этого распределения р есть величина, обратная среднему времени обслуживания: р = 1 / to6cjl, где ?обсл = М [Т^ ]. Вместо «поток обслуживаний — простейший» часто говорят «время обслуживания пока-зательное». Условимся в дальнейшем для краткости всякую СМО, в которой все потоки простейшие, называть простейшей СМО. В этой главе будем рассматривать главным образом простейшие СМО.

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

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

среднее число заявок А, обслуживаемое СМО в единицу времени, или абсолютная пропускная способность СМО;

вероятность обслуживания поступившей заявки Q или относительная пропускная способность СМО;(5 = А/Х;

вероятность отказа РОТК, т.е. вероятность того, что поступившая заявка не будет обслужена, получит отказ; Ротк = 1 - Q;

среднее число заявок в СМО (обслуживаемых или ожидающих в оче-реди) I;

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

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

среднее время пребывания заявки в очереди tQ4; среднее число занятых каналов к.

В общем случае все эти характеристики зависят от времени.

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

Для любой открытой СМ01} в предельном стационарном режиме среднее время пребывания заявки в системе tcllcr выражается через среднее число заявок в системе с помощью формулы Литтла:

4ист = Z / \ (11.0.1)

где X — интенсивность потока заявок.

^ СМО называется открытой, если интенсивность поступающего на нее потока заявок не зависит от состояния самой СМО.

nnnrfhrf^ чі

и-l M*2 И-з M-A; M-Jfc+1 лп

Рис. 11.01

Аналогичная формула (называемая также формулой Литтла) связывает среднее время пребывания заявки в очереди tQ4 и среднее число г заявок в очереди:

I = г/\. (11.0.2)

Формулы Литтла очень полезны, так как позволяют вычислять не обе характеристики эффективности (среднее время пребывания и среднее число заявок), а только какую-нибудь одну из них.

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

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

к=А/\і, (11.0.3)

где р = 1 / — интенсивность потока обслуживаний.

Очень многие задачи теории массового обслуживания, касающиеся простейших СМО, решаются с помощью схемы гибели и размножения (см. гл. 10). Если граф состояний СМО может быть представлен в виде, показанном на рис. 11.0.1, то финальные вероятности состояний выражаются формулами (10.0.23): W-- •Vi P!P2. -і

\ W

1 +

PjP2 РіР2---М<*

MXQXJ M-lM-2

Ро = \

Pi = — р0; Нч

М-1 Н-г—Н-л (11.0.4)

= Рор1р2...рп При выводе формул для среднего числа заявок (в очереди или в системе) широко используется прием дифференцирования рядов, состоящий в следующем.

Если X < 1, то

Е

°° ik d і. d ^ k d x x

KX = X 2 . X = x У. X — x = 2 і

k=l кҐ\ dx dx^i\ dx 1-х (1 — x)

(11.0.5)

k=і

(1-х)2

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

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

1. Простейшая СМО с отказами (задача Эрланга). На га-канальную СМО с отказами поступает простейший поток заявок с интенсивностью X, время обслуживания — показательное с параметром (JL = 1 / їобсл. Со-стояния СМО нумеруются по числу заявок, находящихся в СМО (в силу отсутствия очереди, оно совпадает с числом занятых каналов): s0 — СМО свободна;

sa — занят один канал, остальные свободны; ...;

sk — занято & каналов, остальные свободны (1 < к < га);...;

sn — заняты все га каналов.

Финальные вероятности состояний выражаются формулами Эрланга:

-і V

1! 2! п!

Рк — TlPo (* = 1,2,...,п), (11.0.6)

к! где р = X /

Характеристики эффективности:

Л = X (1 - рп); Q = 1 - рп; Ротк - рп:; к = р (1 - рп). (11.0.7)

При больших значениях п вероятности состояний (11.0.8) удобно вычислять через табулированные функции:

0>т

Р (т, а) = —е"а (^распределение Пуассона^ (11.0.8) т !

тп к

R(m,a) = ЕтТе"а (11.0.9)

к=0

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

Р (тп, а) = R (m, а) - R (тп - 1, а). (11.0.10)

Пользуясь этими функциями, формулы Эрланга (11.0.6) можно переписать в виде

pk = P(k,9)/R(n,9) (к = 0, 1,..., п). (11.0.11)

2. Простейшая одноканальная СМО с неограниченной очередью. На

одноканальную СМО поступает простейший поток заявок с интенсивностью X. Время обслуживания — показательное с параметром [і = 1 / t^. Длина очереди не ограничена. Финальные вероятности существуют только при р = X / < 1 (при р > 1 очередь растет неограниченно). Состояния СМО нумеруются по числу заявок в СМО, находящихся в очереди или обслуживамых:

Sg — СМО свободна;

sa — канал занят, очереди нет;

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

sk — канал занят, к — 1 заявок стоят в очереди;....

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

р0 = 1-р, р* = р*(1-р) (к = 1,2,...), (11.0.12)

где р = X / |Л < 1.

Характеристики эффективности СМО:

Л = Х; Q=1; РОТК = 0; (11.0.13)

J = -JL-; г — tcucl = —f—; їоч = —f—; (11.0.14)

1-p 1-p X (1 - p) X (1 - p)

среднее число занятых каналов (или вероятность того, что канал занят)

fc =X/ji = p. (11.0.15)

3.

Простейшая одноканальная СМО с ограничением по длине очереди. На одноканальную СМО поступает простейший поток заявок с интенсивностью X; время обслуживания — показательное с параметром \i = 1 / Ьо^. В очереди m мест. Если заявка приходит в момент, когда все эти места заняты, она получает отказ и покидает СМО. Состояния СМО: SQ — СМО свободна; s1 — канал занят, очереди нет; s2 — канал занят, одна заявка стоит в очереди;...; sk — канал занят, А; — 1 заявок стоят в очереди;...; 5т+1 — канал занят, га заявок стоят в очереди.

Финальные вероятности состояний существуют при любом р = X / |JL и равны:

Ро = , 1 ~mP+2; Ри = РkPo (k = 1, га + 1). (11.0.16) 1 - р

Характеристики эффективности СМО:

А = X (1 - pm+l); Q = 1 - pm+l; РОТК = pm+l. Среднее число занятых каналов (вероятность того, что канал занят)

к =1~р0. (11.0.17) Среднее число заявок в очереди

г =р [!гр (11-0-18)

, _ р2 [1 - рт (га + 1 - тр)] (1-р"+2)(1-р)

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

z=r + k. (11.0.19)

По формуле Литтла

4ист = * / X; tQ4 = г / \ . (11.0.20)

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

На n-канальную СМО поступает простейший поток заявок с интенсивностью X; время обслуживания одной заявки — показательное с параметром р = 1 / . Финальные вероятности существуют только при Р / 71 — X < 1) гДе р = X / (л. Состояния СМО нумеруются по числу заявок в СМО:

s0 — СМО свободна; очереди нет;

Sj — занят один канал; ...;

sk— занято к каналов (1 < к < п); ...;

sn — заняты все п каналов;

5п+1 — заняты все п каналов, одна заявка стоит в очереди; ...; sn+r— заняты все п каналов, г заявок стоят в очереди; .... Финальные вероятности состояний выражаются формулами:

о о11 о""1 1 1-1

Ро

1!

п ! п • п ! 1 — х ? п+г

Рк = Ї-Ро (1 < * < п); Рп+Г = -Ро (г > 1). (11.0.21)

А;! п -п\

С помощью функций Р(га, а) и R(m, а) формулы (11.0.21) могут быть приведены к виду

Р(к, р)

(11.0.22)

Рк =

(к= 0,..., п);

1-Х Рп+г = ХгРп {г = 1,2,...).

Характеристики эффективности СМО:

(11.0.23) (11.0.24)

(11.0.25)

г = р"+1ро / [п ¦ п! (1 - х)2] = x Рп / (1 - х)2;

Z = г + к = г -hp;

Lot = * / \ Іч = Г / X. 5. Простейшая многоканальная СМО с ограничением по длине очереди. Условия и нумерация состояний те же, что в п. 4, с той разницей, что число т мест в очереди ограничено. Финальные вероятности состояний существуют при любых X и р и выражаются формулами: п+1

Ро =

1-х'

п! п • п ! 1-х n+r

:Po (1 < r < m), (11.0.26)

n • n !

гдех = р/ n = X/ (n[i).

Характеристики эффективности СМО:

r =p 1 —; (11.0.28)

л=Чі-Рп+т); Q=i-P„+m; ^отк =Pn+m; fc=p(i-p„+J; (и.о.27) - _ р"+Ч l-(m + l)X- + mX-+1

П'ПІ (1-х)

J = r + F; (11.0.29)

^оч = ^ / ^S *сист =z/\. (11.0.30)

Многоканальная СМО с отказами при простейшем потоке заявок и произвольном времени обслуживания. Формулы Эрланга (11.0.6) остаются справедливыми и тогда, когда поток заявок — простейший, а время о6служивания_ Тобсл имеет произвольное распределение с математическим ожиданием t^ = 1 / \l.

Одноканальная СМО с неограниченной очередью при простейшем потоке заявок и произвольном времени обслуживания. Если на одноканальную СМО поступает простейший поток заявок с интенсивностью X, а время обслуживания Тобсл распределяется по произвольному закону с математическим ожиданием 1 / [і и коэффициентом вариации v , то среднее число заявок в очереди выражается формулой Полячека—Хинчина

F = p2(l+^)2/[2(l-p)], (И.0.31) где р = X / р., а среднее число заявок в СМО

z={p2(l+^)2/[2(l-p)]}+p. (11-0.32) Из (11.0.31) и (11.0.32) по формуле Литтла получим

_Р2(1+*у)2, - _Р2(і+^2) і (11033)

оч 2 X (1 — р) 2\(l-p)V ( }

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

r«PJKs+^)/[2(l-p)], (11.0.34)

где і\ — коэффициент вариации интервала между событиями во входном потоке; р = X / р; X — величина, обратная математическому ожиданию этого интервала; р, = 1 / ?обсл — величина, обратная среднему времени обслуживания; vр — коэффициент вариации времени обслуживания. Среднее число заявок, связанных с СМО,

z % {p2(vx + vl) /[2(1 — р)]} + Р, (11.0.35)

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

^«p'tf+ttf/pxd-p)]; (h-0.36)

lt «{р2(^ + <)/[2Х(1-р)]}+1/ц. (11.0.37)

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

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

Далее будем пользоваться обозначениями для характеристик эффек-тивности СМО, приведенными на с. 364, и по мере необходимости вводить некоторые другие обозначения.

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

Если единица измерения времени не фиксирована, будем для краткости обозначать интенсивности потоков событий просто буквами X, р,... (без указаний размерностей). То же относится и ко времени tcllcJ, tQ4. Если же единица времени фиксирована (час, минута, год и т.д.), то мы будем указывать единицы измерения.

В данной главе нам удобно будет записывать закон распределения смешанной случайной величины Т не в форме функции распределения F(t), а в форме «обобщенной» плотности f(t), которая определяется следующим образом:

/(*) = *;'*)+?р,-б(*-а

где F„(t) — производная функции распределения на участках ее непрерывности: р{ = Р{Т = 6(:г) — дельта-функция, свойства которой даны в прил. 2.

11.1. На вход одноканальной СМО с отказами поступает про-стейший поток заявок с интенсивностью X; время обслужива-ния — показательное с параметром р. В начальный момент времени t = 0 канал свободен. Построить размеченный граф состояний СМО. Написать и решить дифференциальные уравI—»Vj 1 нения Колмогорова для вероятностей состояний

I 0 h—I 1 І СМО. Найти финальные вероятности состояний и ^ (для установившегося режима) характеристики эфРис. 11.1 фективности СМО: A, Q, Ротк, к.

Решение. Состояния СМО: s0 — свободна; sx — канал занят. Граф состояний показан на рис. 11.1. Уравнения Колмогорова:

dp0/dt = -\p0+[ip1] dpjdt = \pb-\x,pl. (11.1.1)

Так как р0 + рг = 1 для любого можно выразить рг через р0: р = 1 — р0 и получить одно уравнение для р0:

d р0 / dt = -(X + |л) ро + И- (11.1.2)

Решая это уравнение, получаем р0 как функцию t X ~(\ + \L)t

1 + -Є

ИРо(0 = ^

Х + |л отсюда

X г„ —(Х-+-м- і

Рі(0 = 1-Ро(0 = т [1-е

x + |л

При t —> оо получим финальные вероятности

=|Л/(Х + и.); л = х / (X + и.), (11.1.3)

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

\Ро = М-Рі; Ро + Pl =

Формулы (11.1.3) можно записать компактнее, если ввести обозначение р = X / |л:

р0=1/(1 + р); PX=P/(1 + P). Характеристики эффективности СМО:

4 = ; Q = —L-; Ротк=рг =

1 + р 1 + р 1 1 + р

к=1-р0=-Р-. (11.1.4)

1 + р

11.2. Одноканальная СМО с отказами представляет собой одну телефонную линию, на вход которой поступает простейший поток вызовов с интенсивностью X = 0,4вызов/мин. Средняя продолжительность разговора to6cn =3 мин; время разговора имеет показательное распределение. Найти финальные вероятности состояний СМО: р0 и pv а также A, Q, Ротк, к. Сравнить пропускную способность СМО с номинальной, которая была бы, если бы разговор длился в точности 3 мин, а заявки шли одна за другой регулярно, без перерывов.

Решение. X = 0,4; р = 1 / to6cJl =1/3;р = Х/ |л = 1,2. По формулам (11.1.3) р0«1 / 2,2«0,455; ^ «0,545; Q«0,455; Л = Х<2« «0,182; к = рг «0,545.

Таким образом, линия в среднем будет обслуживать 0,455 поступающих на нее заявок, т.е. 0,182 разговора в минуту. Номинальная пропускная способность канала была бы (при регулярно приходящих и регулярно обслуживаемых заявках) Аном — 1 / to6cJl = = 1/3 « 0,333 разг/мин, что почти вдвое больше, чем действительная пропускная способность А.

11.3. Имеется одноканальная СМО с отказами. Поток заявок — простейший с интенсивностью X . Время обслуживания — не случайное и в точности равно to6cJl = 1 / р. Найти относительную и абсолютную пропускную способность СМО в предельном стационарном режиме.

Решение. Рассмотрим на оси 01 простейший поток заявок с интенсивностью X (рис. 11.3). Будем отмечать кружками все заявки, которые приняты к обслуживанию. Пусть какая-то заявка,

^обсл ^обсл

—<Ь ҐТ^.

0 t,

Рис. 11.3

пришедшая в момент tv принята к обслуживанию. Тогда все заявки, пришедшие после нее за время to6cJl, получат отказ; следующей будет принята к обслуживанию заявка, пришедшая в момент ^ такой, что t2 —tx > t^. Рассмотрим интервал Г между концом обслуживания первой заявки и моментом t2 прихода ближайшей следующей, которая будет принята к обслуживанию. Из-за отсутствия последействия в простейшем потоке распределение интервала Т совершенно такое же, как и в вообще интервала между заявками, т.е. показательное с параметром X. Средняя длина интервала Травна mt = 1/Х.

Итак, на оси 0? будут чередоваться неслучайные интервалы занятости канала длины to6cjl = 1/р и случайные свободные интервалы со средней длиной 1/Х. На первые попадет доля всех заявок, равная

і/й. _ х l/p + 1/Х Х + р'

а на вторые — доля, равная

р(Х + р) = 1/(1 + р), где р = Х/р.

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

Q = 1/(1 + р), (11.3.1)

откуда

A = XQ = X/(l + p). (11.3.2)

Отметим, что формулы (11.3.1), (11.3.2) совпадают с (11.1.4), соответствующими показательному распределению времени обслуживания. Это и естественно, так как формулы Эрланга остаются справедливыми при любом распределении времени обслуживания со средним значением, равным 1/р.

Доказать, пользуясь формулой (11.0.5), что для простейшей одноканальной СМО с неограниченной очередью среднее число заявок, находящихся в СМО, равно z = р / (1 — р), где р = \Дц а среднее число заявок в очереди г = р2 / (1 — р).

Решение. По формулам (11.0.12) р0 = 1 - р; pk = р*(1-р) (* = 1,2,...).

Обозначим Zфактическое (случайное) число заявок в СМО:

оо оо оо

Z = МЩ = -?крк = ^кРк(1 - Р) = (1 - Р)

к=О к= 1 к =1

По формуле (11.0.5) для р < 1

к=1 (1 - р)

откуда J = р / (1 — р). Среднее число^заявок в очереди равно z минус среднее число занятых каналов к=А/ р —Х/р = р, т.е. г — = [p/(i-p)]-p = p2/(i-p).

Железнодорожная сортировочная горка, на которую подается простейший поток составов с интенсивностью X = 2 состава в час, представляет собой одноканальную СМО с неограниченной очередью. Время обслуживания (роспуска) состава на горке имеет показательное распределение со средним значением to6cJl = 20 мин. Найти финальные вероятности состояний СМО, среднее число z составов, связанных с горкой, среднее число г составов в очереди, среднее время tCOCT пребывания состава в СМО, среднее время tQ4 пребывания состава в очереди.

Решение. Х = 2 состава/ч; to6cn = 1/3 ч; р = 3 состава/ч;

р = Х/р = 2/3. По формулам (11.0.12) р0 = 1 — 2/3=1/3; рг =(2/3) х х(1/3) = 2/9; р2 =(2/3)2(1/3) = 4/27;... рк = (2/3)*(1/3);... По формулам^ 1.0.13), (11.0.14) z = р / (1 - р) = 2 состава; f = 4/3co- става; t сист = 1 ч; tm = 2 / 3 ч.

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

Решение. Вычислим среднее число zB — составов, находящихся на внешних путях:

оо оо оо

=1-р4 +2p5+...= Y^kPk = Y^hpkp0 =Po^2kPkl

к= 4 к =4 к—4

ОО ОС J ОО J J ОС

кґі p t = 4dP ары

dp 1-p (l-p)! nt, 1-P

По формуле Литтла среднее время, проводимое одним составом на внешних путях, tB « 1,18 / X = 1,18 /2 = 0,59 ч. За сутки (24 ч) на станцию приходит в среднем 24Х = 48 составов. Средний суточный штраф составляет 48 • 0,59 • а « 28,3а.

Вычислить непосредственно по графу состояний, пользуясь схемой гибели и размножения, финальные вероятности состояний для простейшей двухканальной СМО (тг = 2) с тремя местами в очереди (га = 3) при X = 0,6; = 0,2; р = X / \х = 3. Найти для этой

СМО характеристики z, г, ?сист , tоч, не пользуясь формулами (11.0.26), а непосредственно через финальные вероятности, и сравнить с теми, которые получаются по формулам (11.0.26).

Рис. 11.7

Решение. Граф состояний СМО показан на рис. 11.7. По схеме гибели и размножения, обозначая X / |л = р, получаем: л 2 3 4 л 5 1

Ро =

- (40,58)-1 » 0,025; q л к агк

Pl

0,074; р2 = « 0,111; р3 = « 0,165;

40,58

40,58

40,58 10,15 15,18 -„„_

Рі = —— ~ 0,250; рь = и 0,375;

40,58 40,58

z = 1 • 0,074 + 2 • 0,111 + 3 • 0,165 + 4 • 0,250 + 5 • 0,375 и 3,67; г = 1 • 0,165 + 2 • 0,250 + 3 • 0,375 » 1,79; «сист = г / 0,6 « 6,11; іоч = г / 0,6 и 2,98.

11.8. Формула для т (11.0.28) справедлива для любого х < 1 или х > 1- При X — 1 она перестает работать (дает неопределенность вида 0/0). Пользуясь непосредственно схемой гибели и размножения, вывести для этого случая вероятности состояний р0, р1,...; рп+т и найти характеристики эффективности СМО: А,

Q'> -Ротк» ^ 1 Z)Іоч , Ісист ¦ X X

с -^t

72 (і, 72 (і,

n+m

__ А | А А X А

М- 2[i k[i n\L

Рис. 11.8 Решение. Граф состояний СМО имеет вид, показанный на рис. 11.8. Пользуясь общими формулами для схемы гибели и раз-множения и обозначая X / р = р, имеем Ро =

1! 2! При х = Р / п = 1

_ 2 Лп Л п +1 „ п + тп

1! 2! п\ п -п\ пт -п\ „ п 2 / \ +...+Р- ? п! п -і (11.8.1)

1! 2! п! п! п!

_1 _ р:

Рк = ТГ Ро (1 < к < n); pn+r = -^Ро (1 < г < ш); (11.8.2) к!

•^отн — Pra+m і <3 — 1 Рп+т — ^ , Ро >

П! 1 -*-гРо п!

l-Vo

п!

A= \Q = \

А: = А / == р

рп га (га + 1)

Ро; (11-8.3)

¦=х>„+г = = Ег =

П!

г=1

J = f 4- fc;

п\

r=1

г= 1

= z /\] tOH =r / X. 11.9. Автозаправочная станция (АЗС) имеет две колонки (п = = 2); площадка возле нее допускает одновременное ожидание не более четырех автомобилей (га = 4). Поток автомобилей, прибывающих на станцию, простейший с интенсивностью X = 1 авт/мин. Время обслуживания автомобиля — показательное со средним значением to6cjl = 2 мин. Найти финальные вероятности состояний АЗС и ее характеристики: A, Q, Ротк, k,z,r, tcliQT , fOH.

Решение. X = 1, p. = 1 / 2 = 0,5; р = 2; х = = 1- По формулам (11.8.1)—(11.8.3) имеем:

[ 22 22 1 1 1 2 Ро= ! + 2+ —+ —-4 =—; рг = р2 =рг =р4 = ръ =р6

13

Ротк =2/13; д = 1-Ротк =11/13;

A = \Q = 11 / 13 « 0,85 авт/мин;

к — А / [1 = 22/13^ 1,69 колонки;

г = — ^ •*•) . _1_ ~ і 54 автомобиля;

2! 2 13

j = f + к « 3,23 автомобиля.

11.10. Имеется двухканальная простейшая СМО с отказами. На ее вход поступает поток заявок с интенсивностью X = 4 заявки/ч. Среднее время обслуживания одной заявки t, = 0,8 ч. Каждая обслуженная заявка приносит доход с = 4 руоГ Содержание каждого канала обходится 2 руб/ч. Решить: выгодно или невыгодно в экономическом отношении увеличить число каналов СМО до трех?

Решение. По формулам Эрланга (11.0.6) 3,22

1 + 3,2 +

Ро =

2!

Q = 1 - р2 « 0,450; А = 4ф « 1,8 заявки/ч.

= (Q^)-1 « 0,107; р2 « ^ ~ о,550;

рі =

2! 3!

Доход от заявок, приносимый СМО в данном варианте, равен D = А - с « 7,2 руб/ч.

Подсчитаем те же характеристики для трехканальной СМО (отмечая их штрихом вверху):

: 0,0677; Рз « 5,48 • 0,0677 « 0,371; Q' = 1 - « 0,629; Л7 = 4<2' « 2,52; Df = А' • с « 10,08руб/ч.

Увеличение дохода равно D' — D = 2,88 руб/ч; увеличение расхода равно 2 руб/ч; из этого видно, что переход отп = 2кп = 3 экономически выгоден.

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

Решение. Данная СМО не дает ни отказов, ни очередей; ее можно рассматривать как предельный случай СМО с отказами при 72 —> оо. Формулы Эрланга (11.0.6) дают -1

к

Ро

= е"р, где р = X / р; рк = е"р = Р (к, р)

а:=0

к\ (см. прил. 1). При неограниченном числе каналовА = Х; к = = Х/р = р.

11.12. Рассматривается одноканальная СМО с отказами; на ее вход поступает простейший поток заявок с интенсивностью X. Время обслуживания — показательное с параметром р = 1 / to6cJl. Работающий канал может время от времени выходить из строя (отказывать); поток отказов канала — простейший с интенсивно-стью v. Восстановление (ремонт) вышедшего из строя канала на-чинается мгновенно после его отказа; время ремонта Тр — показательное с параметром ч = 1 / tp. Заявка, которая обслуживалась в момент выхода канала из строя, покидает СМО необслуженной.

Найти финальные вероятности состояний СМО: s0 — канал свободен; — канал занят, исправен; s2 — канал ремонтируется и характеристики СМО: А и Q.

Решение. Граф состояний СМО дан на рис. 11.12, а. Алгебраические уравнения для финальных вероятностей состояний:

Хро =^1 См* + у)Р\ — Хро>' »рг=чр2] (и.12.1)

к ним прибавляется нормировочное условие (11.12.2)

Ро + Pl + Р2 = L Выразим вероятности pv р2 из (11.12.1) через р0: X

ХУ Pi

Ро"Ро 5 Подставляя р1ир2в(И-12.2), получаем

(11.12.3)

р0 = {1 + X / (р, + v) + Xv / h (р, + у)]}"1 Чтобы найти относительную пропускную способность Qy нужно вероятность р0 ТОГО, ЧТО заявка будет принята к обслуживанию, умножить на условную вероятность pf того, что заявка, принятая к обслуживанию, фактически будет обслужена (канал не откажет за время обслуживания заявки). Найдем эту условную вероятность по интегральной формуле полной вероятности. Сделаем гипотезу, состоящую в том, что время обслуживания заявки попало на участок от t до t + dt; вероятность этой гипотезы приближенно равна f(t) dty где f(t) — плотность распределения времени обслуживания: f(t) = [ie~^ (t >0). Условная вероятность того, что канал не выйдет из строя за время ty равнаe~vt; отсюда оо

f \ie~^e-vidt

М'

Р

f^+^dt^

[і + У Эту условную вероятность можно найти и проще: она равна вероятности того, что начатое обслуживание закончится раньше, чем канал выйдет из строя. Представим на оси 01 (рис. 11.12, б) совмещение (суперпозицию) двух потоков: потока обслуживании с интенсивностью |j, (обозначен крестиками) и потока отказов канала с интенсивностью v (обозначен кружками). Зафиксируем любую точку t на оси Ot и найдем вероятность того, что А V _ 50 «1 52 * м<

Ч—© *-©—1—х х ©— к-©-©—х—

0 1 1 X - поток обслуживаний |i © - поток отказов и

б

первый после нее крестик придет раньше, чем кружок. Очевидно, она равна отношению интенсивности потока крестиков к суммарной интенсивности потока крестиков и кружков; р / (р + у).Таким образом, X

Ху

1 + -+Q = PoP'z

+ у

р + у ч(р + у)у A = \Q.

р + у + Ч (1 + у/ч) ' (11.12.4)

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

Решение. Граф состояний СМО дан на рис. 11.13. Из уравнений

(х + у')р0 =м>1 +ip2'> (м- + у)Рг 1P2 =vPi + у/р0;

Ро + Pl + Р2 = 1 найдем финальные вероятности -і

Ро =

j X Ху + ру; + уу'

Р + у

1 (и + у) X Ху + ру' + уу'

Pi

Ро; Р2= г—:—Ро;

р + у

ч (р + у) Хр Р + у

Q = Po

р + у

A = \Q = p0 11.14. Рассматривается простейшая одноканальная СМО с ограниченной очередью т = 2; работающий канал может иногда выходить из строя (отказывать). Заявка, которая обслуживается в момент отказа канала, становится в очередь, если в ней еще есть свободные места; если нет, она покидает СМО необслуженной. Интенсивность потока заявок X, потока обслуживаний р, потока отказов канала у, потока восстановлений (ремонтов) Перечис-лить состояния СМО и найти для них финальные вероятности, а °10

20 511 521 д00

°30 А V _ Ч * М- также характеристики эффективности СМО: А, к, г, z,tCHCT ,tOH при X = 2, [І = 1, У = 0,5, ч = 1.

Решение. Состояния СМО:

500 — СМО свободна, канал исправен;

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

sn — канал вышел из строя, ремонтируется; в СМО имеется одна заявка, ждущая очереди;

s20 — канал занят и исправен; одна заявка обслуживается, другая ждет очереди;

$21 — канал вышел из строя, ремонтируется; в очереди ждут две заявки;

s30 — канал занят и исправен; две заявки ждут очереди, одна обслуживается.

Граф состояний СМО показан на рис. 11.14. Уравнения для финальных вероятностей состояний:

M-Pio = Роо; М-Р2о + ЧРп + ХРоо = (м- + 1 + v) Pio;

то + 1P21 + хРю = (м- +1 + v) Р20;

ХР20 = (м- + V) РзО ; yP2О = (м- + V) РзО ; vPio = Ь + х) Рп; хРп + уР2о + уРзо = ч Р21 ;

Роо + Рю + Рп + Р20 + Р21 + Рзо = L

Решая эти уравнения при X = 2, Р, = 1, У = 0,5, Ч = 1, получаем:

Р00 = 3/61 « 0,049; = 6/61 « 0,098; р20 = 14/61 « 0,230;

р30 = 56/183 « 0,306; pj = 1/61 « 0,016; р21 =5/183 « 0,301.

Отсюда

z = 1 (р10 + Рп ) + 2 (р20 + р21) + 3 р30 = 383/183 « 2,09; г = 1 (р20 + рп) + 2 (р21 +р30) = 89/61 « 1,46. к = 1(р10 +р20 + р30) = 116/183 «0,63.

Абсолютная пропускная способность А для СМО с неотказы- вающими каналами могла бы быть найдена умножением к на р,; в нашем случае производительность одного канала (среднее число заявок, фактически обслуживаемых в единицу времени) можно найти, умножая к на вероятность \i / (|І + У) ТОГС^ ЧТО начатое об-служивание будет доведено до конца: А = к[і • [i / ([i + v) = = k\i2/ (|і + v) « 0,42.

11.15. В стоматологическом кабинете три кресла (п = 3), а в коридоре имеются три стула (га = 3) для ожидающих приема. Поток клиентов — простейший с интенсивностью X = 12 клиент/ч. Время обслуживания (приема клиента) — показательное со средним

значением to6cjl = 20 мин. Если все три стула в коридоре заняты, клиент в очередь не становится. Определить среднее число клиентов, обслуживаемых за час, среднюю долю обслуженных клиентов из числа пришедших, среднее число занятых стульев в коридоре, среднее время гсист, которое клиент проведет в коридоре и в кабинете; то же самое среднее время при условии, что клиент будет обслужен.

Решение, р = 12/3 = 4; х = р/3 = 4/3; п = 3; т= 3. По формулам (11.0.26)-(11.0.30) находим:

0,01218 « 0,012;

42 43 44 1 - (4/3)3'"1

Р о =

1 + 4+ — + —+

2 6 3-6 1 - 4/3

рг = 4 • 0,01218 « 0,049; р2 = 8 • 0,01218 « 0,097;

32 44

р3 = — • 0,01218 « 0,130; р3+1 = — • 0,01218 « 0,173;

3 36

4 4

Рз+2 = -Рз+1 ~ 0,231; р3+3 = -р3+2 ~ °>307о о

Средняя доля обслуживаемых клиентов Q = 1 — Р0ТН = = 1- р3+з « 1 - 0,307 = 0,693.

Среднее число клиентов, обслуживаемых за час, равно А = = 12-0,683 ^8,32.

Среднее число занятых каналов (кресел) [по формуле (11.0.27)] fc = 4(1-р3+3) «2,78.

Среднее число клиентов в очереди [по формуле (11.0.28)]

_ 44 • 0,01218 1 - 4 • (4 / З)3 + 3 (4 / З)4 т — ~ 1,5о;

3-6 (1 — 4 / 3)

z = г + к = 4,34; t04=r / X « 0,13 ч; *сист = z / X « 0,362 ч.

Такие малые значения ?сист и f04 связаны с тем, что некоторые клиенты уходят, не становясь в очередь. Условное среднее время, проведенное клиентом в системе, при условии, что он был обслужен, равно tQiiCT = tcmT / Q « 0,52 ч, а условное среднее время пре-бывания в очереди (при том же условии) tQ4 =t04 / <2 ~ 0,19 ч.

11.16. Формулы (11.0.26), (11.0.28) при х = 1 дают неопределенность вида 0/0. Раскрыть эту неопределенность и написать формулы, справедливые при х = 1Решение. При правилу Лопиталя

1-Xm —mx m_1

lim — = = га;

x=i 1 - х -X ' pn+1 - + -

n! n • n!

(11.16.1)

Ро

1+?+...+? 1! (11.16.2) (11.16.3)

Рк =7тРо (1 Pn+l — Pn+ 2 —•¦•— Pn+m ~ , P0>

n! т.е. все вероятности, начиная с pn и заканчивая рп+т, равны друг другу.

Формулы для A, Q, Р0ТК, к остаются прежними. Раскрывая неопределенность в формуле (1.1.0.28), получаем ТП +1

т (га + 1)

lim

х-1

1-(та+1)хт +тХ (1-х)2 (11.16.4)

г =

рп+1р0т (т +1) 2п • п! 11.18. Формулы (11.0.29), (11.0.30) остаются прежними.

Формулы (11.16.1)—(11.16.3) можно было бы вывести и не рас-крывая неопределенность, а непосредственно из схемы гибели и размножения.

11.17. 1) Подсчитать характеристики эффективности A, Q,

Р0ТК, к, г, z, t04, ?сист для простейшей одноканальной СМО с тремя местами в очереди (га = 3) при условиях: \ = 4 заявки/ч; * обсл — 1 / М- — 0,5.2) Выяснить, как эти характеристики изменяются, если увеличить число мест в очереди до га = 4.

Решение. |jl—2; р = \Ді = 2; по формулам (11.0.12)—(11.0.16) при тп = 3 имеем: р0 = 1/31; = 16/31; Q « 0,484; А = \<2 «1,93 заявки/ч; А; = р<3 ~ 0,968; г « 2,19 заявки; z « 3,16 заявки; ?оч « 0,55 ч^'сист ~ 0,79 ч.

2) При тп = 4 имеем = 1/63 « 0,0158; р5 = 32/63 « 0,507; Q « 0,493; Л « 1,96 заявки/ч; г « 3,11 заявки; z = 4,09 заявки;

t04 « 0,78 ч; fCMCT «1,02 ч.

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

Как изменятся характеристики эффективности СМО предыдущей задачи, если X и р остаются прежними, га = 3, но число каналов обслуживания увеличится до п = 2?

Решение, х = 1; по формулам (11.16.1), (11.16.2) имеем р0=1/11;р1 =...= р5 =2/11; <9 = 1 — 2/11 « 0,818; А « 3,27 заявки/ч; f = 12/11 « 1,09 заявки; к = А / р « 1,64; z = г + к « 2,73 заявки; ?оч «0,27ч;^"сист «0,68 ч.

Система массового обслуживания — билетная касса с одним окошком (n = 1) и неограниченной очередью. В кассе продаются билеты в пункты А и В; пассажиров, желающих купить билет в пункт А, приходит в среднем трое за 20 мин, в пункт В — двое за 20 мин. Поток пассажиров можно считать простейшим. Кассир в среднем обслуживает трех пассажиров за 10 мин. Время обслуживания — показательное. Установить, существуют ли финальные вероятности состояний СМО и если да — вычислить первые три из них: р0, pv р2. Найти характеристики эффективности СМО: z, r,tCMCT и tm.

Решение. \А = 3/20 = 0,15 заявки/мин; \в = 2 / 20 = 0,10 заявки/мин. Общая интенсивность потока заявок X = \А + + \в = 0,25 заявки/мин; р = 3 / 10 = 0,3 заявки/мин; р = X / р « « 0,833 < 1, финальные вероятности существуют. По формулам

(11.0.12)—(11.0.14): р0 « 0,167; Pl «0,139; р2 «0,116;

0,1 о/

« 4,99 заявки; г = 0,8332 / 0,167 « 4,16 заявки; ?сист « 4,99 / 0,25 «

« 20,0 мин; tQ4 « 4,16 / 0,25 « 16,7 мин.

Одноканальная СМО — ЭВМ, на которую поступают заявки (требования на расчеты). Поток заявок — простейший со средним интервалом между заявками t = 10 мин. Время обслуживания Тобсл распределено по закону Эрланга 3-го порядка с математическим ожиданием =8 мин. Определить среднее число z заявок в СМО и среднее число г заявок в очереди, а также средние времена пребывания заявки в системе tсист и в очереди tоч.

Решение. Характеристики СМО могут быть найдены по формуле Полячека — Хинчина (11.0.31), (11.0.32). Имеем: X = 0,1 заявки/мин; р = 0,125 заявки/мин; р = Х/р = 0,8.

Коэффициент вариации времени обслуживания для закона Эрланга 3-го порядка равен 1/л/З. По формуле (11.0.31) г=0,64 (1 + 1/3): (2- 0,2) «2,13. По формуле (11.0.32) z = г + 0,8 « « 2,93. По формуле Литтла tm « 21,3 мин, ?сист « 29,3 мин.

Условия предыдущей задачи изменены: поток заявок уже не простейший, а пальмовский, причем интервал между событиями в потоке распределен по обобщенному закону Эрланга 2-го порядка (см. задачу 8.31) с параметрами \г = 1/2; Х2 = 1/8. Найти

приближенно, по формулам (11.0.34)—(11.0.37), характеристики эффективности СМО.

Решение. Случайная величина Т, распределенная по обобщенному закону Эрланга 2-го порядка, есть сумма двух случайных величин Тг и Т2, распределенных по показательным законам с параметрами: lx — 1 / 2; \2 = 1 / 8. Отсюда Ы[Т] = 1 / Хх +1/\ = = 10 мин; D[Г] = Dp; ] + D[Т2 ] = 22 + 82 =68; v{ =68/102 = 0,68; v\ =

= 1/3. Следовательно, г = 1,62 заявки; z= 2,42 заявки; tQ4 =16,2 мин; ^сист =24,2 мин.

Техническое устройство (ТУ) может время от времени выходить из строя (отказывать). Поток отказов ТУ — простейший с интенсивностью X = 1,6 отказа в сутки. Время Тв восстановления (ремонта) ТУ имеет равномерное распределение на участке от 0 до 1 сут. Найти (для предельного стационарного режима) среднюю долю R времени, в течение которого ТУ работает.

Решение. Состояния ТУ: s0 — работает; sx — ремонтируется. Граф состояний ТУ показан на рис. 11.22, где ^ = 1 /М[ТВ] = = 1/0,5 = 2. Этот граф в точности совпадает с графом состояний одноканальной СМО с отказами. Мы знаем, что если поток заявок, поступающих на СМО, — простейший, а время обслуживания имеет произвольное распределение, то справедливы формулы Эрланга (11.0.6); в данном случае р = X/|л = 0,8; р0 = = {1 + р / 11}"1 = 1/1,8 « 0,556; рг = 1 - 0,556 « 0,444. Итак, R и

« 0,556, т. е. ТУ будет работать немногим более половины всего времени, а остальное время ремонтироваться.

В условиях предыдущей задачи ТУ дублировано точно таким же ТУ, которое может выходить из строя только в работающем состоянии; X, |л — такие_же, как в задаче 11.22. Найти величину R, а также среднее число к неисправных ТУ. X 50 51 52 * М- * 2LL Ы^Ы

Рис. 11.22 Рис. 11.23 Решение. Состояния системы S: s0 — оба ТУ исправны (одно из них работает, другое нет); sx — одно ТУ работает, другое ремонтируется; s2 — оба ТУ ремонтируются. Граф состояний дан на рис. 11.23. Граф в точности совпадает с графом состояний двухканаль- ной СМО с отказами. По формулам Эрланга (11.0.6)

+ г!

2!

1 +

Р о =

- {1 + 0,8 + 0,64 / 2} « 0,472;

pt ^ 0,8 • 0,472 = 0,378; R = р0 + рх « 0,850; р2 = 0,150;

к = 1 • рг + 2р2 = 0,678.

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

11.24. Система массового обслуживания — обувной магазин, в котором каждый покупатель проходит три фазы обслуживания: 1) примерка и выбор обуви; 2) уплата денег в кассу и 3) получение покупки на контроле. В магазин прибывает простейший поток покупателей с интенсивностью X = 45 чел/ч.

В отделе примерки имеются четыре стула, занимая которые, покупатели могут самостоятельно выбирать и примерять обувь. Среднее время примерки и выбора обуви tx = 5 мин. Выбравший обувь покупатель направляется в кассу, где вторично становится в очередь (касса в магазине одна). Среднее время оплаты товара в кассе t2 = 1 мин. После оплаты покупатель идет на контроль, где становится в новую очередь и получает покупку. На контроле работают три продавца; среднее время выдачи покупки t = 2 мин. Все потоки событий — простейшие.

Рассматривая магазин как трехфазовую СМО, найти характеристики ее эффективности:

~~ среднее число покупателей в очереди к первой (второй, третьей) фазе обслуживания;

zx (z2, z3) — среднее число покупателей, связанных с первой (второй, третьей) фазой обслуживания;

^оч(1), (tOH(2), f04(3)) — среднее время ожидания покупателя в очереди к первой (второй, третьей) фазе;

^сист(1)> (^сист(2)) ^сист(3)) ~~ среднее время пребывания покупателя в первой (второй, третьей) фазе обслуживания;

г — общее среднее число покупателей во всех трех очередях; z — общее среднее число покупателей в магазине; tоч — общее среднее время, проводимое покупателем в очередях; ^ сист ~~ общее среднее время, затрачиваемое покупателем на приобретение обуви в магазине.

Дополнительно ответить на следующие вопросы: 1) В каком звене и как нужно улучшить обслуживание для того, чтобы сокра-тить затраты времени покупателей? 2) Как можно было бы учесть тот факт, что не все покупатели находят себе подходящую обувь, и какая-то доля а из них (0 < а < 1) уходит из магазина, не сделав покупки?

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

1. Первая фаза. Так как в отделе примерки четыре стула, то число каналов пг = 4. Далее, имеем tx = 1/м-і = 5 мин = 1/12 ч; рг = 45/12 = 15/4 « 3,75; Xi = Pi /пі = 15/16 < 1- По формулам (11.0.21)—(11.0.25) находим: , огтг (3,75)2 (3,75) (3,75)4 1 + 3,75 + v ? J + v ? J + v ? J + 2 2-3 234

« (151,58)"1 « 0,0066; кг = 3,75;

+ (3,75)

2-3.4.4(1-15/16)

^ _ (3,75)5 р™

13,01; 1г = 16,76;

1 4-4! (l_Xl)2 iВторая фаза. X = 45; п2 = 1; р2 = 0,75 < 1. По формулам (11.0.12)—(11.0.14) получаем:

г2 = р2/(1 - р2) = 9/4 = 2,25; J2 = р2/(1 - р2) = 3; =г2/\х = 0,05 ч = 3 мин; t?]CT = 1/15 ч = 4 мин.

Третья фаза. п3 = 3; Х = 45; р3 =3/2; Хз =0,5< 1 . По формулам (11.0.21)—(11.0.25) находим: р{0г) « 0,210; г3 « 0,237;

J3 « 1,737; « 0,316 мин; *с(*>т « 2,316 мин.

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

г = гг + г2 + г3 « 15,5.

Аналогично находим среднее число покупателей в магазине z = Jj + z2 + z3 « 21,5.

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

*оч = *Среднее время пребывания покупателя в магазине ^сист = ^сист + ^сист + ^сист ~ 28,6 МИН.

1) Улучшить обслуживание можно, уменьшая время пребывания покупателя в первой фазе, которая представляет собой наиболее слабое звено СМО. Всего проще достигнуть этого, увеличив число пг стульев в отделе примерки, т.е. число каналов обслуживания в первой фазе. Например, простое увеличение числа стульев на единицу (т.е. переход от щ = 4 к щ = 5) дает существенный выигрыш во времени. Действительно, при щ = 5 для первой фазы получим:

Pi =3,75; xi = 3,75/5 = 0,75; р™ = {59,71}"1; r2 «2,08;

^ « 5,13; « 1,84 мин; ^ « 6,84 мин.

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

На железнодорожную сортировочную станцию поступает эрланговский 10-го порядка поток составов с интенсивно-стью Х = ^2 состава/ч.1^ Время обслуживания состава Тобсл распределено в интервале от 0 до 1 ч по закону с плотностью ip(t), показанной на рис. 11.25. Оценить приближенно [по формулам (11.0.34)—(11.0.37)] характеристики эффектив-ности станции — среднее число z составов на станции, в очереди г, среднее время tCUCT пребывания состава на станции, среднее время tQ4 ожидания составом очереди на обслуживание.

Решение. Для закона tp (t) имеем to6cjl = 1 / 3; р = X / р = 0,8 < 1. Для потока Эрланга 10-го порядка vl = (1 / Vfc)2 =0,1; v2 определяем, разделив дисперсию D[Тобсл] на квадрат математического ожидания: v2 = 1 / 2 = 0,5.

Находим характеристики СМО: г = Р2 х + К ) / [2 (1 " Р)] = 0,82 (0,1 + 0,5) / (2 • 0,2) = 0,96;

z = г + р « 0,96 + 0,8 = 1,76; tm =г /Х«0,8ч; ісист = їоч + 1/р« 1,13ч.

Показать, что для простейшей п-канальной СМО с неограниченным числом мест в очереди среднее число заявок, находящихся в очереди, заключено в пределах

< г < ¦

1-х хп(п-1) + 1 1-х

Решение. Запишем выражение для г в следующем виде [см. формулы (11.0.23), (11.0.21)]:

- Рп+1 Ро X ?п

Г = - Г,, ч2 ~ /і \2 Рп^ЖРп =^-7Р0п-п\( 1-х (1-Х ПІ

^ Подчеркнем, что здесь X — интенсивность именно эрланговского потока, а не того простейшего потока, прореживанием которого получен эрланговский. Следовательно,

р"

Рп

1 + р + JL.+...+ Р_+Р 2L

П\

2 n! n!1 - xj -1

X

>

п п (п 1 + - + —— X X

= xn(i-x).

1 +

>

х

р р2 р С другой стороны, xn(i-x)rc

Xn(n-l) + l'

ті —1

X

1 + - +

Рп <

п п Т+—+ +

р р2 Pn 1-xJ Так как [Xn (1 - х) п] / [Xn (п - 1) + 1] < рп <ХП(1"Х), то указанное в задаче неравенство также выполняется. Заметим, что последнее неравенство может быть использовано для приближенного определения всех характеристик рассматриваемой СМО.

11.27. Железнодорожная касса имеет два окошка, в каждом из которых продаются билеты в два пункта: Ленинград и Киев. Потоки пассажиров, приобретающих билеты в Ленинград и в Киев, одинаковы по интенсивности, которая равна Х0 =0,45 пасс/мин. Среднее время обслуживания пассажира (продажи ему билета) *"обсл — 2 мин.

Поступило рационализаторское предложение: для уменьшения очередей (в интересах пассажиров) сделать обе кассы специа-лизированными: в первой продавать билеты только в Ленинград, а во второй — только в Киев. Считая в первом приближении все потоки событий простейшими, проверить разумность этого предложения.

Решение. 1) Вычислим характеристики очереди для двухка- нальной СМО (существующий вариант). Интенсивность потока заявок X = 2Х0 =0,9 пасс/мин; [І = 1 /= 0,5 пасс/мин; р = X / [І = 1,8; х = Р / 2 = 0,9 < 1, финальные вероятности сущест-вуют. По формуле (11.0.21)

-і 1,8 , 1,8 1

: 0,0525;

Ро =

4 1-0,9

1 + 1,8 + + по формуле (11.0.23)

7 7

= — « 8,56 мин. 0,9

: 7,7 пасс; tc

__ 1,83 - 0,05 25 Г~ 2-2.0,01 2) Во втором варианте (предлагаемом) имеем две одноканаль- ные СМО: р = Х0 / р = 0,45 / 0,5 = 0,9 < 1.

Средняя длина очереди у одной кассы [по формуле (11.0.13)] равна г = р / (1 — р) = 0,92 / 0,1 = 8,1 пасс. Суммарная длина очереди к обеим кассам будет 2г = 16,2 пасс.

Время пребывания пассажира в очереди (11.0.14) t04 = г / X = = 8,1 / 4,5 = 18 мин, что почти вдвое превосходит время стояния в очереди в существующем варианте: 8,6 мин.

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

11.28*. Простейшая многоканальная СМО с «нетерпеливыми» заявками и с неограниченным числом мест в очереди. Имеется простейшая n-канальная СМО с очередью; интенсивность потока заявок X, потока обслуживаний р = 1 /. Время пребывания заявки в очереди ограничено некоторым случайным сроком Т, распределенным по показательному закону с параметром у (на каждую заявку, стоящую в очереди, действует «поток уходов» с интенсивностью у).

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

X X X X X ___ X X

М- 2р 3 р k\i яр np-fv np-frv

Рис. 11.28

Решение. Состояния системы по-прежнему будем нумеровать соответственно числу заявок, находящихся в СМО. Граф со-стояний показан на рис. 11.28. Пользуясь общими формулами для схемы гибели и размножения и вводя обозначения р = X / р; (3 = у / р, получаем:

Pl =т;Ро;-; Рк — ТТ^о (1 <к<п);...; рп = ^—р0] 1! к! п!

Р

= 4 •, ^ow л; , ¦ Ро(г > 1);... ¦ (11-28.1) п! (п + (3)(п + 2(3)... (п + г(3)

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

* « рп (р/РГ -Р/р

бесконечной суммы, начиная с г-го, меньше, чем -— -—-—— е р/р.

п\ г!

Предположим, ЧТО вероятности Ро,Рх, ... , рп , ... , рп+г, ... вычислены, и покажем, как можно найти характеристики данной СМО: относительную пропускную способность Q, среднее число заявок в очереди г и др. Найдем прежде всего Q. Обслужены будут все заявки, кроме тех, которые уйдут из очереди досрочно. Подсчитаем, сколько заявок в среднем уходит из очереди досрочно в единицу времени. Интенсивность потока уходов, приходящаяся на одну заявку, стоящую в очереди, равна У, а суммарная средняя интенсивность потока уходов, приходящаяся на все заявки, стоящие в очереди, равна у г. Значит, абсолютная пропускная способность СМО

А = \-vr, (11.28.2)

а относительная

Q = A/ \ = l-vr/\. (11.28.3)

Таким образом, для того чтобы найти Q, нужно прежде всего знать г, которую непосредственно можно было бы найти по формуле г = 1рп +1 +2рп+2 +...+ грп+г +... . Но эта формула плоха тем, что содержит бесконечное число слагаемых. Этого можно избежать, если воспользоваться выражением для среднего числа занятых каналов к через А: к = А / или, учитывая (11.28.2),

к = (X - у г) / \l = р - рг. (11.28.4)

Из (11.28.4) получим

г = (р - А) / р, (11.28.5)

а среднее число занятых каналов к можно подсчитать как математическое ожидание случайной величины К (число занятых каналов) с возможными значениями 0, 1, 2, ..., п и соответствующими вероятностями Ро, Pv р2, ...,РП_!,[1 - Оо + Pl+—Pn-l)l:

fc = lp1+2p2+... + (n-l)pn_1 + + n[l-(p0 + p1+... + pll_1)]. (11.28.6)

Далее по формуле (11.28.5) вычисляем г. Величину tQ4 находим по формуле Литтла: (11.28.7)

(11.28.8)

(11.28.9)

tm=f/\. Среднее число заявок в СМО

z = г + к,

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

^ сист = Z / Примечание. Можно доказать, что для рассмотренной СМО с «нетерпеливыми» заявками финальные вероятности существуют всегда, если только (3 > 0. Это подтверждается тем, что ряд в первой формуле (11.28.1) сходится при любых положительных р и (3. По существу это означает, что очередь не может расти неограниченно: чем больше длина очереди, тем интенсивнее уходят из нее заявки.

11.29. Рассматривается простейшая двухканальная СМО с «нетерпеливыми» заявками (см. задачу 11.28). Интенсивность потока заявок X = 3 заявки/ч; среднее время обслуживания одной заявки to6cjl — 1 / р = 1 ч; средний срок, в течение которого заявка «терпеливо» стоит в очереди, равен 0,5 ч. Подсчитать финальные вероятности состояний, ограничиваясь теми, которые не ^еньше 0,001. Найти характеристики эффективности СМО: Qy Аук, f, tQ4, tcllcT.

Решение. Имеем X = 3, р = 1, у = 2; р = 3, (3 = 2, п = 2. По формулам задачи 11.28 получаем:

4-6-8-10

+ -і 0,0692;

+

+

+

4-6-8-10-12-14-16

4-6-8-10-12 4-6-8-10-12-14 откуда

р, = Зр0 « 0,208; р2 = | Pl « 0,311; р3 = | р2 « 0,234;

р4 = §р3 « 0,117; р5 = |р4 « 0,044; р6=^-р5ъ 0,013; о 8 1U з з

Рі =— Рб -0,003; ps=—p7 «0,001. 12 18

Среднее число занятых каналов согласно (11.28.6): & = 1 pt + + 2 (1 — рд — рг) « 1,654; средняя длина очереди согласно (11.28.5) г = (р — /г)/(3 = (3 — 1,654)/2 « 0,673; абсолютная пропускная способность А — k\i « 1,654 заявки/ч; относительная пропускная способность Q = А [К « 0,551 и далее: tQ4 = r/X « 0,224 ч; z = = f + к « 2,327; ?сист = z/\ « 0,776 ч.

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

Решение. Состояния СМО: s0 —СМО свободна; очереди нет;

sx — занят один канал;...; sk —занято к каналов (1 < к < п);...; —заняты все п каналов sn+r — заняты все п каналов, а г заявок стоят в очереди (r= 1, 2, ...).

X X X X X X X X

htJjitr--^

1 1 rv n^ I r^t • -rv rv1 1 rv rv ' ' rv

Рис. 11.30

Граф состояний приведен на рис. 11.30, где р = рр. Из этого графа видно, что данная СМО эквивалентна другой СМО с полной гарантией качества обслуживания, но с интенсивностью потока обслуживаний, равной р = рр; для этой СМО р = Х/ р = Х/ (рр). Формулы (11.0.21)—(11.0.25) остаются справедливыми, но при замене р на р, р на р.

11.31. Простейшая одноканальная замкнутая СМО. Один рабочий обслуживает т станков, которые время от времени отказывают (требуют наладки). Интенсивность потока отказов одного станка равна X. Если в момент отказа станка рабочий свободен, он немедленно приступает к наладке; если нет — станок становится в очередь на наладку, поток отказов станка простейший, время наладки — показательное с параметром р = 1 /1 обсл. Ввести состояния СМО, нумеруя их по числу неисправных станков; найти финальные вероятности состояний СМО и следующие характеристики ее эффективности: А — среднее количество станков, ремонтируемое рабочим в единицу времени; w — среднее число неисправных станков; г — среднее число станков, ожидающих ремонта в очереди; Рзан — вероятность того, что рабочий будет занят. Решение. Состояния СМО: s0 — все станки исправны (рабочий свободен); sx — один станок неисправен (рабочий занят его наладкой); ...; sk — к станков неисправны, один налаживается, к — 1 ждут очереди;

sm — все га станков неисправны, один налаживается, га — 1 ждут очереди.

Граф состояний показан на рис. 11.31.

Рис. 11.31

По общим формулам схемы гибели и размножения, обозначая р = Х/р, получаем

Ро = {1 + + т (т ~ 1) р2+...+ +га (га - 1)... (га - к + 1) р*+...+га !рш-1;

рг^трроі Р2=т(га-1)рЧ;...;

рк = га (га — 1)... (га — к + 1) ркр0 (1 < к < п);...;

рт =т\ртр0. (11.31.1)

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

Рзан =1-П0. (И.31.2)

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

Л = (1-р0)ц. (11.31.3)

Среднее число неисправных станков w можно выразить через А с помощью следующих рассуждений. Каждый работающий станок порождает поток отказов с интенсивностью X; в среднем работает т — w станков; порождаемый ими поток отказов имеет интенсивность (т —w) X; все эти неисправности ликвидируются рабочим, значит, (1 — р0)\х — (т — w)\ откуда

W = 771 (1 Pq ) / р. (11.31.4)

Среднее число г станков в очереди найдем следующим путем:

w = r + k, (11.31.5)

где к — среднее число обслуживаемых станков (или, иначе, среднее число занятых каналов обслуживания). В нашем случае число занятых каналов равно 0, если рабочий свободен, и 1, если он занят: к = 0 • р0 + 1 (1 — Ро) = 1 — Ро- Следовательно,

Г = 771 - (1 - Ро) / 9 - {I - Ро)

или

г = т -(1-р0)(1 + 1/р). (11.31.6)

11.32*. В условиях задачи 11.31 найти среднее время tQ4, которое будет ожидать наладки произвольно выбранный вышедший из строя станок.

Решение. Формула Литтла, которой мы пользовались ранее, пригодна только для открытых СМО, где интенсивность потока заявок не зависит от состояния СМО.Для замкнутых СМО она непригодна. Время tQ4 найдем с помощью следующих рассуждений. Пусть в какой-то момент t появилась заявка (отказал станок). Найдем вероятность того, что в этот момент СМО находилась в состоянии sk (к = 0, ..., т — 1) (ясно, что в состоянии sm она находиться не могла). Рассмотрим тп гипотез:

Но — в момент появления заявки СМО находилась в состоянии

Нг — в момент появления заявки СМО находилась в состоянии

Нк — в момент появления заявки СМО находилась в состоянии

sk> - >

Hm_ j — в момент появления заявки СМО находилась в состоянии 5m_t.

Априорные вероятности этих гипотез равны pQy pv ркУ

•••>Pm-V

Теперь найдем апостериорные вероятности гипотез при условии, что наблюдено событие А = {на элементарном участке времени (і, t + dt) появился отказ станка}. Условные вероятности этого события при гипотезах Н0, Hv ..., Нт_1 равны:

Р (А\Н0) = m\dt; Р (А\Н1) = (m - 1) ХА;...; Р (А\Нк ) = (т - к) \dt;...; Р (А\Нт_г) = \dt.

По формулам Бейеса найдем апостериорные вероятности гипотез (при условии, что событие А произошло). Обозначая эти вероятности р0, р1,..., рк,..., рт , получаем: (т - 1) рх

р1 ~ т—1

]П(т -к) рк

к=О

Ро

тр о

m-1

^(т - к) рк

к=0

т—1

(11.32.1)

Рк

Ут-1

(т - к) рк а

т—1

т—1

~ fc) Л

Х> ~Рк

fc=0

к=о Зная эти вероятности, найдем полное математическое ожида-ние времени пребывания отказавшего станка в очереди. Если станок отказал в момент, когда система находится в состоянии s0, он не будет стоять в очереди; если в состоянии sv то будет находиться в ней в среднем время 1 / р, если в состоянии s2 — время 2 / р и т.д. Умножая вероятности (11.32.1) на эти числа и складывая, получаем (11.32.2)

_ j: т—і

^ к=1 Проводя аналогичные рассуждения, можно получить выражения для плотностей распределения случайных величин: Точ — времени нахождения в очереди и Тпр — времени простоя станка:

t* ЫУ ^ (*-1)!

m-1.. ґ..*\к-1

/оч(0 = 6(0Р0 + Е

(11.32.3)

m-1. к\

к=О При этом будет иметь место равенство:

М[Тпр} = М[Точ] + М[Т^} = t02 + I,

м- где

т —1

Р іm_1

t02=J (0 =

О ^ *=1

Находим рк

_Р(т~к>х). х = ^ * R(m,x) ' X (т - к) Р(т - к2,х) / R(m,x) Р* =

j2(m-k)P(m-k,X)/P(m,X)

Л-=0

(m — /с) Р(т — к, х) (т — /с) Р(т — А, х) А:=0 /:=0

(к — 0,..., т - 1).

(т - А) Р(т -к,х) Р(т - к- 1, х)

X Л(т - 1, х) R (т — 1, х)

Следовательно, ^ А;! (то — 1 — A;)!R (то — 1, х) еR (m -1, х)(т -1)! й) Л! (пг — 1 — Л)!

¦(1 + х*)г

(т — 1, х) (л ,

R (т -1,х)

Таким образом, мы показали, что fQ4(t) и /пр(0 представляют собой вероятностную смесь законов распределения.

11.33. Рабочий обслуживает четыре станка (га = 4); каждый станок отказывает с интенсивностью X = 0,5 отказа/ч; среднее время ремонта TP =1 / |JL = 0,8 ч. Все потоки событий — простейшие. Пользуясь формулами задач 11.31, 11.32, найти: 1) финальные вероятности состояний; 2) пропускную способность А; 3) среднее относительное время простоя рабочего Рпр; 4) среднее число станков в очереди г; 5) среднее число неисправных станков гй; 6) среднее время пребы-вания в очереди tQ4 одного отказавшего станка; 7) среднюю производительность группы станков с учетом их неполной надежности, если в работающем состоянии один станок дает / единиц продукции.

Решение.|л = 1/1 = 1,25; р = X / |л = 0,4.

1) По формулам (11.31.1) имеем:р0 = {1 + 1,6 + 1,92 + 1,53+ + 0,61}-1 = 6,66-1 « 0,150; рг = 1,6р0 « 0,240; р2 = 1,92р0 « 0,288;

р3 = 1,53р0 « 0,230; рА = 0,061р0 « 0,092; А = 0,850(і, « 1,06 станка/ч;

.Р = = 0Д50;

г « 4 - 0,850 (1 + 2,5) « 1,03;

w « 1,03 + A; « 1,03 + 0,85 = 1,88;

4р0+3Рі+2Р2+Рз

26) по формулам (11.32.1) и (11.32.2) р0 = « 0,283; рг « 0,340; р2 = 0,270; р3 = 0,108;*оч = 0,8 (рг + 2р2 + Зр3) « «0,964 ч;

7) производительность группы станков равна (га — w)l « 2,12I. 11.34. Простейшая многоканальная замкнутая СМО. Бригада из га рабочих обслуживает га станков (га < га). Поток отказов каждого станка имеет интенсивность X; среднее время наладки станка ^обсл = 1 / И- Все потоки событий — простейшие. Найти финальные вероятности состояний СМО; абсолютную пропускную способность А; среднее число неисправных станков w.

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

Sq — все станки исправны, рабочие не заняты; sx — один станок неисправен, один рабочий занят, остальные свободны; ...;

sk — к станков неисправны, к рабочих заняты, остальные свободны (к < га); ...;

sn — га станков неисправны, все рабочие заняты; sn+1 ~~ п + 1 станков неисправны, из них га налаживаются, один стоит в очереди; ...;

sn+r — га + г станков неисправны, из них га налаживаются, г в очереди (га + г < га);...;

sm — все га станков неисправны, из них га налаживаются, га - га ждут очереди.

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

р* +

Ро =¦

+...+

х

го (го - !)••• (та - п) +1

га (га — 1)... (га — к + 1) к

jfc! Р + га (га — 1)... [га — (га + г — 1)] -і

га

хрп+г+...4 га га (га — 1) 2 Pi = у[РР°; = —Р Ро;---'» Рп =—- -—: р" Ро; - - •;

га!

т (т — 1)... \т — (га + г — 1)1 _ ,

Рп+Г = — , г "Рв+гРо (1 < г < т - 1);

га!га

Рт = —^Ря,Ро>гдер = Х/м.. (11.34.1)

га \п

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

к — 0 • р0 + 1рг + 2р2+...+(га - 1) рп_1 + га (рп + рп+1 +...+Рт) = = рг + 2p2+...+(ra-l)pn_1 +га(1-р0 -^-...-р^). (11.34.2)

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

А = к\х, (11.34,3) а среднее число неисправных станков

w = m-k\x/\ = m- k/ р. (11.34.4)

11.35. Двое рабочих (га = 2) обслуживают шесть станков {т = 6). Станок требует наладки в среднем через каждые полчаса. Наладка занимает у рабочего в среднем 10 мин. Все потоки событий — простейшие. 1) Определить характеристики СМО: среднее число занятых рабочих к; абсолютную пропускную способность А; среднее число неисправных станков w; 2) Установить, улучшатся ли характеристики СМО, если рабочие будут налаживать станки совместно, тратя вдвоем на наладку одного станка в среднем 5 мин.

: 0,153;

6-5-4-3-2 1 | 6 • 5 • 4 • 3 • 2 -1 1 1-2-23 З5 1-2-24 З6

рг = 6/1-1/3 - р0« 0,306.

Среднее число занятых рабочих находим по формуле (11.34.2); к = 1 • рх + 2 (1 - р0 - рг) « 1,235. Абсолютная пропускная споРешение. 1) Решаем задачу в первом варианте (рабочие налаживают станки порознь). Имеем т — 6; га = 2; X = 2; р = 6;р = Х/р = 1/3. По формулам (11.34.1)

собность А = к\х «7,41. Среднее число неисправных станков w = 6 - 7,41 / 2 « 2,30.

2) Если рабочие налаживают станки вместе, то СМО превращается в одноканальную (ra = 6;n=l) прир = 12. Расчеты произведем для р = Х/ р = 1/6. По формулам (11.31.1)

1 + 1 + +— + 654 + 6-5'4'3 + 6-5-4-3-2

Ро

6-5-4.32-1

: 0,264; р1 « 0,264; р2 « 0,220; « 0,147;

0,736

+ : 1,59.

р, « 0,076; « 0,024; р6 « 0,004; w = 6 1/6

Среднее число занятых каналов к = 1 - = 0,736. Однако, учитывая, что «канал» обслуживания состоит в данном случае из двух рабочих, среднее число занятых рабочих будет

V = 2 - 0,736 « 1,47; А = к\х — 0,736 • 12 « 8,8.

Таким образом, взаимопомощь между рабочими (каналами обслуживания) в данном случае повысила среднюю занятость с 1,23 до 1,47, снизила среднее число неисправных станков с 2,30 до 1,59 и повысила пропускную способность с 7,4 до 8,8.

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

1+1+*+* 1! 2! 3!

Ро

; 0,158; Ротн =р3 =— р0 «0,21;

Q = 1 — Ротн ~ 0,79; Л = \д«3,16.

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

2) Объединяем все три канала в один с параметром р = 3 • 2 = 6; получаем

Решение. 1) Находим вероятности состояний СМО без взаимопомощи между каналами по формулам Эрланга (11.0.6):

Ро=- ~Т~ГТ = 0,6; рх — (2/3) 0,6 = 0,4;

(1 + 2/3)

Ротк — Р\ — 0,4; g = 1 - Ротк = 0,6; A = \Q = 4-0,6 = 2,4.

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

Среднее время пребывания заявки в СМО во втором варианте будет меньше, чем в первом: tCUCT = Q (1/6) = 0,1 мин. Однако это уменьшение куплено «дорогой ценой» — тем, что ряд заявок вовсе не обслуживаются и, значит, проводят в СМО нулевое время.

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

11.37. Имеется простейшая трехканальная СМО с неограниченной очередью. Интенсивность потока заявок X = 4 заявки/ч; среднее время обслуживания^^ = 1 / р = 0,5ч. Выгодно ли, имея в виду: 1) среднюю длину очереди, 2) среднее время пребывания заявки в очереди, 3) среднее время пребывания заявки в СМО, объединить все три канала в один, с втрое меньшим средним временем обслуживания?

Решение. 21) В первоначальном варианте (трехканальная СМО): п = 3, Х = 4,р = 1/0?=2;р = Х/р = 2;х = р/л = 2/3<1.

Финальные вероятности существуют. Вычисляем р0 по формулам (11.0.21):

2 22 2* 24 -(1/3)

14 1 1 г •

Р о =

1! 2! 3! 3!(1 — 2/3)

О4. 1/Q Q _ Г 9

г = -!¦ = - » 0,889; = 0,222 ч;

3 • З! (1 / З)2 9 °ч X 9

<с„ст +to6 ~ 0,722.

2) При объединении трех каналов в один: п = 1;Х = 4;|х = 6; р = 2/3. По формулам (11.0.12)—(11.0.14) имеем

(2 / З)2 - г

г = { ' ' и 1,333; * = - я 0,333 ч; 1/3 °ч X

<с„ст = tm + to6 = 1 / 3 + 1 / 6 = 0,500.

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

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

11.38. Рассматривается система массового обслуживания — стоянка такси, на которую поступают простейший поток пассажиров с интенсивностью X и простейший поток автомобилей с интенсивностью р,. Пассажиры образуют очередь, которая уменьшается на единицу, когда к стоянке подходит автомобиль (берется «идеальный» случай, когда водитель безропотно везет каждого пассажира туда, куда ему требуется). В случае, если на стоянке нет пассажиров, в очередь становятся автомобили. Число мест для автомобилей на стоянке ограничено (равно га); число мест в очереди для пассажиров также ограничено (равно /). Все потоки событий — простейшие. Посадка производится мгновенно. Построить граф состояний СМО, найти финальные вероятности состояний, среднюю длину гп очереди пассажиров, среднюю длину гт очереди автомобилей, среднее время tQ4 n пребывания в очереди пассажира, среднее время tQ4T пребывания в очереди такси и посмотреть, как эти характеристики изменятся при га —> оо, I —> оо.

Рис. 11.38

X Мst, о

50,ш Решение. Состояния СМО будем нумеровать соответственно числу пассажиров и автомобилей на стоянке двумя индексами: первый — число пассажиров, второй — число автомобилей. Состояние Sq q означает, что на стоянке нет ни пассажиров, ни автомобилей; состояние s0 к — нет автомобилей, к пассажиров; состояние 5с0 — с автомобилей, ни одного пассажира. Граф состояний СМО показан на рис. 11.38. Граф соответствует схеме гибели и размножения. Применяя общие формулы (11.0.4) для этой схемы и обозначая X / р = р, получаем:

Pi-i,o = рр/,о; Pi-2,о = р2р/,о; • • -; рс,о = р'~с.р/,о; •••; (11.38.1)

Pi,о ={l + P + p2+...+p'+m}_1 или, суммируя геометрическую прогрессию со знаменателем р,

pii0=(l-p)/(l-p'+m+1). (11.38.2)

Вероятности (11.38.1) образуют геометрическую прогрессию с первым членом Pi о и знаменателем р. Если р > 1, наивероятнейшее состояние системы будет 50 т — автомобилей нет, все места в очереди пассажиров заняты; если р < 1 — наивероятнейшее состояние sl 0 — пассажиров нет, все места в очереди автомобилей заняты.

При т —> оо,/ —> оо финальные вероятности не существуют; при р > 1 очередь пассажиров, а при р < 1 очередь автомобилей имеют тенденцию возрастать неограниченно (эта тенденция сдерживается тем, что как число пассажиров, так и число такси в городе бесконечными быть не могут).

11.39*. В столовой самообслуживания имеется один раздаточный пункт, на котором отпускаются как первые, так и вторые блюда. Поток посетителей столовой — простейший с интенсивностью X; на отпуск как первого, так и второго блюда идет случайное время, распределенное по показательному закону с одним и тем же параметром р. Некоторые посетители берут и первое, и второе (доля таких посетителей равна q), другие — только второе (доля 1 — q). Найти: 1) условия, при которых существует устойчивый, стационарный режим работы столовой; 2) среднюю длину очереди и среднее время пребывания посетителей в столовой, если посетитель съедает одно блюдо в среднем за время т, а два блюда — за время 2т.

Решение. Время, идущее на обслуживание одного посетителя, представляет собой случайную величину Г, распределенную с вероятностью q по закону Эрланга 2-го порядка, со средним значением to6cJl = 2 / р, а с вероятностью (1 - q) — по показательному закону с параметром р. Найдем математическое ожидание случайной величины Г. Для этого воспользуемся формулой полного математического ожидания с двумя гипотезами: Нх = {посетитель берет только второе блюдо}; Н2 = {посетитель берет оба блюда}. Вероятности этих гипотез: Р (Нг) = 1 — q \ Р (Н2) = q.

Полное математическое ожидание случайной величины Травно

М[Г] = Р (Нг) М[Т\Нг ] + Р (Я2) М[Т|#2 ] = (1 - q)(1 / р) + +значит, столовая может обслуживать в среднем р / (q + 1) посетителей в единицу времени; если X > р / (q + 1), то СМО перегружена, и финальные вероятности не существуют, если же X < р / (q + 1), то они существуют. Предположим, что X < р / (q + 1).

Для нахождения средней длины очереди г, средних времен пребывания заявки в очереди tD4 ив системе (столовой) ?сист воспользуемся формулой Полячека — Хинчина (11.0.31). Для этого надо знать коэффициент вариации случайной величины Т — времени обслуживания. Найдем сначала второй начальный момент этой величины М[Т2]. По формуле полного математического ожидания (с теми же гипотезами Нх и #2) получим

М[Т2] = (1 - q) М[Т2\Нг] + дМ[Т2|#2]. (11.39.1)

При гипотезе Нг случайная величина Т распределена показа-тельно с параметром р:

М[Г2\Н,) = D [Т\Нг} + (М[Т\Нг ])2 = 1 / ц2 + (1 / ц)2 = 2 / ц2.

При гипотезе Я2 вычислим второй начальный момент величины Г по формуле

М[Г2|Я2] = В[Г|Я2]+(М[Г|Я2])2.

Но М[Г|Я2] = 2 / |л, (М[Г|Я2])2 = 4 / р2; дисперсия В[Г|Я2]

вдвое больше, чем ЩТ\Нг], как дисперсия суммы двух независимых одинаково распределенных случайных величин Тг и Т2, т.е. D[T\H2] = 2 / р2. Следовательно,

М[Г2|#2] = 2 / (X2 -t- 4/|х2 —6 / |х2, откуда по (11.39.1)

М[Т2]=(1-д)2/^+д6/\12 =2(1 + 2д)/ц2. Дисперсия случайной величины Г

D[T] = М[Г2 ] - (М[Г])2 =(1 + 2q-q2)/»2;

отсюда коэффициент вариации случайной величины Г

^ = Vl + 2q-q2 /(? + 1).

Подставляя это выражение ир = Х(^ + 1)/рв формулу Поля- чека—Хинчина (11.0.31), получаем 1+1 + 2q~q2

(Х2/>х2)(1 + 2д)

(<7 + 1У

(Х2/ц2)(9 + 1): f —

2[l-(X/ji)(g+ 1)] 1-(Х/ц)(д + 1)

Далее

fOM = г/Х; ї"сист =їоч +(д + 1)/ц + (g + 1) т = їоч + (g + 1) (т + 1/ц).

11.40. Пример простейшей СМО с отказами и с приоритетом. Имеется двухканальная СМО с отказами, на которую поступают два простейших потока заявок: I с интенсивностью \г и II с интенсивностью \2 (будем кратко называть их «заявки I» и «заявки II»). Заявки I имеют перед заявками II приоритет, состоящий в следующем: если заявка I приходит в момент, когда все каналы заняты и хотя бы один из них обслуживает заявку II, то пришедшая заявка I «вытесняет» из обслуживания заявку II, становится на ее место, а та покидает СМО необслуженной. Если заявка I приходит в момент, когда все каналы заняты обслуживанием заявок I, то она получает отказ и покидает СМО. Заявка II получает отказ, если она приходит в момент, когда заняты оба канала (безразлично какими заявками).

Построить размеченный граф состояний СМО, нумеруя состояния двумя индексами (г, j); первый указывает число заявок I, второй — число заявок И, находящихся в СМО. Написать уравнения для финальных вероятностей состояний. Решить их при \г = \2 = рх = р2 = 1. Выразить через р{- (г + j < 2) следующие характеристики эффективности СМО:

PQTK (^отк ) ~~ вероятность отказа в момент поступления для заявки I (II);

Аг (А2) — среднее число заявок I (И), обслуживаемое СМО в единицу времени;

К $2) ~~ сРеДнее число каналов, занятых обслуживанием зая-вок I (II); _

РОТК, А, к — те же характеристики для СМО в целом, безотносительно к виду заявок.

Решение. Состояния СМО: s00 — в СМО нет заявок; s10 — в СМО одна заявка I и ни одной заявки И; s01 — в СМО ни одной заявки I и одна заявка И; s20 — в СМО две заявки I и ни одной заявки И; Sj j — в СМО по одной заявке I и И; s02 — в СМО ни одной заявки I и две заявки И. Размеченный граф состояний СМО дан нарис. 11.40.

Уравнения для финальных вероятностей состояний:

(Х1 + Х2)р00 = р1р10 + р2р01; + Х2 + рг)р10 =\Роо + 2рх х хр2о + М-2Рц 5 = \Рю + \Рп 5

+ х2 +М*2) х Рої = Х2Роо +М«іРіі + 2р2р02;

+М-1 +^2)Pii:=X2Pio+XiPoi + XiPo2; (Xi + 2р2) р02 = Х2р01;

Poo + Pio + Р20 + Рої + Рп + Ро2 = L

Решая их при \ = Х2 = рх = р2 = 1, получаем

poo =0,20; p10 =0,25; p20 =0,20; Рої =0Д5; Рг =0,15; p02 =0,005; P^ = p20 = 0,2;

= Pm + Pu + Pm =0.40; Л1=Х1(1-Р(Т1') = 0,8.

Величину a2 вычислим, учитывая то, что некоторые заявки II, принятые к об- рис її.40

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

Среднее число таких заявок в единицу времени равно \п (рп + р02), следовательно,

А2 = Х2 [1 - (р20 + Рп + Ро2 )] - Х1 (Pll + Ро2 ) = °>4І

= А / Ш j ~ / М-2 •

Вероятность Ротк того, что произвольно выбранная заявка, поступившая в СМО, получит отказ, найдем по формуле полной вероятности с гипотезами: Нх = {пришла заявка I}; Н2 = {пришла заявка II}. Вероятности этих гипотез

Р(Я1) = Х1 /(X, +Х2); Р(#2) = Х2 / (Xj + Х2).

Следовательно, X,

X,

_р( і) ¦*¦ /YTV

Р = ¦

+ '

PL2! =од

+ Х2

(Х1+Х2) Заметим, что все характеристики для заявок I можно было бы получить, совершенно игнорируя заявки II и рассматривая задачу так, как если бы на двухканальную СМО с отказами поступали только заявки I. Предоставляем читателю убедиться в этом, подсчитав все характеристики для двухканальной СМО с отказами, на которую поступает только поток заявок I.

11.41. Условия предыдущей задачи изменены так, что количество каналов СМО с отказами равно п = 3. Построить граф состояний СМО. Написать уравнения для финальных вероятностей Pij (і + J ^ 3), где і — число заявок I, j — число заявок И, находящихся в СМО. Считая эти уравнения уже решенными, выразить через р{- те же характеристики эффективности, что и в предыдущей задаче.

Решение. Граф состояний показан на рис. 11.41.

Уравнения для финальных вероятностей состояний:

(\ + Х2 ) Poo = Щ Рю + M>2Poi ; X,

M-1 2^2 X X,

44

X,

M-1 M-2 M-2 X, і" Й2 X, і Хі Зй,.

М-2

'X,

2ц2

X,

502

ІРС

Рис. 11.41

(\ + Х2 + р1)р10 = ХіРоо +

(\+\2 +2\1г)р20 = = \р10 + Зр^зо + р2р21;

(Х1 + Х2 = = \2Роо + М-2Рц +2 р2р02;

+Х2 + рх + р2) рп =\р01 + + Х2р10 + 2рхр21 + 2р2р12;

(Х1+р2 + 2р1)р21=Х1(р11 + (Xi + х2 + 2Р2)Р02 = :Х2Роі +М'іРі2+3М'2Роз; (Хі +М-1 +2р2)р12=Х1(р02+р03) + Х2р11;

(хі + Зр2) р03 = Х2р02; Роо + Рю + Р20 + Рзо + Рої + Рп + Р21 + Ро2 + Р12 + Роз = Ротк = Рзо ' Ротк = Рзо + Р21 Р\2 "I" Роз '

А1 = М1 ~ Рзо); А2 = М1 ~ (РЗО + Р21 + Pl2 + Роз)] ~Х1 (Роз + Pl2 + Роз); : А / м-1; ^2 X,

Л2 / р2; А;

~Ь k2 j -Р(2).

X,

-1 птк 1

\ +х2

Хх + Х2

11.42. Пример СМО с очередью и с абсолютным приоритетом. Имеется одноканальная СМО с двумя местами в очереди (га = 2). На вход СМО поступают два простейших потока заявок I и II с интенсивностями Х1?Х2. Времена обслуживания — показательные с параметрами рх, р2. Заявка I, прибывшая в СМО, «вытесняет» заявку II, если она обслуживается, и занимает место в очереди перед ней, если она стоит в очереди. «Вытесненная» заявка II покидает СМО необслуженной, если в очереди уже нет мест, и становится в очередь, если места есть. Нумеруя состояния СМО двумя индексами г, j соответственно числу заявок I и И, находящихся в СМО, построить размеченный граф состояний СМО и написать уравнения для финальных вероятностей состояний. Считая этим уравнения уже решенными, выразить через p{j (і + j < 3) следующие характеристики эффективности СМО:

і^тк (Роте ) ~~ вероятность того, что заявка 1(11) получит отказ немедленно после прибытия; Qi (Q2) ~~ вероятность того, что заявка I (II) будет обслужена;

(z2) — среднее число заявок I (II), связанных с СМО; г (f2)_— среднее число заявок I (II), находящихся в очереди; Чист (^сист) ~ среднее время пребывания в системе заявки I

(III;

(^оЧ2)) ~~ среднее время пребывания в очереди заявки I (II);

^сист ~~ среднее время пребывания в системе любой (произвольной) заявки;

tQ4 — среднее время пребывания в очереди любой заявки. Решение. Состояние СМО: s- — в СМО находится г заявок I и j заявок II (г + j < 3). Размеченный граф состояний показан на рис. 11.42.

Уравнения для финальных вероятностей состояний:

(Xi + Х2).Роо = M-lPlO +V>2Poi'f (Xi +х2 = \Роо +

+М-іР20 (Х1~^Х2 + M-1 ) Р20 =\Рю +М-іРзО +М-2^21''

М-1^30 = Xl(^20 + ^21)5 (Х1~^Х2 + ^2) Рої = Х2^00 + М-іРі + М-2^02 5

(Х1+ Х2 + М-1 + М-2)Рі1 = X2-Pl0 + Х1^01 + М4Р21 + М-2^125 (Х1 + Х2 + + М-2)Ро2 = \Poi + V>lPl2 + (Х1 + М«1 + M-2)Pl2 =Х1^02 +

+Х2^11 +ХіР03; (Х1 + М-2)РоЗ = Х2^02'

РОО + РіО + Р20 + РЗО + Рої + Рц + Р21 + Р02 + Р\2 + РОЪ = ^ ¦^отк = Рз0 j PQTK = Рз0 + Р21 P12 Роз ' Ql = ^ — ^отк = 1 ~~ Рзо • 500 * 520 'Ч 530 510 М-1

Р2 \

М-2 Х2

501 'Ч S21 511 Р2

\0 S02 w 512 Пк

Рис. 11.42 Чтобы найти <32, найдем сначала А2 — среднее число обслужен-ных заявок II в единицу времени:

А2 = Х2(1~ Ро(тк)- \(Р03 +Рі2 + Р2і)=Х2І1~(РзО +Р 21 + + Pl2 + Роз)]" Xl(P03 +Pl2 +Р21 )•

Разделив это выражение на Х2, находим среднюю долю обслу-живаемых заявок II (вероятность того, что заявка II будет обслу-жена): Q2 — А2 / Х2. Тогда

zx=l (р10 + рп + р12) + 2 (р20 +р21) + Зр30; z2 =1(р01 +рп + + Р21) + 2 (р02 + р12) + Зр03; гх = 1 (р20 + р21) + 2р30; г2 = 1 (рп +

+р21) + 2р12.

По формулам Литтла

7(1) _ -= /\ . 7(2) _ - /\ . 7(1) _ - /х . 7(2) _ - /х .

сист ~~ / 5 сист — ^2 / А2' L04 ~~ 'l / А1 > L04 ~ ' 2 / А2'

7 _ Х1 7(1) | Х2 Г(2) . Г ^ Х1 7(1) | Х2 Г(2)

''СИСТ х х ''СИСТ ~ х х 0СИСТ 5 U04 х х °ОЧ — х х ''ОЧ •

1 2 1 2 1 ' 2 1 ^2

Все характеристики, относящиеся к заявкам I, можно вычислить и не решая уравнений (11.42), а просто игнорируя наличие заявок И, рассматривая СМО с ограниченным числом мест в очереди (га = 2) и находя ее характеристики по формулам п. 3 (см. с. 379, 380).

11.43. ПростейшаяСМО без очереди и с «разогревом» каналов. На вход n-канальной СМО поступает простейший поток заявок с интенсивностью X. Время обслуживания — показательное с пара-метром р. Перед тем как начать обслуживание заявки, канал дол-жен подготовиться («разогреться»). Время «разогрева» Траз имеет показательное распределение с параметром у и не зависит от того, как давно канал прекратил работу. Заявка, заставшая канал сво-бодным, «занимает» его и ждет, пока он разогреется, после чего поступает на обслуживание. Заявка, заставшая все каналы заня-тыми (обслуживаемой или ожидающей заявкой), покидает СМО и остается необслуженной. Найти финальные вероятности СМО и характеристики ее эффективности: вероятность отказа Ротк, от-носительную пропускную способность Q, абсолютную пропуск-ную способность А, среднее число занятых каналов к.

Решение. Будем считать, что обслуживание заявки состоит из двух фаз: ожидания разогрева и самого обслуживания: ^обсл = траз + То6сл. Случайная величина Тобсл распределена по обобщенному закону Эрланга 2-го порядка (см. задачу 8.39) с параметрами р, у. Мы знаем, что формулы Эрланга (11.0.6) справедливы не только для показательного, но и для любого распределения времени обслуживания. Найдем величину fx = 1 / М[Т^ ]. Имеем

М[Тобсл] = М[Траз] + М[Тобсл]=1/1х + 1/у = (^ + у)/(И)

откуда fx = (|xv) / (ц + у). Вычислив р = X / jl и подставив это значение р в формулы Эрланга (11.0.6), получим: Ро =

Рк

1!

к\ п\

к\

Ро{1<к< п); El

п\

1-^Ро

п!

л = х<5 = х

Рп

Ро; п! Чтобы найти среднее число занятых каналов к, нужно разде-лить А на р: 1 - Е1 Ро = Р 1-?1 м- п\ t п! у Po-

ll.44. Простейшая одноканальная СМО с очередью и «разогревом» канала. На одноканальную СМО с неограниченной очередью поступает простейший поток заявок с интенсивностью X. Время обслуживания — показательное с параметром \і (р > X). Перед тем как приступить к обслуживанию заявки, свободный до того канал должен «разогреться». Время «разогрева» — показательное с параметром у и не зависит от того, как давно канал закончил работу. Если обслуживание начинается сразу же после окончания обслу-живания предыдущей заявки, «разогрева» не нужно. Составить граф состояний СМО и написать уравнения для финальных веро-ятностей состояний; выразить через эти вероятности характери-стики эффективности СМО: средние числа заявок в системе z ив очереди г, средние времена пребывания заявок в системе ?сист и в очереди tQ4.

Решение. Состояния СМО (рис. 11.44):

Sqq — канал свободен, не разогрет;

X 500 X % X X 02 603

Рис. 11.44

501 — пришла одна заявка и ждет, канал разогревается;

sn — канал разогрет, одна заявка обслуживается, очереди нет;

s02 — канал разогревается, в очереди две заявки; ...;

Sqi — канал разогревается, в очереди / заявок;

su — канал обслуживает одну заявку, I — 1 заявка стоит в очереди; ....

Уравнения для финальных вероятностей: Хр0о = М>11; (х + V) р01 = Хр00; (X + р) ри = vpoi + №12! (X + v)Po2 = Хр01; (Х + р)р12 =ур02 + хРп +М-Р13Ї —;

(х + у)Ро,/ = хРо,/-і5 (Х + р )ри =vp0}/ +Хр1М +рр1/+1;...;

00 оо

* = (Р<М + Pi,/); f = (РО,/ + Pu+i)•

г =0 1=1

По формуле Литтла

^сист — ^ / Х5 ^оч — ^ / Х11.45*. Имеется одноканальная СМО с очередью, ограниченной числом мест га = 2. На вход СМО поступает простейший поток заявок с интенсивностью X. Время обслуживания распределено по обобщенному закону Эрланга с параметрами рх, р2 (см. задачу 8.31). Найти вероятности состояний СМО:

Sq — в СМО нет заявок;

s1 — в СМО одна заявка (очереди нет);

s2 — в СМО две заявки (одна обслуживается, одна в очереди);

S3 — в СМО три заявки (одна обслуживается, две в очереди).

1)_ Найти характеристики эффективности СМО: Ротк, Q, А, z, г, ?сист, tOH. Вычислить их для значений X = 2, Pj = 6; р2 = 12. 2) Сравнить их с теми, которые получились бы для простейшей СМО с таким же значением X и значением р, равным 1 / ?обсл, где ^обсл ~~ среднее время обслуживания заявки в данной СМО.

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

Представим обслуживание состоящим из двух фаз (I и И), продолжающихся соответственно время Тх и Т2; полное время обслуживания Тобад = Тх + Т2, где Тх имеет показательное распределение с параметром рх; Т2 — показательное распределение с параметром р2. Тогда Тобсл будет иметь обобщенное распределение Эрланга с параметрами рх и р2 (см. задачу 8.39).

Введем следующие состояния СМО: sn X о, , M-1 с „ 50 — СМО свободна;

5И — в СМО одна заявка, обслуживание в первой фазе; S2l M-1 522 512 — в СМО одна заявка, обслужива-ние во второй фазе;

sfb 531 532 521 — в СМО две заявки (одна обслуживается и одна в очереди); обслуживание в первой фазе;

s22 — в СМО две заявки, обслуживание во второй фазе;

Рис. 11.45

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

— в СМО три заявки, обслуживание во второй фазе.

Дальнейших состояний нет, так как (по условию га = 2) больше трех заявок в СМО быть не может. Размеченный граф состояний СМО показан на рис. 11.45. При таком подходе состояние расчленяем на два: sn и s12 (или, короче, sx = su + s12); аналогично 52 = s21 + 522, 53 = 531 + s32. Уравнения для финальных вероятностей, соответствующих графу рис. 11.45, будут:

ХРо = М-2^12 ; (Х + Ml ) Рп = ХРо + М-2^22 ; (Х + М<2 ) Р\2 = V4P11 5 (Х + Рх) р21 =Р2Рз2 + XPll5 (Х + М-2 ) Р22 =^1^21 + XPl2 5 М-ІРзі = Х^2І5 М»2^32 =^1^31 + Х^22 ' нормировочное условие Pq + рп + р12 + р21 + р22 + р31 + р32 = 1.

Решая эти уравнения, получаем: (Х + Р2)Х х , Х3(Х + Р, +р2) + Х2р2(Х + р2)

1 +

+

Ро

2 2 рхр2

рхр2

¦ + — + р2

,4

| Х2(Х + Р, +р2) | Х4(Х + рг + ^2) + хУ2(Х + р2) |

2 3

М-хМ-2 -1

3 2

M-iM-2

Х^Х + ^+щ) | Х4(Х + цх +ц2) + ХУ2(Х + ц2)

M-iM-l (Х+!Х2) X ^ X X3(X+(i1+(i2)+XV2(X+(i2)_> .

Рп = Ро! Рі2 = Ро> Ргі = г~2 р0,

M-lM-2 М-ГМ-1

_Х2(м.х +1^2 + х) _ Х4(Х + цх +Ц2) + ХУ2(Х + Ц2)

Р22 — 2 Рзі ~ ~¦> Ро>

3 2

MqM-2 р0. (11.45.1)

Р32 =

X4(X+H1 + H2) + \V2(X+^2)+ Х3(Х+^+Щ)

МчМ'г M-iM-a Далее находим финальные вероятности состояний sv s2, s3:

Pi =Рц + P12 +

pxp2

X2

p2 = p21 + p22 =—— [(X + p1)(X + p1 + p2) + p2(X + p2)] Poi pxp2

з

X'

Рз =Рзі +Рз2 + хМ-і + + М-2) +

рхр2

+ р2(рх + р2)(Х + р2)]р0, (11.45.2)

где Ро определяется первой из формул (11.45.1).

Характеристики эффективности СМО могут быть найдены через вероятности р0, pv р2, Рз по формулам:

Ротк = Р3; Q = 1 - Рз5 4 = X (1 - Рз); z = 1рх + 2р2 + Зр3;

г = 1р2+2р3; ^сист = ^ / X; *оч = г / X. (11.45.3)

Подставляя в формулы (11.45.1) численные данные X = 2, рх = 6, р2 = 12, получаем: р0 = 0,540; рп = 0,182; р12 = 0,090; р21 = 0,087; р22 = 0,050; р31 = 0,029; р32 = 0,022. Отсюда, возвращаясь к исходной (немарковской) СМО, имеем: р0 = 0,540; рх = 0,272; р2 = 0,137; Рз = 0,051.

Далее, по формулам (11.45.3): Ротк = 0,051; Q = 0,949; А = 1,89; z = 0,705; г = 0,243; tCUCT = 0,352; їоч - 0,122.

2) Подсчитаем те же характеристики для простейшей СМО с теми же Х = 2, р = (1 / pj +1 / р2 )~1 = 4 По формулам (11.0.12)—(11.0.15)

имеем:

р = 0,5; р0 « 0,533; k = 1 - р0 « 0,467; рг = рр0 « 0,267; р2 - р2р0 « 0,133; рз = р3р0 « 0,067; РОТК = р3 « 0,067;

Q = 1 - Рз « 0,933; А « 1,866; J « 0,733; г « 0,267; *сист = 0,367;

їоч «0,133.

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

11.46*. Имеется одноканальная СМО с двумя местами в очереди. На ее вход поступает пальмовский поток заявок с интервалом Г, распределенным по обобщенному закону Эрланга с параметрами

Х1,Х2; время обслуживания — показательное с параметром р. 1) Применяя метод фаз, написать уравнения для финальных вероятностей состояний р0, pv р2, р3. Выразить через эти вероятности характеристики СМО: Ротк, Q, A,z, г, tCMCT,t04. 2) Вычислить финальные вероятности и характеристики эффективности для следующих исходных данных: \г = 3, \2 = 6; р = 4и сравнить их с теми, которые соответствуют простейшей СМО с параметрами X = (1 / \1 + 1 / \2 )-1 = 2, р = 4,

рассмотренной в задаче 11.45.

Решение. 1) Если рассматривать, как мы делаем обычно, состояния СМО, нумеруя их соответственно числу заявок в СМО: s0, sv s2, s3, то система не будет марковской. Чтобы ее марко- визировать, разделим на две фазы (I и II) не время обслуживания, а интервал Г между заявками: Т — Тх + Т2, где случайные величины Тг и Т2 имеют показательное распределение с параметрами \ и Х2 соответственно.

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

— заявок в СМО нет; интервал между заявками в первой фазе;

— заявок в СМО нет; интервал между заявками во второй фазе;

sn — в СМО одна заявка (обслуживается); интервал между заявками в первой фазе;

si2 — в СМО одна заявка (обслуживается); интервал между заявками во второй фазе;

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

s22 — в СМО две заявки (одна обслуживается, другая в очереди), интервал между заявками во второй фазе;

531 — в СМО три заявки (одна обслуживается, две в очереди); интервал между заявками в первой фазе;

s32 — в СМО три заявки (одна обслуживается, две в очереди), интервал между заявками во второй фазе.

Граф состояний СМО дан на рис. 11.46.

Уравнения для финальных вероятностей:

\Poi =м*Рц; х2Ро2 =\Poi (хі +ИОРЦ =х2РО2

(Х2 + р) р12 = х:рп + рр22; + р) Р21 = х2р12 + рр31;

(х2 +р) р22 = \р21 +рр32; +М«) Ргі = Х2Р22 + х2Рз25 (Х2 +р) р32 =\pzl.

Нормировочное условие р01 + Р02 + Рп + ри + Р21 + Р2 2 + +Рзі + Рз2 = L

Эти уравнения удобнее всего решать, выражая вероятности р{- через последнюю, р32. Выражения для вероятностей р{- (г = 0, 1,2, 3; j = 1,2) имеют вид:

р = и | ^ + , И» (і^ + Хі + х2) , Iх 2 +Х1р + 2Х2р + Х 2) [ Х1 Х1Х2 Х1Х2 [ р2(р2 +2Х.Р + 2Х2Р+Х2, +Х,Х2 + Х2) [ Х2Х2

+ Р2(Р + 2ХХР2 +ЗХ2Р2 + Х21Р + 2Х1Х2Р + ЗХ2Р + Х32)

Х3Х2

Р3(Р3+ЗХ1Р2+ЗХ2Р2+ЗХ2Р+4Х1Х2Р+ЗХ2Р+Х31+Х2Х2+Х1Х2+Х32) Pl2 - 2 2 Р32Ї

р2(р2 +2X1p + 2X2p + X2 + ХгХ2 + X2) Х2Х2 _ р^р* +2Ххр2 +ЗХ2Р + Х^р + 2ХхХ2р + ЗХ2р + Х32) " х^х2 Рз2;

з

Ро2 = 75ТГ^3 + ЗХУ + зх2^2 + Х1^ + 4ХхХ2р + Х 2 2

_ р3(р3 + 2Ххр +ЗХ2р + Х21р + 2Х1Х2р + ЗХ22р + Х32)

Х1Х2

+ ЗХ2Р + X3 + Х2Х2 + ХхХ2 + Х32) р32; _/(р3 .

Рог ~ і * Г4Т2 ~ ~ —Рз2Переходя обратно к исходной (немарковской) СМО, получаем: Ро = Ро\ + Ро25 PI = Рп + Pl2> Р2 = Р21 + Р22) Рз = Рз\ + Рз2'

Далее, Ротк =р3; Q==i-p3; A = Q\;z = lp{ +2р2 + Зр3; г =

= +2Рз^сист =Z / \]t04 = г /\.

Финальные вероятности состояний: р01 «0,308; р02 «0,208; рп « « 0,231; р12 « 0,082; р21 « 0,091; р22 « 0,032; р31 « 0,037; р32 «0,011.

Для исходной (немарковской) СМО р0 «0,616; р2 «0,313; р2 « 0,123; Ротк « 0,048; Q « 0,952; А « 1,904; J « 0,703; г « 0,219;

fCMCT « 0,352; їоч «0,110.

Из сравнения этих данных с результатами предыдущей задачи 11.45 делаем вывод, что СМО задачи 11.46 имеет незначительное преимущество перед СМО задачи 11.45 по всем характеристикам эффективности и несколько большее преимущество перед про-стейшей СМО с теми же X, р.

11.47. Простейшая СМО без очереди с неограниченной взаимопомощью между каналами. На п-канальную СМО с отказами поступает простейший поток заявок с интенсивностью X. Каналы работают со «взаимопомощью» — если в момент обслуживания очередной за-явки в СМО есть свободные каналы, то все они подключаются к обслуживанию данной заявки. Интенсивность простейшего потока обслуживаний заявки есть некоторая функция р = ф (к) числа к каналов, одновременно обслуживающих ее. Построить граф состояний СМО и найти финальные вероятности состояний. Выразить через них характеристики эффективности СМО: вероятность отказа Ротк, относительную пропускную способность Q, среднее число занятых каналов к. Подсчитать эти характеристики при п = 4, X = 1, р (к) — k[i, р = 0,5 и сравнить их с теми же характеристиками в случае отсутствия взаимопомощи между каналами.

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

СМО превращается в одноканальную СМО с от- ^

казами; ее состояния: s0 — ни один канал не за- | s0 | "*j sn | нят; sn — все п каналов заняты. Размеченный '—'%(n) '—' граф состояний показан на рис. 11.47. Пользуясь этим графом, получаем финальные вероятности Рис. 11.47 состояний: -1

1+ х

Ро =

ф(п)

ф(п) + X' X X

Рг = —ттРо =

ф(п) ф(п) + Х

При ф (п) = п(л имеем р0 = (п|х) / (пц + X); рх = X / (пц + X). При п = 4, X = 1, |х = 0,5 имеем р0 =2/3; Р0ТК = рх =1/3; Pj =1/3;Q = 1 — Pj = 2/3; .4 = XQ = 2 / 3 ss 0,667.

Среднее число занятых каналов к = 4 • 1/3 + 0 • 2/3 = = 4/3« 1,333. Этот же результат получим, разделив А на р: к = (2/3) / 0,5 = 4/3.

Для сравнения рассчитаем характеристики эффективности че- тырехканальной СМО без взаимопомощи между каналами [см. формулы Эрланга (11.0.6) и (11.0.7)]; при р = X / р = 2

р0={1 + р + р2 /2 + р3 /6 + р4/24}" =1/7;

Ротк — Ра — (2 / 3)(1 / 7) = 2 / 21;

А = X (1 - 2 / 21) « 0,905; Q = A\k = A/ р ^ 1,81.

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

11.48. Простейшая СМО без очереди с равномерной взаимопомощью между каналами. Имеется простейшая n-канальная СМО с отказами, на которую поступает поток заявок с интенсивностью X. Между каналами осуществляется взаимопомощь, но не объединением всех каналов в один, как в предыдущем примере, а так называемая «равномерная» организованная следующим образом. Если заявка приходит в момент, когда все п каналов свободны, то все каналы принимаются за ее обслуживание; если в момент обслуживания заявки приходит еще одна, часть каналов переключается на ее обслуживание; если, пока обслуживаются эти две заявки, приходит еще заявка, часть каналов переключается на ее обслуживание и т.д., пока не окажутся занятыми все п каналов; если они все заняты, вновь пришедшая заявка получает отказ. Функция ip (k) = k\i, т.е. обслуживание к каналами в к раз быстрее обслуживания одним каналом.

Составить размеченный граф состояний СМО, определить финальное вероятности состояний и характеристики эффективности: Q, А, к. Подсчитать их при п = 4, X = 1, р = 0,5, т.е. в условиях задачи 11.47, и сравнить с тем, что получается без взаимопомощи. ^

Решение. Состояния СМО нумеруются по числу заявок, находящихся в ней. Граф состояний (11.48) — тот же, что для простейшей одноканальной СМО с производительностью р* = пр и ограниченной очередью, имеющей п — 1 мест. Для определения характеристик можно воспользоваться формулами (11.0.16) — (11.0.19); полагая р = р* = X / |i* = X / (п р) = 0,5; имеем при га = 3:

X ^ i X X __ X X

• • • • • • rQ

n\L п(х np, П\і. n\i.

Рис. 11.48

1 — п * 0 ^

Ро = Д5 = —^«0,514; Р4 =(Р*)4Р0 «0,032;

1 - (р*) 1 - 0,5

А = X (1 - р4) « 0,968; Q = 1 - р4 « 0,968; к = А / р* « 1,936.

В условиях задачи 11.47 при отсутствии взаимопомощи Л «0,905; <2 ~ 0,905; А; « 1,81, т.е. взаимопомощь несколько увеличивает пропускную способность СМО. В данном случае это увеличение незначительно, так как СМО сравнительно мало нагружена.

Для простейшей трехканальной СМО с отказами и параметрами: X = 4 заявки/мин, среднее время обслуживания заявки одним каналом 1 / р = 0,5 мин, интенсивность обслуживания заявки к каналами = кр определить характеристики эффективности СМО Qy А, к для трех вариантов использования СМО: 1) при отсутствии взаимопомощи; 2) при неограниченной взаимопомощи; 3) при равномерной взаимопомощи между каналами. _

Ответ. 1)Q«0,79; Л «3,16; А; «1,58; 2) Q=0,6; Л=2,4; А; = 1,2; 3) Q « 0,887; А « 3,51; к « 1,76.

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

Построить граф состояний, найти финальные вероятности состояний и характеристики эффективности: k, z, r,fCHCT , t04.

Решение. Граф состояний этой СМО совпадает с графом состояний простейшей одноканальной СМО с неограниченной очередью, с интенсивностью потока заявок X и потока обслуживаний ТІ р (см. 2, с. 366, 367). Полагая в формулах (11.0.12)—(11.0.15) Р= X = - / \п р), получаем р0 = 1 - Х; Рк = X* (1 ~ х) (* = 1, 2^...);

* = х/(1-х);^=х7(1-х);*сист = * -,tm =^7Г—їMi-х) х (і — х)

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

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

Нумеруя состояния СМО по числу заявок, находящихся в ней, составить размеченный граф состояний СМО и найти финальные вероятности состояний. Найти характеристики эффективности СМО: Ротк, Q, A, z, г, tCiiCT, tQ4. Решение. Состояния СМО: 50 — система свободна;

вг — одна заявка обслуживается всеми п каналами; ...; sk— к заявок обслуживаются всеми п каналами (1 < к < п); ...; sn — п заявок обслуживаются п каналами, одна заявка стоит в очереди; ...;

sn+m ~~ 71 заявок обслуживаются п каналами, т заявок стоят в очереди.

_____ X | [ X _____ X X [ < X [ < X X _

n+m І

П\1 п\ъ n\l n\l ^ n\l n\L п\ъ

Рис. 11.51

Граф состояний СМО дан на рис. 11.51. Этот граф состояний СМО совпадает с графом состояний простейшей одноканальной СМО с ограниченным числом т мест в очереди, интенсивностью потока заявок X и интенсивностью потока обслуживаний п р (см. п. 3, с. 367). Подставляя в формулы (11.0.16)—(11.0.20) X = X / (п р) вместо р и п + т вместо т, получаем:

Ро = (1 - X) / (1 - Xn+m+2); Vk = ХкРо (к = 1.... ;nV т);

PQTK ~ Рп+т ? Q — ^ ~~ Pn+m'i А \Q.

(i-xn+m+2)(i-x)'

^сист — z / \ — Г /

11.52. На вход автоматизированного банка данных (АБД) подается в среднем X = 335 статей/ч. Первая операция по обработке входного потока первичных информационных документов (ПИД) состоит в отборе тех статей, которые должны вводиться в АБД. В отборе участвует 6 чел. (отборщиков); средняя производитель-ность каждого отборщика р = 60 статей/ч. Известно, что в среднем из входного потока отбирается для ввода в АБД 61,3 % ПИД. Все потоки событий — простейшие. Рассматривая систему отбора ПИД для ввода в АБД как шестиканальную (п = 6) СМО с неогра- ниченной_очередью, определить ее характеристики эффективности: A, Qyk, z, г, ?сист , t04.

Решение. Так как очередь неограниченна, Q = 1; А = X. Интенсивность потока ПИД, отобранных для ввода в АБД, Х0 = \р, где р « 0,613, т.е. Х0 = 335 • 0,613 « 205статей/ч.

Интенсивность потока ненужных для ввода в АБД ПИД будет Хн = X (1 - р) « 130 статей/ч. _

Среднее число человек, занятых отбором ПИД, k = \/\x = = р = 5,58 и не зависит от числа каналов (отборщиков). Стационарный режим в СМО существует, если выполнено условие X = X / (np) < 1; в нашем случае оно выполнено (х = 0,93).

Вероятность того, что в СМО будут заняты работой все п отборщиков [см. формулу (11.0.22)], определяем по формуле: Д(п,р) + Р(п,р). Х

рп =Р (п,р)/

X]

Пользуясь таблицами, данными в приложениях 1, 2, получаем:

=0,1584/

0,93 ^

і 0,0569.

0,7603 + 0,1584

0,07 J

Среднее число ПИД в очереди [см. (11.0.23)] г = = Рп X / (1 _ х)2 ~ 10,8. Среднее время пребывания ПИД в очереди^ = г / X « 1,87 мин. Среднее число ПИД, находящихся в системе (в очереди и на обработке), z = г + р « 15,38. Среднее время пребывания ПИД в системе ?сист = t04 + 1 / р « 2,87 мин.

11.53. На вход СМО (рис. 11.53) подается простейший поток заявок с интенсивностью X. Обслуживание состоит из двух последовательных фаз, выполняемых в СМОх и СМ02. В СМОх проводится обслуживание заявки, а в СМ02 контролируется качество проведенного в СМОг обслуживания. Если в СМ02 не обнаружено недостатков в обслуживании, то заявка считается обслуженной в СМО; если в СМ02 обнаружены недостатки в обслуживании, то заявка возвращается на повторное обслуживание в CMOj (см. рис. 11.53). Вероятность того, что заявка, обработанная в СМ01( будет в результате контроля в СМ02 возвращена на повторное обслуживание в СМ02, равна 1 — р и не зависит от того, сколько раз она была обработана в CMOj.

СМО СМО, nv pj Xqi Х2 смо2

щ, р2 Х()2 ^""Ч

t Поток заявок на повторное обслуживание в СМО,

\0=Х

X !

x02(i-р)

Рис. 11.53

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

Решение. Обозначим Х2 интенсивность потока заявок, подаваемых на вход СМО:. Очевидно, что Х2 > X, так как на вход СМО: будет поступать поток заявок, направляемых на обслуживание в СМО: впервые (интенсивность потока X), плюс поток заявок, направляемых на повторное обслуживание (см. рис. 11.53). Если стационарный режим существует, то интенсивность потока обслуженных в СМО: заявок Х01 будет равна интенсивности Хг Поток обслуженных в СМО: заявок поступает в СМ02, следовательно, на вход СМ02 поступает поток заявок с интенсивностью Х2 = = = Х01. В силу наличия стационарного режима в СМ02 интенсивность потока заявок на выходе СМ02 (Х02) будет также равна Х2. Таким образом,

х1=х01=х2 = х02. (11.53.1)

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

Интенсивность потока обслуженных в СМО заявок Х0 будет равна интенсивности потока заявок на выходе СМ02 (Х02), умноженной на вероятность р того, что заявка не будет возвращена в СМОх на повторное обслуживание:

Х02р = Х0 = Х, (11.53.2)

откуда

\02 = \/ р. (11.53.3)

Таким образом [см. формулы (11.53.1)—(11.53.3)],

\г = \2 = \/р. (11.53.4)

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

Xi = Хі = (11.53.5)

Х2 =Х2 / (^2^2) = х / ) < (11.53.6)

Они вытекают из того, что как СМОр так и СМ02 представляют собой пх- и ^-канальные системы с интенсивностью обслуживания в каналах [хг и р2 соответственно, с неограниченными очередями (см. п. 4, с. 368).

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

Решение. Среднее время однократного пребывания заявки в СМОх tx (см. рис. 11.53) будет определяться из условия, что на вход этой системы поступает простейший поток заявок с интенсивностью \ = X / р, число каналов обслуживания nv интенсивность обслуживания \хг, число мест в очереди не ограничено. Для этих условий в соответствии с (11.0.21)—(11.0.25) имеем

=(pi +fi)x71 = —+ РГ41 ^ » (И-54Л)

Hi nl .nJCl-Xi) \

где

X рг X

Pi =—; Xi =—; xi = —;

-1

2 Л п 1 71 і +1

1 + PI+Pl+...+ PI1 + .IV

PV>i ni Р

pi

1! 2! пг1 пг -пг\ 1 - Xi

Аналогично рассчитываем величину t2 — среднее время одно-кратного пребывания заявки в СМ02 для условий Х2 = X /р; п2; р2:

Р 01 = Р 02

п,+1

(11.54.2)

Ч =(р2 +r2)X"1 = — +

И-2 "2 -n2!(l - Х2)2Х2 где X

р\Х2

р2 • X , л2 —

р2 =

х2

Tl0 п0+1

1+ Р2 , Р2

Pot _ + -V+JV 1_

1! 2! п2\ п2-п2\ 1-Х: Следовательно, среднее время однократной обработки заявки CMOj и СМ02 будет (11.54.3)

' 12

= *1 + V Из условия задачи 11.53 следует, что случайная величина X — число циклов обработки одной заявки в СМС^ и СМ02 будет иметь геометрическое распределение, начинающееся с единицы, с параметром р: 1 2 3 к V pq pq2 pq (11.54.4)

Обозначим Tv Т2, Th ... — время первого, второго, ..., к-то цикла обработки заявки в СМОг и СМ02. По условиям задачи случайные величины Tv ..., Th ... независимы, одинаково распределены и имеют математическое ожидание т12.

Время пребывания заявки в СМО ^с учетом возможных возвратов заявки на повторное обслуживание' можно записать в ви- х

де Т = Tk J т-е- оно представляет собой сумму случайного числа

k=i

(11.54.5)

t = М[Г] = MfTj. ] М[Х] = т12 / р.

Для рассмотренной СМО формула Литтла также справедлива, поэтому среднее число заявок, находящихся в СМО, будет опре-деляться по формуле

z ~t\ z = zl + z2 = рх + p2 + rx + r2. (11.54.6)

случайных слагаемых, где число слагаемых X не зависит от случайных величин Tv Т2, Г3, ... В соответствии с решением задачи 7.64 находим математическое ожидание величины Т\

11.55. Условия задачи (11.53) изменены так, что в СМОх и СМ02 проводится только первичное обслуживание и его контроль; если заявка не прошла контроль в СМ02, то она направляется на повторное обслуживание в СМОэ и повторный контроль в СМ04 (рис. 11.55). СМ03 и СМ04 представляют собой п3- и п4-ка- нальные системы с показательным распределением времени обслуживания заявок в каналах с параметрами р3 и р4 соответственно. Вероятность того, что заявка, обработанная в СМ03, будет в результате контроля в СМ04 возвращена на повторное обслуживание в СМ03, равна 1 — -к.

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

Решение. В рассматриваемой СМО в стационарном режиме будет иметь место очевидное равенство (см. рис. 11.55)

Х = Х1=Х01=Х2=Х02. (11.55.1)

Следовательно, интенсивность потока заявок, которые прошли однократное обслуживание и контроль в CMOj и СМ02, будет Хр. Поток заявок, не прошедших контроль в СМ02 и направляемых на повторное обслуживание в СМ03 и СМ04, будет иметь интенсивность X (1 — р). Работа системы повторного обслуживания СМ03 и СМ04 (от точки 1 до точки 2 на рис. 11.55) принципиально ничем не отличается от работы системы, приведенной в задаче 11.53.

СМО

Рис. 11.55

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

^ <1; х>=^<1;

ъп3\13

п

Л

n2\i2

X (1 - р)

< 1.

х4

(11.55.2) і"і4ц4

Кроме того, будут иметь место равенства (см. рис. 11.55)

хз - Х03 = Х4 = Х04 = X (1 - р)*-1. (11.55.3)

11.56. Для условий предыдущей задачи определить среднее время t пребывания заявки в СМО и среднее число заявок z, нахо-дящихся в СМО.

Решение. Среднее время пребывания заявки в СМОх будет определяться из условия, что на вход этой системы поступает простейший поток заявок с интенсивностью Хх = X [см. рис. 11.55 и формулу (11.55.1)], число каналов обслуживания nv интенсив-ность обслуживания в канале число мест в очереди не ограни-чено. Для этих условий в соответствии с (11.0.21)—(11.0.25)

<,=(Рі+г1)>ГІ=- + Р"Рт , (П-56.1)

где

X Рх

Рі=—; Хі=—; Pi пх п,+1

і 2!

Рої

1!

Л П 1 Л П]

П1 ! пх •П1 !1 - Xi Аналогично рассчитываем величину t2 для СМ02 при Х2 = X, n2, \х2: Р 02

п,+1

(11.56.2)

t2=(p2+r2)\ 1 = —+

р2 п2 -п2!(1- х2) х где Р 2

х2

Р 2 = Среднее время пребывания заявки в СМОг и СМ02 равно ¦-t, +t2.

1 12

(11.56.3) Среднее время ?3 однократного пребывания заявки в СМОэ будет определяться из следующих условий: на вход этой системы поступает простейший поток заявок с интенсивностью \3 = X (і — р) / ^ [см. рис . 11.55 и формулу (11.55.3)], число каналов обслуживания п3, интенсивность обслуживания в канале р3, число мест в очереди не ограничено. Тогда в соответствии с (11.0.21)—(11.0.25) *з=(Рз+гз)Хз ^і/н-з+Рз7*3 Роз /К где

"зК1-Хз)2\]. (11-56.4) Рз . ^М-з п -і

п,+1

1

Роз

Рз Р

п3!

Щ • П3 ! 1 - Хз

1! 2! Аналогично рассчитываем величину f4 для СМ04 при Х4 = X (1 — р)/и,п4>и,4:

i4=(p4+r4)\- =l/^4+p4^+1po4 /[«4 «4 ! (1-Х4)2Х4], (11.56.5) где Х4 X (1 — р)

Л. 4 5

Пл

¦к

М-з

р4 Мч Следовательно, среднее время однократной обработки заявки в СМ03 и СМ04 будет

f^=is+f4. (11.56.6) В соответствии с формулой (11.54.6) математическое ожидание времени пребывания заявки в СМ03 и СМ04 (см. рис. 11.55) с учетом возможной повторной обработки равно

тох =т{1} /-к. (11.56.7)

34

1 34

Для определения среднего времени пребывания заявки в СМО рассмотрим две гипотезы: 1) Н1 — заявка подвергалась только однократной обработке; Р(Н1) = р\ 2) Н2 — заявка подвергалась многократной обработке; Р(Н2) = 1 - р.

При гипотезе Нх математическое ожидание времени пребывания заявки в СМО будет определяться по формуле (11.56.3), при гипотезе Н2 — по формулам (11.56.7) и (11.56.3). Полное математическое ожидание времени пребывания заявки в СМО будет

ї = тп+т$(1-р)/'К- (11-56.8)

Среднее число заявок, находящихся в СМО, определяется по формуле Литтла:

z=t\. (11.56.9)

11.57. Рассмотрим условия задачи 11.53 применительно к многократной обработке информации в двух фазах. С целью контроля правильности перфорации она осуществляется дважды: на перфораторе и на «контрольнике», с помощью которого обнаруживают ошибку. Перфораторщица осуществляет в среднем одну ошибку на 1000 знаков (букв, цифр и т.п.). Каждая перфокарта содержит в среднем 80 знаков. Если во время контроля на перфокарте обнаружена хотя бы одна ошибка, то эта перфокарта возвращается снова на перфорацию. За год необходимо обработать 50 000 документов, каждый из которых содержит в среднем 400 знаков.

Найти минимально необходимое число перфораторщиц, работающих на перфораторах и контрольниках, если одна перфораторщица в год перфорирует 4,2 • 106 знаков, и определить характеристики такой системы.

Р е ш е н и е. Из условий задачи следует, что в год необходимо в среднем отперфорировать и проконтролировать 50 000 • 400 / 80 = = 250 000 перфокарт. Следовательно, X = 250 000 перфокарт/год = 125 перфокарт/ч = 2,083 перфокарт/мин. Производительность перфораторщицы, работающей за перфоратором или на «контрольнике», составляет р2 = р2 = 4,2 • 106 / 80 = 52 500 перфокарт/год = 26,25 перфокарт/ч = 0,438 перфокарт/мин. Вероятность необнаружения ни одной ошибки на перфокарте равна р = 0,99980 « 0,9. При этом мы пренебрегаем вероятностью того, что и перфораторщица и контролер ошибутся одинаково в одном и том же знаке. Эта вероятность намного меньше, чем (0,001)2 = 10~6, так как клавиатура перфоратора и «контрольника»

имеет около 50 различных знаков. Если считать, что ошибочно может быть нажат на клавиатуре любой знак из 50, то получим вероятность одинаковой ошибки, равную 10~6 / 2500. Если считать, что ошибочно может быть нажат на клавиатуре только ближай- ший к нужному знає (а их от 5 до 8), то эта вероятность будет 1(П6 / 25 - 1(Г6 / 64.

Условие стационарной работы перфораторщиц будет [см. формулы (11.53.5), (11.53.6)]

* / (niMiP) = Хі < і; х / (я2м-2р) = х2 < і»

откуда nl > X / (рхр) = 250 ООО / (52 500 • 0,9) = 5,29; гг2 > 5,29.

Таким образом, нужно иметь шесть перфораторщиц и шесть контролеров.

Характеристики работы перфораторщиц: Хвх1 = X / р = = 250 000 :0,9 = 278 000 перфокарт/год; п1 = 6; щ = 52 500 перфо-карт/год; Xi = X /(пхрр) = 0,882; рх = X / (ррх) = 5,29.

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

Рп = = Ш =0,107.

ni v 0882

R(nltPl) + P(nl9Pl)TJ^- 0,282 + 0,152-^— 1-Xi 1-0,882

Среднее число перфокарт, ожидающих перфорации, гг = = РпХг/( 1-Х!)2=6,78.

Среднее время ожидания перфокарты в очереди: tml = = rlP\~l = 2,92мин;tx = t04l + 1 / рх = 5,21 мин.

Общее число перфокарт в первой фазе zx = гг + кг = = гг + Pl = 12,07.

Так как характеристики второй фазы (контроля) такие же, как и первой, то можно выписать общие характеристики работы системы с учетом возврата перфокарт на новую обработку. Общее среднее число перфокарт, находящихся в системе, z = 2zx = 24,14; из них в очереди будет г = 2rj = 13,56. Общее среднее время обработки одной перфокарты с учетом ее возможного возврата на по-вторную обработку равно t = т12 / р = (^ + 12) / p = 2tx / р = = 11,57 мин.

<< | >>
Источник: Е. С. ВЕНТЦЕЛЬ, Л. А. ОВЧАРОВ. ЗАДАЧИ И УПРАЖНЕНИЯ ПО ТЕОРИИ ВЕРОЯТНОСТЕЙ. 2003

Еще по теме ГЛАВА 11 теория массового обслуживания:

  1. 25. ЦИКЛЫ ОБСЛУЖИВАНИЯ ПОТРЕБИТЕЛЕЙ. СЕРТИФИКАЦИЯ СИСТЕМ ОБСЛУЖИВАНИЯ
  2. ГЛАВА 17. РАСЧЕТНО-КАССОВОЕ ОБСЛУЖИВАНИЕ КЛИЕНТОВ
  3. Глава 10. ИНФОРМАЦИОННО-АНАЛИТИЧЕСКАЯ РАБОТА: ОБРАБОТКА МАТЕРИАЛОВ СРЕДСТВ МАССОВОЙ ИНФОРМАЦИИ
  4. ГЛАВА 1. ЭКОНОМИЧЕСКАЯ ТЕОРИЯ ГОСУДАРСТВА
  5. Глава 19. Экономическая политика: теория и практика
  6. Глава 13. ТЕОРИЯ ИГР И СТРАТЕГИЯКОНКУРЕНЦИИ
  7. Глава 21. ТЕОРИЯ СПРОСА И ПОЛЕЗНОСТИ
  8. ГЛАВА 5. Теория мирохозяйственных связей. Основные концепции международной торговли
  9. Глава 2. ЭКОНОМИЧЕСКАЯ ТЕОРИЯ КАК НАУКА
  10. Глава 7. ЭКОНОМИЧЕСКАЯ ТЕОРИЯ ТОВАРА И ДЕНЕГ
  11. Глава 26. ТЕОРИЯ ПРОИЗВОДСТВА И ПРЕДЕЛЬНЫХ ПРОДУКТОВ
  12. Глава 32. МЕЖДУНАРОДНАЯ ТОРГОВЛЯ И ТЕОРИЯ СРАВНИТЕЛЬНОГО ПРЕИМУЩЕСТВА