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

User Rating: 2 / 5

Star ActiveStar ActiveStar InactiveStar InactiveStar Inactive
 

Курсовая работа
на тему :
«Теория массового обслуживания».

 

Содержание:
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. Среднее число поступающих заявок (требований на обслуживание) в единицу времени будем обозначать  (интенсивность поступления требований).

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

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

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

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

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

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

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

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

= 1/М(Т).

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

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

 

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 и обозначив через  величину Р0(t) (производная от Р0(t) в точке 0), получим
P0(t)= - P0(t)

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

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

Р1(h)= 1 - Р0(h)h

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

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

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

f(T) = - Р0(Т) =  ехр(-Т), (T>0).

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

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

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

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

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

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

= exp(—a.(T+s))Iexp(--a.s) exp(—wT) = Р {t>T}.

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

 

2.2. Входной поток

 

В предыдущем пункте был рассмотрен случайный процесс с <чистыми поступлением требований, для которого характерно, что поступившее в систему требование присоединяется к очереди и не покидает ее до тех пор, пока не будет обслужено. Такие процессы называют процессами чистого рожде¬ния. Найдем аналитические представления Р~(t) для процесса чистого рожде¬ния с экспоненциальным распределением вероятностей интервалов времени между двумя последовательными поступлениями требований на обслужива¬ние.

Для сколь угодно малого, но не равного нулю интервала h при n>0, имеем

n поступлений в течение t единиц времени и ни
одного поступления в интервале h
Рn(t+h) = или
n-1 поступление в течение t единиц времени и
одно поступление в интервале h.

Применяя теоремы сложения и умножения вероятностей, получаем Рn(t+h) = Рn(t).Ро(h) + Рn-1(t)*Р1(h), n=1,2,...

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

Так как Р0(h) = ехр(-*h), Р1(h) = 1- Р0(h)=1 - ехр(-*h), то для малых значений h можно написать приближенные равенства
• Р0(h)= 1 –*h, Р1(h)=*h,
Р0(t+h)= Р0(t)*(1-*h).
Последние равенства перепишем в следующем виде:
[Рn(t+h)- Рn(t)]/h=- *Рn(t) + *Pn-1(t)
• [Р0(t+h)- Po(t)]/h=- *Ро(t)
При h0 эти равенства становятся точными и переходят в разностно--дифференциальные уравнения
Pn(t)=-  *Pn(t)+ *Pn-1(t),n>0,
Р0 (t)==- *P0(t).
Решение последнего уравнения нам известно Po(t) = ехр(- *t). В теории разностно-дифференциальных уравнений с постоянными коэффициентами хорошо изучены полученные уравнения (n>О). Их решениями являются сле-дующие функции
Pn(t)=[( *t)n* exp(- *t)]/n,n=1,2...
Убедиться в справедливости написанных представлений функций Рn(t) можно непосредственной подстановкой их в соответствующие уравнения.
В теории вероятностей распределение вероятностей Рn(t) известно как распределение Пуассона. Среднее значение (математическое ожидание) этого распределения равно *t.
Итак, если временные интервалы между моментами двух последовательных событий распределены по экспоненциальному закону с интенсивностью, то число поступлений требований на обслуживание в интервале времени t единиц времени характеризуется пуассоновским распределением со средним значением равным *t.
Пример 6.1. Найти математическое ожидание и дисперсию для распреде-ления вероятностей (Пуассона)
Рn(t)=[( *t)n*ехр(-*t)]/n!, n=0,1,2,...
Решение. В начале заметим, что справедливы два равенства
M[t] =п*Pn(t)= (n-1)*( *t)n-1 *ехр(*t)/(n-1)! = *t
и (*t)n-1*exp(-*t)/(п-1)! = ехр(-*t)*ехр(*t) = 1.
Чтобы установить справедливость этих равенств, достаточно вспомнить разложение функции ехр(*t) в ряд Тейлора-Маклорена

