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

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

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

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

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

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

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

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

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

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

Теорема 8.1. Если постоянная интенсивность потока ʎ известна, то вероятность появления m событий простейшего потока за время длительностью определяется формулой Пуассона

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

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

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

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

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

По числу каналов Одноканальные

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

ОДНОКАНАЛЬНЫЕ СМО

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

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

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

Интенсивность потока обслуживаний автомобилей: Приведенная интенсивность потока автомобилей определяется как отношение интенсивностей λ и μ, т.е. Вычислим вероятности нахождения п заявок в системе: 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 (автомобиля в час).

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

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

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

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

Решение Параметр потока обслуживания  и приведенная интенсивность потока автомобилей ρ определены в предыдущем примере: μ=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. Среднее число автомобилей, находящихся в системе (на обслуживании и в очереди):

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

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

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

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