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

Содержание: 
1.Модели массового обслуживания 
1.1.Задачи, связанные с обслуживанием очередей -3 
1.2.Функционирование моделей систем массового обслуживания -4 
1.3.Описание математической модели -5 
2.Система обслуживания с пуассоновским потоком на входе и выходе. 
2.1.Система массового обслуживания со специальными свойствами -7 
2.2.Входной поток -8 
2.3.Выходной поток -10 
2.4.Верификация пуассоновского закона распределения при анализе реальных систем -12 
3.Системы массового обслуживания при наличии входного и выходного потоков. 
3.1.Типы структур систем массового обслуживания -12 
3.2.Операцинные характеристики систем массового обслуживания -14 
3.3. Модель(M/M/1):(GD/¥/¥) -15 
3.4. Модель(M/M/1)(GD/N/¥) -16 
4.Литература. -18

 

 

1. Модели массового  обслуживания

1.1. Задачи, связанные  с обслуживанием очередей

 

 

В окружающей нас действительности много реально протекающих процессов обслуживания на транспорте, в торговле, в медицине, в связи и т.д. Все они могут быть изучены, исходя из соответствующих им моделей систем обслуживания. Создание систем телефонной связи и необходимость расчета их пропускной способности послужили в 20-х годах ХХ века стимулом раз¬вития теории массового обслуживания. Первые исследования группы Operations research британских ВВС была посвящена решению задач этой же тема¬тики (очередь самолетов противника, которая обслуживается снарядами зе¬нитных батарей)~ С 1970-х годов интенсивно разрабатываются методы анали¬за и оптимизации процессов обслуживания требований на вычисления с ис¬пользованием одного или нескольких компьютеров (системы разделенного времени).

Представим себе несколько ситуаций:

—очередь покупателей возле касс продовольственного магазина;

—скопление больных, ожидающих своей очереди на прием к врачу;

—группу самолетов, ожидающих разрешения на взлет в крупном аэропор-ту;

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

Все приведенные ситуации объединяет одно общее обстоятельство: пре-бывание в состоянии ожидания. Избавиться от этого в принципе невозможно. Можно лишь надеяться на возможность сокращения времени ожидания до некоторого «приемлемого» предела. Явление ожидания является следствием того, что ни время возникновения потребностей в обслуживании, ни продол¬жительность обслуживания поступившего в обслуживающую систему клиента обычно заранее неизвестны. В математическую модель, адекватно описывающую ситуации, аналогичные приведенным, включается предположение, что входящий поток требований на обслуживание является случайным. Иными словами, последовательность моментов времени поступления требова¬ний (t~,}, рассматривается как последовательность случайных величин. Требо¬вания на обслуживание характеризуются объемом (или длительностью) работы по обслуживанию и могут относиться к определенным классам. Принадлежность требований (клиентов) к определенным классам могут служить основанием для приоритетного обслуживания. Требования, имеющие абсолютный приоритет, обслуживаются в первую очередь. Например, некоторые виды отказов в вычислительных системах имеют абсолютный приоритет и«обслуживание» таких отказов состоит в их выявлении и устранении. 
Для правильного описания вероятностного закона функционирования обслуживающей системы необходимо выделить некоторые количественные характеристики (параметры) обслуживающей системы, ее описывающие. Одной из традиционных характеристик обслуживающей системы является время пребывания в очереди на обслуживание другой характеристикой системы массового обслуживания может служить доля времени, в течение которого находящаяся в функциональной готовности система из-за отсутствия заявок находится в состоянии бездействия (простаивает). Первая характеристика оценивает систему с позиции клиента. Вторая — с позиции загруженности системы. Интуитивно ясно, что чем большее время затрачивает клиент в ожидании обслуживания, тем меньше время, которое система проводит в состоянии бездействия, и, наоборот. Варьируя операционные характеристики обслуживающей системы, можно добиться разумного компромисса клиентов с обслуживающей системой.

 

 

