Теория массового обслуживания презентация

Содержание

Теория массового обслуживания начала развиваться в начале XX столетия. Основоположником теории массового обслуживания считается датский ученый Агнер Краруп Эрланг. В 1909 г. Эрланг применил теорию вероятностей к исследованию

Слайд 1Теория массового обслуживания
это математическая теория, ставящая целью изучение систем массового

обслуживания (СМО).


ЭЛЕМЕНТЫ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ


Слайд 2Теория массового обслуживания начала развиваться в начале XX столетия.
Основоположником теории

массового обслуживания считается датский ученый Агнер Краруп Эрланг.

В 1909 г. Эрланг применил теорию вероятностей к исследованию зависимости обслуживания телефонных вызовов от числа поступивших на телефонную станцию вызовов.


Слайд 3Значительный вклад в создание и разработку общей теории массового обслуживания внес

выдающийся советский математик Александр Яковлевич Хинчин (1984 – 1959).


Он предложил сам термин теория массового обслуживания и систематизировал основные положения теории системы массового обслуживания в монографии «Работы по математической теории массового обслуживания»


Слайд 4В зарубежной литературе теория массового обслуживания известна под названием «Теория очередей».


Слайд 5Для достижения этой цели ставятся задачи теории массового обслуживания, состоящие в

установлении зависимостей эффективности функционирования СМО от ее организации (параметров):

Слайд 6В сфере производства и обслуживания примерами СМО могут служить:


Слайд 7
Такие системы как компьютерные сети, системы сбора, хранения и обработки информации,

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


Слайд 8Случайные процессы и потоки событий
В качестве аппарата теории систем массового обслуживания

используют понятия теории случайных величин, а также теории случайных процессов.

Случайным процессом, или случайной функцией S(t), называется функция, которая каждому моменту времени t; из некоторого временного промежутка ставит в соответствие единственную случайную величину S(t).

Если состояния системы S изменяются во времени случайным образом, то будем говорить, что в системе S протекает случайный процесс.

По множеству состояний системы S протекающий в ней случайный процесс может быть дискретным или непрерывным.

Случайный процесс, протекающий в системе S , называется марковским, если обладает свойством отсутствия последействия, или отсутствия памяти, т.е. для любого фиксированного момента времени t0 вероятность состояния в будущем (при ) зависит только от состояния системы в настоящем (при ) и не зависит от того, как развивался этот процесс в прошлом (при ).


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

в случайные моменты времени.

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

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

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


Слайд 10Поток событий называется ординарным, если вероятность наступления за достаточно малый (элементарный)

промежуток времени более одного события пренебрежимо мала по сравнению с вероятностью наступления одного события за этот промежуток.

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

Простейшим (пуассоновским) называется поток событий, который обладает свойствами стационарности, отсутствия последействия и ординарности.



Интенсивностью потока ʎ называют среднее число событий, которые появляются в единицу времени.


Слайд 11Теорема 8.1.
Если постоянная интенсивность потока ʎ известна, то вероятность появления m

событий простейшего потока за время длительностью определяется формулой Пуассона


Эта теорема является основополагающей для теории систем массового обслуживания.
Формула (8.1) отражает все свойства простейшего потока.

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


Слайд 12Пример 8.1.
На автоматическую телефонную станцию поступает простейший поток вызовов с интенсивностью

λ =1,2 вызовов в минуту.
Найти вероятность того, что за две минуты:
а) не придет ни одного вызова;
б) придет ровно один вызов;
в) придет хотя бы один вызов.

Решение.
а) Случайная величина X – число вызовов за две минуты – распределена
по закону Пуассона с параметром λτ =1,2 ∙ 2 = 2,4 . Вероятность того, что вызовов не будет (m = 0 ), по формуле (8.1):

.
б) Вероятность одного вызова (m = 1) по формуле (8.1):


в) Вероятность хотя бы одного вызова:

.


.


.


Слайд 13
Каждая СМО включает в свою структуру некоторое число обслуживающих устройств (пунктов,

приборов, линий), которые называют каналами обслуживания. Роль каналов могут играть лица, выполняющие те или иные операции линии связи, автомашины, краны, ремонтные бригады, железнодорожные пути, бензоколонки.



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


Слайд 14Обслуживание заявок, в общем случае, также длится не постоянное, заранее известное,

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

Схема СМО изображена на рисунке.


Слайд 15
Таким образом, во всякой СМО можно выделить следующие основные элементы:
1) входящий

поток заявок;
2) очередь;
3) каналы обслуживания;
4) выходящий поток обслуженных заявок.

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


Слайд 16В качестве характеристик эффективности функционирования СМО можно выбрать три основные группы

показателей:

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


