Е.С. Вентцель, Л.А. Овчаров - Задачи и упражнения по теории вероятностей (1115276), страница 49
Текст из файла (страница 49)
Предполагается, что потокисключений термина в динамическом словаре — пуассоновский синтенсивностью |i (t), одинаковой для всех терминов словаря.В этом случае интенсивности потоков «размножения» и «гибели» будут иметь вид7\k(t) = \(t)NМ*) = и(*)*.n{t))(Ю.38.1)а уравнения (10.0.24) и (10.0.25) примут вид (зависимости от времени tфункций mx(t), Dx(t),n(t),\(t),[i(t),pk(t) для краткости опущены):dmx J it = X - тх(\/ п 4- |л);dDx J dt = X - тх (X / п - [i) - 2 (X / п + р.) Dx.
(10.38.2)Если величины X, n, \i постоянны (не зависят от времени), топри t —• оо существует стационарный режим работы, для которогоdmx J dt = dDx / dt = 0, откуда1-lm„ —n l + ^ |;DT=mi 1 +хГГЛАВА ИТЕОРИЯ МАССОВОГО ОБСЛУЖИВАНИЯСистемой массового обслуживания (СМО) называется любая система,предназначенная для обслуживания каких-либо заявок (требований), поступающих на нее в случайные моменты времени. Примеры СМО: телефонная станция; бюро ремонта; билетная касса; парикмахерская;ЭВМ. Теория массового обслуживания изучает случайные процессы,протекающие в системах массового обслуживания.Любое устройство, непосредственно занимающееся обслуживаниемзаявок, называется каналом обслуживания (или «прибором»).
СМО бывают как одно-, так и многоканальными. Пример одноканальной СМО —билетная касса с одним кассиром; пример многоканальной — та же касса снесколькими кассирами.Различают СМО с отказами и СМО с очередью. В СМО с отказами заявка, пришедшая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем в процессе ее работы не участвует. В СМО сочередью заявка, пришедшая в момент занятости всех каналов, не покидает СМО, а становится в очередь и ждет, пока не освободится какой-нибудь канал.
Число мест в очереди т может быть как ограниченным, так инеограниченным. При т = О СМО с очередью превращается в СМО с отказами. Очередь может иметь ограничения не только по количеству стоящих в ней заявок (длине очереди), но и по времени ожидания (такие СМОназываются «системами с нетерпеливыми клиентами»).СМО с очередью различаются не только по ограничениям очереди, нои по дисциплине обслуживания: обслуживаются ли заявки в порядке поступления, или в случайном порядке, или же некоторые заявки обслуживаются вне очереди (так называемые «СМО с приоритетом»). Приоритетможет иметь несколько градаций или рангов.Аналитическое исследование СМО является наиболее простым, есливсе потоки событий, переводящие ее из состояния в состояние, — простейшие (стационарные пуассоновские).
Это значит, что интервалы временимежду событиями в потоках имеют показательное распределение с параметром, равным интенсивности соответствующего потока. Для СМО этодопущение означает, что как поток заявок, так и поток обслуживании —простейшие. Под потоком обслуживании понимается поток заявок, обслуживаемых одна за другой одним непрерывно занятым каналом. Этот поток363оказывается простейшим, только если время обслуживания заявки Тобслпредставляет собой случайную величину, имеющую показательное распределение.
Параметр этого распределения |л есть величина, обратная среднему времени обслуживания: |л = 1 / to6cjl, где to6cJl = М [То6сл ]. Вместо «потокобслуживании — простейший» часто говорят «время обслуживания показательное». Условимся в дальнейшем для краткости всякую СМО, в которой все потоки простейшие, называть простейшей СМО. В этой главе будем рассматривать главным образом простейшие СМО.Если все потоки событий простейшие, то процесс, протекающий вСМО, представляет собой марковский случайный процесс с дискретными состояниями и непрерывным временем. При выполнении некоторыхусловий для этого процесса существует финальный стационарный режим, при котором как вероятности состояний, так и другие характеристики процесса не зависят от времени.Задачи теории массового обслуживания — нахождение вероятностейразличных состояний СМО, а также установление зависимости между заданными параметрами (числом каналов п, интенсивностью потока заявокX, распределением времени обслуживания и т.д.) и характеристикамиэффективности работы СМО.
В качестве таких характеристик могут рассматриваться, например, следующие:среднее число заявок А, обслуживаемое СМО в единицу времени, илиабсолютная пропускная способность СМО;вероятность обслуживания поступившей заявки Q или относительная пропускная способность СМО; Q = А / X;вероятность отказа РОТК, т.е. вероятность того, что поступившая заявкане будет обслужена, получит отказ; Ротк = 1 — Q;среднее число заявок в СМО (обслуживаемых или ожидающих в очереди) I;среднее число заявок в очереди г ;среднее время пребывания заявки в СМО (в очереди или под обслуживанием) ^ист'усреднее время пребывания заявки в очереди tOH;среднее число занятых каналов к.В общем случае все эти характеристики зависят от времени.
Но многиеСМО работают в неизменных условиях достаточно долгое время, и поэтомудля них успевает установиться режим, близкий к стационарному. Мы здесьповсюду, не оговаривая этого каждый раз специально, будем вычислять финальные вероятности состояний и финальные характеристики эффективности СМО, относящиеся к предельному, стационарному режиму ее работы.Для любой открытой СМ0 1 } в предельном стационарном режимесреднее время пребывания заявки в системе tCiiCT выражается через среднее число заявок в системе с помощью формулы Литтла:WT = z / \где X — интенсивность потока заявок.(11.0.1)СМО называется открытой, если интенсивность поступающего на нее потока заявок не зависит от состояния самой СМО.364|X0»|IlX2» 4 - 1 IiVjHiИ2H3HjfcX|4»HA:+1n-l|1КРис.
11.01Аналогичная формула (называемая также формулой Литтла) связывает среднее время пребывания заявки в очереди tQ4 и среднее число г заявок в очереди:L=r/\.,(11.0.2)Формулы Литтла очень полезны, так как позволяют вычислять не обехарактеристики эффективности (среднее время пребывания и среднеечисло заявок), а только какую-нибудь одну из них.Специально подчеркнем, что формулы (11.0.1) и (11.0.2) справедливыдля любой открытой СМО (одноканальной, многоканальной, при любыхвидах потоков заявок и обслуживании); единственное требование к потокам заявок и обслуживании — чтобы они были стационарными.Аналогично универсальное значение для открытых СМО имеет формула, выражающая среднее число занятых каналов к через абсолютнуюпропускную способность А:k=A/\i,(11.0.3)где [i = 1 / ^у, — интенсивность потока обслуживании.Очень многие задачи теории массового обслуживания, касающиесяпростейших СМО, решаются с помощью схемы гибели и размножения(см.
гл. 10). Если граф состояний СМО может быть представлен в виде,показанном на рис. 11.0.1, то финальные вероятности состояний выражаются формулами (10.0.23):j WРо =\ 1 + -^-,| \)\---\fc-i .. \)V--^n-iM-iM-2-M-»Н-1^2PiР2 = - i L - L P o ; - M-lM-2=—Po,НаPk_/AХnXi...0'Ч[1г\Х2AQAJ... AА-^Po(0<*<n);...;НчJ(11.0.4)При выводе формул для среднего числа заявок (в очереди или в системе) широко используется прием дифференцирования рядов, состоящий вследующем. Если х < 1, тоiкхEit=iк\—"V d= х у.—хfcidxкd \—^ьdXX= х —> х = х=-,dx j~4dx 1 — x(1 — x)и окончательно5>»= (1-х)*k=i(11.0.5)365Ниже приведем без вывода ряд формул, выражающих финальные вероятности состояний и характеристики эффективности для некоторыхчасто встречающихся типов СМО.
Другие примеры СМО будут разобраны далее в виде задач.1. Простейшая СМО с отказами (задача Эрланга). На п-канальнуюСМО с отказами поступает простейший поток заявок с интенсивностьюX, время обслуживания — показательное с параметром JJL = 1 / io6cjl. Состояния СМО нумеруются по числу заявок, находящихся в СМО (в силуотсутствия очереди, оно совпадает с числом занятых каналов):50 — СМО свободна;s2 — занят один канал, остальные свободны; ...;sk— занято А; каналов, остальные свободны ( 1 < А ; < п ) ; . . .
;sn — заняты все п каналов.Финальные вероятности состояний выражаются формулами Эрланга:-1V1+JL + £l + ... + £:1!2!Р * = ^ Р о ( * = 1,2,...,п), (11.0.6)п\где р = X / |х.Характеристики эффективности:Л = X (1 - рп);Q = l - рп;Ротк - рп;к = р (1 - рп). (ц.о.7)При больших значениях п вероятности состояний (11.0.8) удобно вычислять через табулированные функции:тР (га, а) = — е~ат!^распределение Пуассона,)7/1(11.0.8)ЛД(т,а) = £ ^ - е -а(11.0.9)(см. прил. 1), из которого первую можно выразить через вторую:Р(т, a) = R (m,a)-R(m - 1 , а).(11.0.10)Пользуясь этими функциями, формулы Эрланга (11.0.6) можно переписать в видерА = Р ( * , р ) / Д ( п , р ) (* = 0,1,...,п).(11.0.11)2.
Простейшая одноканальная СМО с неограниченной очередью. Наодноканальную СМО поступает простейший поток заявок с интенсивностью X. Время обслуживания — показательное с параметром \х = 1 / t^^.Длина очереди не ограничена. Финальные вероятности существуют только при р = X / [I < 1 (при р > 1 очередь растет неограниченно). СостоянияСМО нумеруются по числу заявок в СМО, находящихся в очереди илиобслуживамых:50 — СМО свободна;s1 — канал занят, очереди нет;366s2 — канал занят, заявка стоит в очереди;...;sk — канал занят, к — 1 заявок стоят в очереди;....Финальные вероятности состояний выражаются формулами:р0 = 1 - р , р* = р * ( 1 - р ) (* = 1,2,...),(11.0.12)гдер = Х/р, < 1.Характеристики эффективности СМО:А=\j = _iL_.1-рf=_e!_.1-рQ=l;P OTK =0;pi• i=(11.0.13)£•Х(1-р)Х(1-р)(11014)среднее число занятых каналов (или вероятность того, что канал занят)к = Х/р, = р.(11.0.15)3.
Простейшая одноканальная СМО с ограничением по длине очереди. На одноканальную СМО поступает простейший поток заявок с интенсивностью X; время обслуживания — показательное с параметромр = 1 / ^ ^ . В очереди т мест. Если заявка приходит в момент, когда всеэти места заняты, она получает отказ и покидает СМО.
Состояния СМО:50 — СМО свободна;Sj — канал занят, очереди нет;52 — канал занят, одна заявка стоит в очереди;...;sk — канал занят, к — 1 заявок стоят в очереди;...;5 т+1 — канал занят, га заявок стоят в очереди.Финальные вероятности состояний существуют при любом р = X / р, иравны:р0 =* ~ р+ ;1-р т 2Л= Р Ч ( * = 1 . - > ™ + 1).(п.0.16)Характеристики эффективности СМО:А = X (1 - pm+l);Q = 1 - рт+1;РОТК =pm+vСреднее число занятых каналов (вероятность того, что канал занят)к=1-р0.(11.0.17)Среднее число заявок в очередиm^ _ Рр2 I[1(m 1-+ *1- - ™РЛтр)]1 - p- Р I™F =W+ 2 /-./-.тп+2\\'(1-P)(1-P)(11.018)V* */Среднее число заявок в СМОz=r+ k.(11.0.19)По формуле Литтла*сист=^/^;4>ч = г / \ .(11.0.20)3674.
Простейшая многоканальная СМО с неограниченной очередью.На n-канальную СМО поступает простейший поток заявок с интенсивностью X; время обслуживания одной заявки — показательное с параметром \i = 1 / i ^ . Финальные вероятности существуют только приР / п — X < 1> г Д е Р = ^ / М" Состояния СМО нумеруются по числу заявокв СМО:s0 — СМО свободна;sl — занят один канал; ...;очереди нет;sk— занято к каналов (1 < к < п); ...;sn — заняты все п каналов;5п+1 — заняты все п каналов, одна заявка стоит в очереди; ...;sn+r— заняты все п каналов, г заявок стоят в очереди; ....Финальные вероятности состояний выражаются формулами:Ро ='Iпn+11 1_1JоL + .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