1.2. Функционирование  моделей систем массового обслуживания

 

 

На обслуживающую систему поступают требования (заявки на обслуживание), которые присоединяются к очереди других (ранее поступивших) требований. Обслуживающий узел выбирает одно (из очереди) требование‚ чтобы приступить к его обслуживанию. После завершения процедуры обслужи¬вания ~поступившего из очереди требования система приступает к обслуживанию следующего требования (если таковое есть в блоке ожидания). Цикл функционирования такого рода системы многократно повторяется. При этом предполагается, что переход от обслуживания одного требования к другому происходит мгновенно (без какой-либо задержки).

Основными элементами системы массового обслуживания являются требования (заявки на обслуживание) и механизм обслуживания (обслуживающая система). Основной количественной характеристикой в моделях массо¬вого обслуживания является продолжительность h интервала времени, которое требуется для полного обслуживания i-ого требования с момента ti его поступления в обслуживающую систему до момента ti+h — завершение обслуживания. для характеристики самой обслуживающей системы (собственно обслуживание без ожидания в очереди) достаточно ввести показатель, характеризующий время, расходуемое на обслуживание одного требования.

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

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

—первый пришел — первым обслуживается (собственно очередь);

—пришел последним — первым обслуживается (стек);

—случайный отбор требований из очереди;

—обслуживание в соответствии с уровнем приоритета.

Дополнительными характеристиками системы массового обслуживания являются допустимая вместимость блока ожидания (допустимая длина очереди), а также емкость (мощность) источника требований (конечного или бесконечного). И, наконец, в модели систем массового обслуживания игнорируется индивидуальный характер поведения клиентов, поставляющих требования.

 

 

1.З. Описание математической  модели

 

 

Характеристика входного потока. Обозначим через Рn(t) вероятность наступления n событий (поступлений требований на обслуживание в обслуживающую систему) в интервале времени, длина которого равна t. Среднее число поступающих заявок (требований на обслуживание) в единицу времени будем обозначать l (интенсивность поступления требований).

Характеристика выходного потока. Пусть Qn(t) — вероятность того, что в течение t единиц времени из системы выбывает n клиентов (после завершения их обслуживания). Процесс выбывания такого рода называют процессом чистой гибели. Интенсивность выбывания обслуженных клиентов обозначим

m - среднее число обслуженных клиентов в единицу времени.

Если предположить (это обычно делается при разработке математической модели), что длина интервала времени, в течение которого наступает каждое последнее событие, не зависит от времени, требуемого для реализации пред-шествующего события, то можно определить функцию f(t) — плотность вероятности того, что длина интервала времени между последовательными наступлениями случайного события (поступление требования на обслуживание) равняется t единиц времени (t³0). Так ~как функция f(t) является плотностью распределения вероятностей, то

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

где P{t³T} вероятность того, что интервал времени реализации случайного события не менее Т, а Р0(Т) — вероятность того, что в течение времени Т не реализуется ни одного события.

Поскольку f(t) — плотность вероятности того, что интервал времени между последовательными реализациями случайного события равняется t, то 
Поэтому выполняются следующие равенства: 
Таким образом, 1-F(T) = -Р0¢(Т), (Т>О). 
Дифференцируя правую и левую части последнего неравенства по верхнему пределу Т. получаем

Из теории вероятностей известно, что при заданной плотности распределения вероятностей f(t) наступления случайного события можно найти математическое ожидание (среднее значение) этой случайной величины по формуле

Величина М{Т} — среднее значение временных интервалов между двух последовательных реализаций события. Таким образом, интенсивность потока требований l (среднее количество требований, поступающих в единицу времени) есть величина обратная М(Т), то есть

l= 1/М(Т).