Слайд 17ПО ЧИСЛУ КАНАЛОВ
Одноканальные
Имеется один канал обслуживания
Многоканальные
Количество каналов n ≥ 2
Могут состоять

из

однородных каналов
разнородных каналов
Каналы отличаются длительностью обслуживания одной заявки.

Практически время обслуживания каналом одной заявки T об является непрерывной случайной величиной. Однако при условии абсолютной однородности поступающих заявок и каналов время обслуживания может быть и величиной постоянной (T об = const).

Классификация систем массового обслуживания


Слайд 18По дисциплине обслуживания СМО подразделяют на три класса
1. СМО с отказами.

Заявка, поступившая на вход СМО в момент, когда все каналы заняты, получает «отказ» и покидает СМО.

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

2. СМО с ожиданием (неограниченным ожиданием или очередью).

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

Слайд 193. СМО смешанного типа (с ограниченным ожиданием).

Это такие системы, в которых

на пребывание заявки в очереди накладываются некоторые ограничения.

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


Слайд 20ОДНОКАНАЛЬНЫЕ СМО
Пусть СМО состоит только из одного канала (n=1).
Будем изучать

эту CMO при следующих предположениях:
1. Входной поток является пуассоновским с параметром l.

2. Время обслуживания подчиняется экспоненциальному закону с параметром m:

3. Время обслуживания требования не зависит от количества требований, поступивших в систему.



Слайд 21Одноканальная СМО с отказами
При указанных выше предположениях СМО в любой момент

времени t может находиться в одном из двух состояний: – в системе 0 требований (система свободна) или – в системе 1 требование (система занята).

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


Слайд 22Для составления матрицы перехода мы должны вычислить
Имеем:






Перейдем к решению следующей важной

задачи: нахождению вероятностей и пребывания системы в каждом из возможных состояний.







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

поступлениями требований, так и длительностей обслуживания. При этом плотность распределения длительностей интервалов между поступлениями требований имеет вид

Слайд 28Одноканальная СМО с ожиданием и ограниченной очередью

Система массового обслуживания имеет один

канал. Входящий поток заявок на обслуживание поток имеет интенсивность λ. Интенсивность потока обслуживания равна μ (т. е. в среднем непрерывно занятый канал будет выдавать μ обслуженных заявок).

Длительность обслуживания — случайная величина, подчиненная показательному закону распределения. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.

Рассмотрим систему с ограниченной очередью. Предположим, что независимо оттого, сколько требований поступает на вход обслуживающей системы, данная система (очередь + обслуживаемые клиенты) не может вместить более N-требований (заявок), из которых одна обслуживается, а
(N-1) ожидают, Клиенты, не попавшие в ожидание, вынуждены обслуживаться в другом месте и такие заявки теряются.


Слайд 29
Интенсивность потока обслуживаний автомобилей:


Приведенная интенсивность потока автомобилей определяется как отношение интенсивностей

λ и μ, т.е.


Вычислим вероятности нахождения п заявок в системе:


P1=ρ∙P0=0,893∙0,248=0,221;
P2=ρ 2∙P0=0,8932∙0,248=0,198;
P3=ρ 3∙P0=0,8933∙0,248=0,177;
P4=ρ 4∙P0=0,8934∙0,248=0,158.
Вероятность отказа в обслуживании автомобиля:
Pотк=Р4= ρ 4∙P0≈0,158.
Относительная пропускная способность окна оформления:
q=1–Pотк=1-0,158=0,842.
Абсолютная пропускная способность окна оформления
А=λ∙q=0,85∙0,842=0,716 (автомобиля в час).

В зону таможенного контроля в пункте пропуска автомобили въезжают по системе электронной очереди. Каждое окно оформления прибытия/убытия представляет собой одноканальную СМО. Число стоянок для автомобилей, ожидающих оформления , ограниченно и равно 3, то есть (N-1)=3. Если все стоянки заняты, т. е. в очереди уже находится три автомобиля, то очередной автомобиль в зону таможенного контроля не пропускается, т.е. в очередь на обслуживание не становится. Поток автомобилей, прибывающих на оформление имеет интенсивность λ=0,85 (автомобиля в час). Время оформления автомобиля распределено по показательному закону и в среднем равно =1,05 час. Требуется определить вероятностные характеристики окна оформления прибытия/убытия пункта пропуска, работающего в стационарном режиме.

Решение


Слайд 30
Среднее число автомобилей, находящихся на обслуживании и в очереди (т.е. в

системе массового обслуживания):

Среднее время пребывания автомобиля в системе:
часа.
Средняя продолжительность пребывания заявки в очереди на обслуживание:
Wq=Ws-1/μ=2,473-1/0,952=1,423 часа.
Среднее число заявок в очереди (длина очереди):
Lq=λ∙(1-PN)∙Wq=0,85∙(1-0,158)∙1,423=1,02.