ехр(*t)=1 + (*t)/1! + (*t)2/2! + ...+ (*t)n/n! +....
Первое приведенное равенство — математическое ожидание распределе¬ния Пуассона. Найдем дисперсию D[t]. Известно, что величину дисперсии можно найти по формуле
D[tI=а2—М2[t],
где а2 — второй начальный момент. Найдем а2.

а2 =n2(*t)*ехр(-*t)/n! = (*t )n(*t)n-1ехр(-*t)/(n-1)! =(*t)[(n-1)+1]* (*t)n-1*exp(-*t)/(n-1)!=
=( *t)*[(n-1)*( *t)n-1*exp(*t)/(n-1)!+( *t)n-1 *exp(*t)/(n-1)!]
Первая сумма в квадратных скобках равна *t, а вторая — равна 1, поэтому D[t]= (*t)2+(*t)-( *t)2=(*t).

Следслвие. Дисперсия дискретной случайной величины, распределенной по закону Пуассона, равна математическому ожиданию этой величины, то есть D[t] = M[t] =(*t). Отметим, что это уникальное свойство распределения Пуассона. Ни одно другое дискретное распределение случайной величины не обладает этим свойством. для предварительного суждения о том, является ли данное распределение пуассоновским, по эмпирическим данным достаточно
вычислить математическое ожидание и дисперсию. Если с удовлетворитель¬ной точностью математическое ожидание и дисперсия при этом совпадают, то можно быть уверенным в том, что оно пуассоновское.

 

2.3. Выходные потоки

 

Процесс на выходе системы массового обслуживания рассматривают в предположении, что система начинает функционировать при наличии ,в ней N клиентов, которые после обслуживания выбывают из системы с интенсив-ностью  (экспоненциальное распределение интервалов времени). Процессы такого рода называют процессами "чистой"гибели.
К категории процессов "чистой" гибели относится, например, изъятие из склада хранимых в нем запасов. В этом случае предполагается, что на складе имеется N единиц запасов, которые изымаются с интенсивностью  (единиц запасов в единицу времени).
При условии абсолютной случайности исходов для малого интервала h можно записать (так же как и в случае <чистого~ рождения)
Q0(h) = exp(-*h)=1-*h, Q1(h) = 1 - Q0(h)- *h=1-*h для величин Qn(t+h) имеют место следующие соотношения:
Qn(t+h)=Qn(t)*1 + Qn-1(t)( *h),
Qn(t+h)= Qn(t)(1-*h) + Qn-1(t)*( *h), n = N-1, N—2,. ..,1,
Qo(t+h)= Q0(t)*(1- *h).
Написанные приближенные равенства можно переписать в следующемвиде:

[QN(t+h)-QN(t)]/h=*QN-1(t),
[Qn(t+h) –Qn(t)]/h=-*Qn-1(t), n=N-l, N-2,...,1,
[Qo(t+h)- Qo(t)]/h =-*Qo(t).
Перейдя к пределу при h0, получаем систему разностно-дифференциальных уравнений
QN(t)= *QN-1(t),
Qn(t) =-*Qn(t)+ *Qn-1(t), n=N-1,N-2,...,1,
Q0(t) =-*Qo(t).
Второе и третье разностно-дифференциальные уравнения имеют единст-венные решения
Qn(t)=[ (*t)n*exp(-*t)]/n!, n=0,1,2,..,N-1
Решение первого уравнения задается формулой
QN(t)=1-Qn(t).
Чтобы убедиться, что написанные формулы действительно являются ре-шениями приведенных разностно-дифференциальных уравнений, достаточно продифференцировать их и подставить в соответствующее уравнение.

Напомним, что Qn(t) — это вероятность n единиц выбывания в течение t единиц времени. Часто интерес представляет вероятность того, что по исте-чении t единиц времени в системе остается n заявок на обслуживание (n кли-ентов). Обозначим эту вероятность Rn(t). Тогда, если предположить, что в начальный момент времени число находящихся в системе клиентов (заявок на обслуживание) равнялось N, то будем иметь
Rn(t) =QN-n(t)
Откуда следует, что

Rn(t) = [(*t)N-n*exp(-*t)]/(N-n)!, n = 1,2,..,N.
Ro(t) = 1 Rn(t).

Пример. В начале каждой недели складируется 15 единиц запасов, ко¬торые в течение недели расходуются. Изъятия запасов из складского поме¬щёния происходят лишь в первые шесть дней каждой недели и осуществляется в соответствии с пуассоновским распределением со средней интенсив¬ностью = 3 (единиц запасов в 1 рабочий день). Как только уровень запасов снижается до пяти единиц, делается новый заказ на поставку в конце недели пятнадцати единиц запасов. Запасы по своей природе таковы, что все неис¬пользованные до конца недели предыдущие запасы приходят в негодность исписываются (ликвидируются).

Исследование ситуации. Учтем, что средняя интенсивность потребления =3 (единиц в 1 день).
Вычислим вероятность того, что уровень запасов понизится до пяти еди¬ниц в t-й день. Вероятность такого события вычисляется по формуле
R5(t)= [(3t)15-5*ехр(-3t)]/(15—5)! = [(3t)10*exp(-3t)]/10! t=1,2,...,6.
Результаты для определенных значений t сведены в таблицу

t(дни) 1 2 3 4 5 6
m*t 3 6 9 12 15 18
R5(t) 0.0008 0.0413 0.1186 0.1048 0.0486 0.0150

По условиям примера R5(t) есть вероятность возникновения необходимо¬сти формирования в t-й день нового заказа на пополнение склада пятнадца¬тью единицами запасов. Эта' вероятность достигает наибольшего значения при t =3, а затем постепенно падает по мере возрастания t (от t=4 до t=6).

Если нужно знать вероятность, с которой новый заказ на накопление за-пасов придется оформлять не позднее чем в t-й день, то нужно вычислить ве-роятность того, что в t-й день уровень запасов окажется равным или будет меньше пяти единиц. В этом случае имеем

Rn<=5(t) = R0(t) + R1(t) +.. + R5(t)=1-[R1(t)+R2(t)+..+R15(t)]+R1(t)+..+R5(t)=1-[R6(t)+R7(t)+..+R15(t)]=
=1-15n=6(3t)15-n*exp(-3t)/(15-n)!.

Вычисления, проведенные по последней формуле, сведены в таблицу

t(дни) 1 2 3 4 5 6
m*t 3 6 9 12 15 18
Rn<=5(t) 0.0012 0.0839 0.4126 0.7576 0.9303 0.9847

Из таблицы видно, что вероятность возникновения необходимости делать новый заказ в t-й день монотонно возрастает.
В рассматриваемой ситуации необходимо также вычислить среднее число единиц запасов, которые будут по негодности ликвидироваться в конце неде¬ли. Это можно сделать, если вычислить математическое ожидание числа ос-тавшихся не Изъятыми из склада единиц запасов в конце шестого дня:

М{n | t=h} = n*Rn(6) = 0.5537 (единиц).

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

 

2.4. Верификация пуассоновского закона распределения при анали¬зе реальных систем.

 

Очень• важно иметь практически осуществимый алгоритм проверки гипо-тезы о том. Что входной или выходной поток действительно является пуас-соновским. Самыми простыми способами установления этого факта являют¬ся следующие:

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

 

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

3.1. Типы структур систем массового обслуживания.

 

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

8877878
Заметим, что в любой произвольный момент времени всех находящихся клиентов можно разбить на тех. Кто находится в очереди (ждёт когда его начнут обслуживать) и тех, кто уже обслуживается.
В настоящее время для характеристики любой системы массового обслу-живания приняты стандартные обозначения. восходящие к Д.Г. Кендаллу(1953 г). Они имеют следующую структуру:
(а / b / с): (d / е / f ),
где символы а, b, c, d, e, f характеризуют некоторые существенные элементы модельного представления процессов массового обслуживания.

а — тип распределения моментов поступлений заявок на обслуживание;

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

с — число параллельно функционирующих узлов обслуживания(с=1,2,...,);

d — дисциплина очереди;

е — максимальное число допускаемых в систему требований (Число требо-ваний в очереди + число требований, принятых на обслуживание);

f— емкость источника, генерирующего заявки на обслуживание.

для конкретизации а и Ь приняты следующие стандартныё обозначения:

М — пуассоновское распределение моментов поступлений заявок на об-служивание или выбывания из системы, обслуженных клиентов (или экспо-ненциальное распределение интервалов времени между моментами последо-вательных поступлений требований или Продолжительностей обслуживания клиентов);

D — фиксированный (детерминированный) интервал времени обслужива-ния одного клиента.

Например, структура (М /D/10): (GD/N/) означает, что речь идет о системе массового обслуживания с пуассоновским входным потоком, фикси¬рованным временем обслуживания и десятью параллельно функционирующими узлами обслуживания. дисциплина очереди не регламентирована Что подчеркивается парой символов GD. Кроме того, независимо от того, сколь¬ко требований поступает на вход обслуживающей системы, данная система(очередь + обслуживаемые клиенту) не может вместить более N требований(клиентов), то есть клиенты, не попавшие в блок ожидания, вынуждены об¬служиваться в другом месте. Наконец, источник, порождающий заявки на обслуживание, имеет неограниченную емкость.

Напомним, что под дисциплиной очереди понимаются три возможные принципа, заложенные в порядок обслуживания очереди:
— «первым пришел — первым обслужен (собственно очёредь);

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

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

— выбор заявок из очереди в соответствии с некоторым приорите-том.

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

 

3.2. Операционные характеристики систем массового
обслуживания

 

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

pn — вероятность того, что в системе находятся n клиентов (заявок на об-служивание);

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

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

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

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

По определению
Ls=n*pn, Lq=(n-c)*pn.

Между Ls и Ws (между Lq и Wq) существует строгая зависимость. В част-ности, если частота поступлений заявок в систему равняется , то мы имеем
Ls= *Ws,Lq=*Wq
В случае, когда не все заявки имеют возможность попасть в обслужи-вающую систему (из-за небольшой вместимости блока ожидания), приведен¬ные соотношения надо видоизменить путем введения нового значения пара¬метра эфф, которое позволило бы учесть только действительно попавшие в систему требования. Определим это значение следующим образом

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

Ls=эфф*Ws, Lq=эфф*Wq.
В общем случае
эфф=*,0<<1.

Это означает, что только часть поступающих требований на обслужива¬ние действительно попадают в систему.
Если средняя скорость обслуживания равняется  в час, следовательно, средняя продолжительность обслуживания равняется 1/ и тогда справедли¬во соотношение.
Ws=Wq+ 1/.

Умножая левую и правую части этого неравенства на , получаем
Ls = Lq + / .
Последнее равенство остается справедливым и в случае замены  на эфф. При этом будет
Ls=Lq+ эфф/,или эфф=(Ls-Lq).

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

pnLs=n*pnWs=Ls/Wq=Ws-1/Lq=*Wq

 

3.3. Модель (M/ M/ 1): (GD//).

 

В этой модели имеется единственный узел обслуживания, а на вмести¬мость блока ожидания и емкость источника требований никаких ограничений не накладывается. Входной и выходной потоки являются пуассоновскими с параметрами  и  соответственно.
Сначала выведем уравнения для Pn(t) — вероятностей того, что в интервале времени t в системе находится n требований (клиентов). Выберем достаточно малое значение h>0. Тогда вероятность Pn(t+h) (вероятность поступления в
систему n>О требований в интервале (t+ h) складывается из следующих веро-ятностей:

1. В конце временного интервала t в системе находится n тре-бований, а в интервале h не происходит ни поступлений, ни выбы-вании.

2. В конце временного интервала t в системе находится (n-1) требований, а в интервале h происходит одно поступление, но не происходит ни одного выбывания.

3. В конце временного интервала t в системе находится (n+1) требований, а в интервале h не происходит ни одного поступления, но происходит одно выбывание.

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

Рn(t+h) =Рn(t)*(1-(*h))(1-(*h)) + Рn-1(t)(*h)( 1-(*h)) +Pn-1(t)*(1-(*h))(*h),n>0.

В последнем равенстве мы воспользовались тем, что при малых h>0 име¬ют место следующие представления вероятностей:
(1-*h ) — вероятность того, что в интервале h нет ни одного поступле¬ния;
(1-*h)  вероятность того, что в интервале h нет ни одного выбыва¬ния;

(*h) — вероятность того, что в интервале h только одно поступление;
(*h) — вероятность того, что в интервале h только одно выбывание. для n=0 вероятность того, что в интервале h не произойдет ни одного вы¬бывания, очевидно, равна единице.
Следовательно, Р0(t+h)=Р0(t)*(1-(*h) ) + Р1(t)*( *h)( 1-(*h)) группировав соответствующим образом члены написанных приближен¬ных равенств, разделив их на h и перейдя к пределу при h0, получим сле¬дующие дифференциально-разностные уравнения

Pn = *Pn-1(t) +*Рn+1(t) - (+)*Рn(t), n>0,

Po(t) = -*Р0(t) +*Р1(t), n=0.

В принципе написанная система разностно-дифференциальных уравнений разрешима, и поэтому она задает некоторый стохастический процесс (Pn(t)), который не обязательно стационарен. Однако, решения этой системы, выпи-санные в явном виде, весьма громоздки.
Можно доказать, что при < существует стационарный процесс, то есть при t существует решение полученной системы разностно¬-дифференциальных уравнений, не зависящее от t. В этом случае, очевидно, будут иметь место предельные переходы

Pn'(t)0, Pn(t)  pn ,t).
Осуществив предельный переход при t  в системе разностно¬-дифференциальных уравнений, приходим к равенствам
-*p0+*p1=0,n=0,
*pn-1+*pn+1-(+)*pn=0,n>0.

В математике полученные уравнения называются разностными. для раз-ностных уравнений с постоянными коэффициентами полностью разработана теория и известны способы представления их решений. Для нашего разност-ного уравнения решения таковы Pn=(1-)*n,n=0,1,2,.., где через  обозначена величина =/<1. Чтобы убедиться в справедливо¬сти представления решения, достаточно подставит его в разностное уравне¬ние.
Полученное распределение вероятностей pn=(1-)*n в теории вероят¬ностей называется геометрическим распределением.
Выражение для Ls получается путем элементарных преобразований:
Ls=n*pn=n*(1-)*n=(1-)**d/d*(1/(1-))=/(1-).
Заметим, что ряд n сходится как сумма бесконечной убывающей геометрической прогрессии со знаменателем <1 .
Используя выведенные ранее формулы, получаем Ls=М= *(1-), Lq =Ls-/=2/(1-),

Ws=Ls/=1/[(1-)], Wq=/[(1-)].

 

3.4. Модель (М/ М/ 1): (GD/N/)

 

Разница между моделью (М/М/1):(GD/N/) и уже рассмотренной мо¬делью (М/М/1):(GD//) заключается в том, что максимальное число требований, допускаемых в блок ожидания, равняется N (то есть максимальна длина очереди есть N-1). В результате эффективная частота эфф поступ¬лений требований становится меньше частоты  с которой заявки на обслу¬живание генерируются соответствующим источником.
Разностно-дифференциальные уравнения для n=0 и для 0N имеем Рn(t) =0, а для n = N можно написать

PN(t + h)=PN(t)*1*(1-*h) +PN-1(t)*(*h)*(1-(*h)).

Таким образом, для установившегося процесса в модели (М/М/1):(GD//) разностные уравнения имеют вид

-*p0+p1=0,-pn+*pN-1=0,
-(1+)*pn+pn+1+*pn-1=0,0<n<n.
Решение этого разностного уравнения имёет вид:

Следует отметить, что значение параметра =/ не обязательно меньше единицы, как это требовалось в модели (М/ М/ 1): (GD//). Это следует из того, что число допускаемых в систему требований контролируется путем введения ограничения на длину очереди (которая не может превышать N-1),

а не соотношением между интенсивностями входного и выходного потоков есть не отношением /.
С учетом формул для pn находим

Выражения для Lq, Ws, Wq можно получить из формулы для Ls если предварительно вывести формулу эфф. Поскольку вероятность того, что требование не имеет возможности присоединиться к очереди, равна рn(то есть вероятность того, что в системе уже находится N требований) доля тре¬бований, которым разрешено войти в блок ожидания, равняется

P{n<n}= 1-Рn.<br="">Отсюда следует, что

эфф=*(1-pN),
Wq=Lq/эфф =Lq/[*(1 —pN)],
Ls= Lq + эфф / = Lq +*(1-pN)/,
Ws=Wq+ 1/ =Ls/[*(1-pN)].

Таким образом, еще раз убедились, что

эфф = *(Ls-Lq) = *(1-pN).

 

Литература:

1. В.А.Онегов «Исследование операций».
2. Х.Хата «Введение в исследование операций» (том 2).
3. Е.С.Вентцель «Теория вероятностей».

buy a home you can afford

Недавно добавили