Пусть g(t) — плотность вероятности того, что длина интервала времени между двумя последовательными наступлениями случайного события (завершение обслуживания одного клиента) равна t. Тогда, рассуждая аналогично тому, что мы только что сделали (вместо f(t) ~ g(t)), можно найти выражение для f1(t), если известны плотности Qn(t). Точнее, получим:

В последних равенствах М1(Т) — среднее значение временных интервалов между двумя последовательными обслуживаниями, а m— интенсивность потока обслуживания (среднее количество обслуживаний в единицу времени). 
Понятно, что возможность полного расчета характеристик системы обслуживания возможен лишь для конкретных случаев обслуживающих систем(задание функций Рn(t) и Qn(t)). Наиболее хорошо изучена система обслужи¬вания, состоящая из одного обслуживающего канала, в который поступает пуассоновский поток требований интенсивности l, а на выходе — пуассоновский поток обслуженных интенсивности m.

 

 

2. Система обслуживания  с пуассоновским потоком на  входе и на выходе.

2.1. Система массового  обслуживания со специальными  свойствами.

 

 

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

Свойство 1. Процессы поступления требований на обслуживание и выбытия обслуженного клиента имеют стационарный характер (стационарный процесс). Это означает, что вероятность наступления событий (на входе и на выходе) в интервале [t, t+h] зависит лишь от h, то есть вероятность такого события не зависит ни от количества событий, ни от момента времени t.

Свойство 2. Для бесконечно малого значения длины интервала h вероятность реализации события больше нуля, но меньше единицы.

Свойство 3. На бесконечно малом отрезке времени h реализуется не более одного события. 
Свойство 1 означает, что события равновероятны и независимы. Отсюда по теореме умножения вероятностей при n = 0 следует, что

Р0(t+h) = Р0(t).Р0(h).

Вычитая из правой и левой частей последнего равенства величину P0(t), поделив левую и правую части на h, сгруппировав члены левой и правой частей равенства нужным образом, получим равенство, тождественное исходному

(Р0(t+h) — Р0(t))/h = - [(1 – Р0(h))/h].Р0(t).

Перейдя в последнем равенстве к пределу при h® 0 и обозначив через a величину Р0(t) (производная от Р0(t) в точке 0), получим 
P0¢(t)= - aP0(t)

По свойству З выполняется равенство Р0(0)=1. Таким образом, получили обыкновенное дифференциальное уравнение с начальным условием, которое математически описывает свойства 1—З. Решение этого уравнения хорошо известно — P0(t)=e-at, t³0 
Для достаточно малых значений h имеем разложение в ряд Тейлора

В силу свойства 3

Р1(h)= 1 - Р0(h)»ah

Последнее равенство означает, что вероятность реализации в интервале времени длины h (h - мало) одного события (одно требование на обслуживание) прямо пропорциональна h (коэффициент пропорциональности a).

Сделаем некоторые выводы:

1. Используя результаты  п.б.1.З.; при Po(t)=е-at, получаем, что плотность вероятности f(t) того, что длина интервала времени между двумя случайными событиями равна Т, имеет экспоненциальный вид, то есть

f(T) = - Р0¢(Т) = a ехр(-aТ), (T>0).

2. Математическое  ожидание случайной величины  Т, распределенной экспоненциально  равно М{Т}=1/a (единиц времени). Тогда среднее число требований в единицу времени (интенсивность потока требований) будет равна l=a, поэтому в дальнейшем, когда будем говорить о плотности экспоненциального распределения интервалов времени между двумя последовательными требований на обслуживание с интенсивностью l будем записывать 
f(T)=l.ехр(-lТ).

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

g(T)=m exp(-m t)

где m (единиц обслуженных клиентов) — интенсивность исходного потока, которая равна m=1/М1 (М1 (единиц времени) — математическое ожидание величины интервала времени между двумя событиями). -

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

P{t>T+s 1 Рs} = P{t>T+s, t>~}IР(t)~s) = Р(t)~Т+s}/Р{t>s) =