Работу рассмотренного окна оформления можно считать удовлетворительной, так как не обслуживается в среднем 15,8% случаев (Ротк=0,158).


Слайд 31Одноканальная СМО с ожиданием и неограниченной очередью


Перейдем теперь к рассмотрению одноканальной

СМО с ожиданием без ограничения на вместимость блока ожидания (т.е. Ν → ∞). Остальные условия функционирования СМО остаются без изменений.
Устойчивое решение в такой системе существует только тогда, когда λ<μ, то есть заявки должны обслуживаться с большей скоростью, чем поступают, в противном случае очередь может разрастись до бесконечности.
Вероятность того, что в системе находится п заявок, вычисляется по формуле

,n=0,1,2,…,



Слайд 32Характеристики одноканальной СМО с ожиданием, без ограничения на длину очереди, следующие:

среднее

число находящихся в системе клиентов (заявок) на обслуживание:




средняя продолжительность пребывания клиента в системе:




среднее число клиентов в очереди на обслуживание:




средняя продолжительность пребывания клиента в очереди:





Слайд 33Пример 9.3
Пусть рассматриваемое зона таможенного контроля в пункте пропуска располагает

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


Слайд 34Решение
Параметр потока обслуживания  и приведенная интенсивность потока
автомобилей ρ определены в предыдущем

примере: μ=0,952; ρ=0,893.
Вычислим предельные вероятности системы по формулам
P0=1- ρ =1-0,893=0,107;
P1=(1- ρ)· ρ =(1-0,893)·0,893=0,096;
P2=(1- ρ)· ρ 2=(1-0,893)·0,8932=0,085;
P3=(1- ρ)· ρ 3=(1-0,893)·0,8933=0,076;
P4=(1- ρ)· ρ 4=(1-0,893)·0,8934=0,068;
P5=(1- ρ)· ρ 5=(1-0,893)·0,8935=0,061 и т.д.
Следует отметить, что Р0 определяет долю времени, в течение которого окно оформления вынужденно бездействует (простаивает). В нашем примере она составляет 10, 7%, так как Р0=0,107. Среднее число автомобилей, находящихся в системе (на обслуживании и в очереди):




ед.


Слайд 35Средняя продолжительность пребывания клиента в системе:



Слайд 36

Среднее число автомобилей в очереди на обслуживание:



Слайд 37Средняя продолжительность пребывания автомобиля в очереди:


Слайд 38Относительная пропускаемая способность системы равна единицы, так как все поступившие заявки

рано или поздно будут обслужены: q=1.


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


Слайд 39
Следует отметить, что пункт таможенного контроля, осуществляющий оформления автомобилей, прежде всего,

интересует количество клиентов, которое посетит окно оформления при снятии ограничения на длину очереди.


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


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



Слайд 40При 12-часовом режиме работы окна оформления это эквивалентно тому, что окно

оформления в среднем за смену (день) будет терять 12∙0,134=1,6 автомобиля.

Снятие ограничения на длину очереди позволяет увеличить количество обслуживаемых клиентов в нашем примере в среднем на 1,6 автомобиля за смену (12 ч. работы) пункта оформления.

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


Слайд 41В подавляющем большинстве случаев на практике система массового обслуживания является многоканальными,

то есть параллельно могут обслуживаться несколько заявок, и, следовательно, модели с обслуживающими каналами (где число каналов обслуживания n>1) представляют несомненный интерес.
Процесс массового обслуживания, описываемый данной моделью, характеризуется интенсивностью входного потока λ, при этом параллельно может обслуживаться не более n клиентов (заявок). Средняя продолжительность обслуживания одной заявки равняется . Режим функционирования того или иного обслуживающего канала не влияет на режим функционирования других обслуживающих каналов системы, при чем длительность процедуры обслуживания каждым из каналов является случайной величиной, починенной экспоненциальному закону распределения. Конечная цель использования параллельно включенных обслуживающих каналов заключается в повышение (по сравнению с одноканальной системой) скорости обслуживания требований за счет обслуживания одновременно n клиентов.

Многоканальная СМО с отказами


Слайд 42Стационарное решение системы имеет вид:
где



Формулы для вычисления вероятностей называются формулами

Эрланга.

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

вероятность отказа:

Так как заявка получает отказ, если приходит в момент, когда все каналы заняты. Величина Ротк характеризует полноту обслуживания входящего потока;
вероятность того, что заявка будет принята к обслуживанию (она же – относительная пропускная способность системы) дополняет Ротк до единицы:


Слайд 43
абсолютная пропускная способность

среднее число каналов, занятых обслуживанием( )

следующее:



