Теория вероятности. Вентцель Е.С (4-е издание) (1082431), страница 95
Текст из файла (страница 95)
19.10. Система массового обслуживания с ожиданием Система массового обслуживания называется сисшемой с ожиданием, если ваявка, ваставшая все каналы занятыми, становится в очередь и ждет, пока не освободится какой-нибудь канал. Если время ожидания заявки в очереди ничем не ограничено, то система называется «чистой системой с ожиданием>.
Если оно ограничено какими-то условиями, то система называется «системой смешанного типа». Это промежуточный случай между чистой системой с отказами и чистой системой с ожиданием, Для практики наибольший интерес представляют именно системы смешанного типа. Ограничения, наложенные на ожидание, могут быть различного типа.
Часто бывает, что ограничение накладывается на время о ж ид а н и я в а я в к и в о ч е р е д и; считается, что оно »ограничено сверху каким-то сроком Т, . который может быть как строго определенныи, так и случайным. Прн этом ограничивается только срок ожидания в очере [и з нзчзтое обсЧса ванне доводится до кон[ш. Веззв,.сичз от того, сколько времени продолжалось ожидание (например, клиент в парикмахерской, сев в кресло, обычно уже не уходит до конца обслуживания). В других задачах естественнее наложить ограничение не на время ожидания в очереди, а на общее в рема п р сбывания заявки в системе (например, воздушная цель может пробыть в зоне стрельбы лишь ограниченное время н покидзет ее независимо от того, кончился обстрел илн нет).
Наконец, можно рассмотреть и такую смешанную систему (она ближе всего к типу торговых предприятии, торгующих предметами не первой необходимости). когда заявка становится в очередь только в том случае, если длина гзл01 системА мАссОВОГО ОБслужиВАния с О)кидАнием 549 очереди не слишком велика. Здесь ограничение накладывается на число заявок в очереди. В системах с ожиданием существенную роль играет так называемая «дисциплина очереди». Ожидающие заявки могут зызызагося на обслуживание как в порядке очереди (раньше прибывший раньше и обслуживается), так и в случайном, неорганизованном порядке.
Существуют системы массового обслуживания «с преимушествами», где некоторые заявки обслуживаются предпочтительно перед другими («генералы и полковники вне очереди»). Каждый тнп системы с ожидзнием имеет свои особенности и свою математическую теорию. Многие из них описаны, например, з книге В. В. Гнеденко «Лекции по теории массового обслуживания». Здесь мы остановимся только на простейшем случае смешанной системы, являющемся естественным обобщением задачи Эрланга лля системы с отказами. Для этого случая мы выведем дифференциальные уравнения, аналогичные уравнениям Эрланга, и формулы для вероятностей состояний в установившемся режиме, аналогичные формулам Эрланга.
Рассмотрим смешанную систему массового обслуживания Х с л каналами при следующих условиях. На вход системы поступает простейший поток заявок с плотностью ). Время обслуживания одной 1 ааявки Т,о — показательное, с параметром р= —. Заявка, заставгл ~ шая все каналы занятыми, становится в очередь и ожидает обслуживания; время ожидания ограничено некоторым сроком Т,; если до истечения этого срока заявка не будет принята к обслуживанию, го она покидает очередь и остается необслуженной.
Срок ожидания Т„„ будем считать случайным и распределенным по показательному закону л (Г) = оег и (1 > О), где параметр ч †величи, обратная среднему сроку ожидания: т, =,И (Т„,„1. 1 гож Параметр» полностью аналогичен параметрам А и р потока заявок и «потока освобождений». Его можно интерпретировать, как плотность «потока уходов» заяви... стоящей в Очереди, Действительно, представим себе заявку, которая только и делает. что становится в очередь и ждет в ней, пока не кончится срок ожидания То., после чего уходит и сразу;ке снова становится в очередь. Тогда «пооок уходов» такой заявки нз очереди будет иметь плотность ж Очевидно, при у — »со система смешанного типа превращается в ччстуо снст ...
с отказ .п.; ..рц у —. О "..", Бращаетс. о чист) систему с ожиданием. ББО злзмзнты тзояин массового озслтживання (гл ю Заметим, что при показательном законе распределения срока ожи« дания пропускная способность системы не зависит от того, обслуживаются ли заявки в порядке очереди илн в случайном порядке; для каждой заявки закон распределения оставшегося времени ожидания не аависнт от того, сколько времени заявка уже стояла в очереди. Благодаря допущению о пуассоновском характере всех потоков событий, приводящих к изменениям состояний системы, процесс, протекающий в ней, будет марковским.
Напишем уравнения для вероятностей состояний системы. Для етого, прежде всего, перечислим эти состояния. Будем их нумеровать не по числу занятых каналов, а по числу связанных с системой заявок. Заявку будем называть «связанной с системой». если она либо находится в состоянии обслуживания, либо ожидает очереди.
Возможные состояния системы будут: хе — ни один канал не занят (очереди нет), х, — занят ровно один канал (очередп нет), х» — занято ровно Й каналов (очереди нет), х„— заняты все л каналов (очереди нет), х„„~ — заняты все л каналов, одна заявка стоит в очереди, лв+, — заняты все л каналов, з заявок стоят в очереди, Число заявок а, стоящих в очереди, в наших условиях может быть сколь угодно большим. Таким образом, система Х имеет бесконечное (хотя и счетное) множество состояний. Соответственно, число описывающих ее дифференциальных уравнений тоже будет бесконечным. Очевидно, первые л дифференциальных уравнений ничем не будут отличаться от соответствующих уравнений Эрлангв: — = — Лр,(1)+ рр,(г), лр,(г) лР„(г) — =ЛР— (1) — (Л+Фр) Р И)+(а+1)РР Ю.
— =ЛРл-,(г) — (Л+(и — 1) Р1 Рл-~ (г)+ п(ьРп(г) Отличие новых уравнений от уравнений Эрланга начнется прп й=п. Действительно, в состояние лл система С отказами может ш!01 снствмА мАссового ОвслужиВАння с одгявалнням 351 перейти только иэ состояния х„,; что касается системы с ожиданием, то она может перейти в состояние х не только нэ х,, ио и иэ х„+, (все каналы заняты, одна заявка стоит в очереди).
Составим дифференпиальное уравнение для р„(Е). Зафиксируем момент Е и найдем р„(1+йЕ) — вероятность того, что система в момент Е+!ЛЕ будет в состоянии х,, Это может осуществиться тремя способам н: 1) в момент Е система уже была в состоянии х„а эа время !ЛЕ не вышла иэ него (не пришла ни одна эаявка и ни один иэ каналов не освободился); 2) в момент Е система была в состоянии х„г, а аа время йЕ перешла в состояние х„(пришла одна эаявка); 3) в момент Е система была в состоянии х„, (все каналы заняты, одна заявка стоит в очереди), а эа время Е!Е перешла в х„(либо освободился один канал и стоящая в очереди ааявка эаняла его, либо стоящая в очереди заявка ушла в связи с окончанием срока).
Имеем: р„(1+ДЕ) = р„(Е)(1-ЛйŠ— ар.бЕ)+ + р„! (Е) ЛЕЯЕ+ р„„(Е) (лр+ «) д Е, откуда ~" () = — (Л+лр) р„(Е)+Лрл, г(Е)-+(пр+ «) р „,(Е). Вычислим теперь р„ч,(Е+йЕ) при любом г ) Π— вероятность того, что в момент Е+йЕ все а каналов будут заняты н ровно а эаявок будут стоять в очереди. Это событие снова может осуществиться тремя способами: 1) в момент Е система уже была в состоянии х„„„а аа время !ЛЕ это состояние не иаменилось (значит, ни одна ааявка не пришла, ни один канал не освободился и нн одна иэ я стоящих в очереди ааявок не ушла); 2) в момент Е система была в состоянии х„ч,, а эа время АЕ перешла в состояние х„ь, (т, е.
пришла одна заявка); 3) в момент Е система была в состоянии х„„~!, а эа время ДЕ перешла в состояние х„ч, (для этого либо один из каналов должен о! яо!'Ол!!тъсч, н тогда едня пэ я, ! стоян!!!х а гчергли яячэпк Зяй мет его, либо одна иэ стоящих в очереди заявок должна уйти в связи с окончанием срока). Следовательно: р,,(Е+ ЬЕ) = р„„,(Е)(1 — ЛАŠ— пр ОŠ— э«дг)-+ + !эл«..
!(Е)»пг+РЯ„,~!(Е) [лр+(г+ 1) «) Е!Е. откуда — '";; '= — (Л+ р+")р...(Е)-+ +Л)г„, г(Е)-1-1 и+( +1) ) р„ 552 ЭЛЕМЕНТЫ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ [ГЛ. !З Таким образом, мы получили для вероятностей состояний систему бесконечного числа дифференциальных уравнений: Л) = Лре (г) + [ьр[ (г) лра(О лР,',( ) =Лр,([) — (Л+ р) р, (г)+ 2рра([). Фр (О „',— = лр,, ([) — (л+ йр) р, ([)+(й+ 1) рр,, ([) (1 ( [г ( и — 1), (19.10.1) ~„"~ ) =ур„, (т) — (Л+ пр) р„(Г)+-(п[ь-+ч) р„ч,(Г), Р"„" ( ) =- Лр„, , (Г) — (Л -+ пз -+ зч) р„ , (Г) + +(п[ +-(а+ 1) ч] р„з,з,([).
Уравнения (19.10.1) являются естественным обобщением уравнений Эрланга на случай системы смешанного типа с ограниченным временем ожидания. Параметры )„р, ч в Этих уравнениях могут быть как постоянными, так и переменными. При интегрировании системы(19.10.1> нужно учитывать, что хотя теоретически число возможных состояний системы бесконечно, но на практике вероятности р„„,(Г) при воарастании а становятся пренебрежимо малыми, и соответствующие уравнения могут быть отброшены.
Выведем формулы, аналогичные формулам Эрланга, для вероятностей состояний системы при установившемся режиме обслуживания (при г — РОО). Из уравнений(19.10.1), полагая веера (и=о, ...,п, ...) постоянными, а все проиаводные — равными нулю„получим систему алгебраических уравнений: — лр,+рр, =о, Л.рг — (),+9) р, +29ра =0 лр„,— (А+ар) р,+(к+1) рр„,=о (1 ( «е ( п — 1), (19.10.2) Лр„, — (Л+ п[ь) р„+ (в[А+ ч) р„, =- О, ЛРаеч-г (Л+п[ь+ зч) Р~зч+ -[- 1~[А -[- ( + 1) «! р„е,, = О, система массового овслтживлния с ожиданием 553 !э.!е1 К ним нужно присоединить условие: (19.
10. 3) Найдем решение сисгемы (19.10,2). Для этого применим тот же прием, которым мы пользовались в случае системы с отказами: разрешим первое уравнение относительно р,, подставим во второе, и т. д. Для любого А (а, как и в случае системы с отказами, получим: (19.10.4) Перейдем к уравнениям для А > и (в =и+а.
а)~1). Тем же способом получим: л1И (лн+т) Хч+ ра . )гл+Е Л1на(ЛИ+ ч) (ЛИ+2т) и вообще при любом г)~1 (19.10.5) В обе формулы (19.10.4) и (19.10.5) в качестве сомножителя входит вероятность р. Определим ее из условия (19.!0.3). Подставляя в него выражения (19.10.4) и (19.10.5) для й (и и а)~1г получим: а=о а ! л1иа Ц (ли + лгч) л!=! откуда (19.10.5) Ро— а=о Лл+5 л1иа Ц (ли+ тч) гл!-ь + ч=! и!ил И(ли+и!0 л 1 554 элвмянты твовмм массового овслвжмвлння 1гл, ы Преобразуем выражения (19.10.4), (19.10.5) и.-(19.10,6), вводя в них вместо плотностей ), и ч «приведенные» плотности: 1 й !аб ъ й аб = "л!! =Р (19.10.7) Параметры а н 'р выра>кают соответственно среднее число заявок и среднее число уходов заявки, стоян!ей в очереди, прнходяп!неся на среднее время обслуживания одной заявки.
В новых обозначениях формулы (19.10.4), (19.10.5) и (19.10.6) примут внд: аб Р»= л! Рб (О (А (л); (19.10.8) аа! а Ра (з ',>~ 1); (1 9.10.9) Ра+а = Д (л+ жя) т=1 (19.10.10) Подставляя (19.10.10) в (19.10.8) и (19.10.9), получим окончательные выражения для вероятностей состояний системы! (О < А ~ л); (19.10.11) Ра— У вЂ” "„+ —,',, ~, — — ~~! (н+ лзя) т=! аа а1 ю Д (а+ та) т=! (з)~1). (19.10.12) Рат!— Рб— Х Л1+ а" ~~3 аа ю=! Д (а+жр) системА мАссОВОГО ОБслужиВАния с ОжидАнием 555 19 1Щ Зная вероятности всех состояний системы, можно легко опрсделнть другие интересуюшие нас характеристики. в частности, вероятность Р, того, что заявка покинет систему необслуженной.
Определим ее из следующих соображений: при установившемся режиме вероятность Р„того, что заявка покинет систему необслуженной, есть не что иное, как отношение среднего числа заявок. уходяших из очереди в единицу времени, к среднему числу заявок, поступзюших в единицу времени. Найдем среднее число ааявок. ухоляших нз очереди в единицу времени.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