Величина характеризует степень загрузки СМО.


Слайд 44Пример 9.4.
Пусть n-канальная СМО представляет собой вычислительный центр (ВЦ) с тремя

(n=3) взаимозаменяемыми ПЭВМ для решения поступающих задач. Поток задач, поступающих на ВЦ, имеет интенсивность λ=1 задача в час. Средняя продолжительность обслуживания tоб=1,8 час.
Требуется вычислить значения:
- вероятности числа занятых каналов ВЦ;
- вероятности отказа в обслуживании заявки;
- относительной пропускной способности ВЦ;
- абсолютной пропускной способности ВЦ;
- среднего числа занятых ПЭВМ на ВЦ.
Определите, сколько дополнительно надо приобрести ПЭВМ, чтобы увеличить пропускную способность ВЦ в 2 раза.
Решение.
Определим параметр μ потока обслуживаний:


Приведенная интенсивность потока заявок



Слайд 45Предельные вероятности состояний найдем по формулам Эрланга:







Вероятность отказа в обслуживании заявки

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

пропускная способность ВЦ


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


Среднее число занятых каналов – ПЭВМ



Слайд 46Таким образом, при установившемся режиме работы СМО в среднем будет занято

1,5 компьютера из трех – остальные полтора будут простаивать. Работу рассмотренного ВЦ вряд ли можно считать удовлетворительной, так как центр не обслуживает заявки в среднем в 18% случаев (Р3= 0,180). Очевидно, что пропускную способность ВЦ при данных λ и μ можно увеличить только за счет увеличения числа ПЭВМ.
Определим, сколько нужно использовать ПЭВМ, чтобы сократить число не обслуженных заявок, поступающих на ВЦ, в 10 раз, т.е. чтобы вероятность отказа в решении задач не превосходила 0,0180. Для этого используем формулу вероятности отказа:


Составим следующую таблицу:

Анализируя данные таблицы, следует отметить, что расширение числа каналов ВЦ при данных значениях λ и μ до 6 единиц ПЭВМ позволит обеспечить удовлетворение заявок на решение задач на 99,22%, так как при n = 6 вероятность отказа в обслуживании (Ротк) составляет 0,0078.


Слайд 47Многоканальная СМО с ожиданием
Рассмотрим многоканальную систему массового обслуживания с ожиданием. Процесс

массового обслуживания при этом характеризуется следующим: входной и выходной потоки имеют интенсивности λ и μ соответственно, параллельно обслуживаться могут не более С клиентов, то есть система имеет С каналов обслуживания.

Средняя продолжительность обслуживания одного клиента равна



Вероятности того, что в системе находятся п заявок (С обслуживаются, остальные ожидают в очереди) равна:



где



Решение будет действительным, если выполняется следующее условие: 





Слайд 48Остальные вероятностные характеристики функционирования в стационарном режиме многоканальной СМО с ожиданием

и неограниченной очередью определяется по следующим формулам:

среднее число клиентов в очереди на обслуживание



среднее число находящихся в системе клиентов (заявок на обслуживание и в очереди)

LS=Lq+ρ;

средняя продолжительность пребывания клиента (заявки на обслуживание) в очереди



средняя продолжительность пребывания клиента в системе



Рассмотрим примеры многоканальной системы массового обслуживания с ожиданием.

Пример 9.5. Таможня с тремя таможенными постами (каналами) выполняет пропуск товаров. Поток неправильно заполненных деклараций, для товаров прибывающих на таможню,  - пуассоновский и имеет интенсивность λ=2,5 у.е. в сутки, среднее время оформления одной заявки распределено по показательному закону и равно tоб=0,5 часа. Предположим, что другой таможни в округе нет, и, значит, очередь деклараций может расти практически неограниченно.


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

заявок в очереди на обслуживание;

среднее число находящихся в системе заявок;

среднюю продолжительность пребывания заявки в очереди;

среднюю продолжительность пребывания заявки в системе.

Решение.

Определим параметр потока обслуживаний







Приведенная интенсивность потока заявок

ρ=λ/μ=2,5/2,0=1,25,

при этом λ/μ ∙с=2,5/2∙3=0,41<1.

Поскольку λ/μ∙с<1, то очередь не растет безгранично и в системе наступает предельный стационарный режим работы.
Вычислим вероятности состояний системы:












Слайд 50Вероятность отсутствия очереди на таможне
Ротк≈Р0+Р1+Р2+Р3≈0,279+0,394+0,218+0,091=0,937.
Среднее число заявок в очереди на обслуживание

Среднее

число находящихся в системе заявок

Ls=Lq+ρ=0,111+1,25=1,361.

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


часа

Средняя продолжительность пребывания заявки на таможне (в системе)


часа.


Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика