Потоки событий. Уравнения Колмогорова

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

Основные понятия и классификация систем массового

Обслуживания

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

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

Требованием (клиентом, заявкой) в СМО называется каж­дый отдельный запрос на выполнение какой-либо работы. Обслуживание — это выполнение работы по удовлетворе­нию поступившего требования. Объект, выполняющий обслужи­вание требований, называется обслуживающим устройством (прибором) или каналом обслуживания.

Временем обслуживания называется период, в течение ко­торого удовлетворяется требование на обслуживание, т.е. пери­од от начала обслуживания и до его завершения. Период от мо­мента поступления требования в систему и до начала обслужи­вания называется временем ожидания обслуживания. Время ожидания обслуживания в совокупности с временем обслужива­ния составляет время пребывания требования в системе.

СМО классифицируются по разным признакам.

1. По числу каналов обслуживания СМО делятся на одноканальные и многоканальные.

2. В зависимости от условий ожидания требованием нача­ла обслуживания различают СМО с потерями (отказами) и СМО с ожиданием.

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

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

Для СМО с ожиданием основными характеристиками яв­ляются математические ожидания длины очереди и времени ожидания. Примером системы с ожиданием может служить процесс восстановления телевизоров в ремонтной мастерской.

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

В качестве характеристик эффективности может приме­няться вероятность отказа как в системах с потерями (или харак­теристики времени ожидания) и в системах с ожиданием.

3. По дисциплине обслуживания СМО делятся на систе­мы с приоритетом в обслуживании и на системы без приоритета в обслуживании.

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

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

5. По месту нахождения источника требований СМО де­лятся на разомкнутые (когда источник требования находится вне системы) и замкнутые (когда источник находится в самой сис­теме).

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

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

Методы и модели исследования СМО можно условно раз­бить на аналитические и статистические (имитационного моде­лирования процессов массового обслуживания).

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

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

Потоки событий. Уравнения Колмогорова

В настоящее время теоретически наиболее разработаны и удобны в практических приложениях методы решения таких за­дач массового обслуживания, в которых поток требований явля­ется простейшим (пуассоновским).

Для простейшего потока частота поступления требований в систему подчиняется закону Пуассона, то есть вероятность поступления за время t, ровно kтребований задается форму­лой:

Pk= Потоки событий. Уравнения Колмогорова - student2.ru e-λt

где λ – параметр потока (интенсивность – среднее число требований, поступивших в систему за единицу времени).

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

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

Стационарным называется поток, вероятные характеристики которого не зависят от времени. Например, математи­ческое ожидание числа требований, поступающих в систему в единицу времени, является величиной постоянной и называется интенсивностью потока. Таким образом, вероятность поступления в систему определен­ного количества требований в течение заданного промежутка времени Потоки событий. Уравнения Колмогорова - student2.ru t зависит от его величины и не зависит от начала его отсчета на оси времени.

Отсутствие последействия означает, что число требований, поступивших в систему до момента t, не определяет того, сколько требований поступит в систему за время t + Потоки событий. Уравнения Колмогорова - student2.ru t.

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

Вероятность того, что на временном интервале t = τ не поступит ни одного требования p0 определяется как:

p0 = e-λτ.

Тогда вероятность того, что на этом же временном интервале появится хотя бы одно требование определяется соотношением

p(t) = 1– p0 = 1– e-λτ.

Вероятность попадания на элементарный временной интервал, т.е. когда τ = Δt, хотя бы одного события (требования) потока, можно определить, заменив функцию e-λτ двумя первыми числами её разложения в ряд Маклорена по степеням Δt. Действительно:

p(Δt) = 1–e-λΔt ≈ λ Δt.

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

р (t<T)=F(t)=1 – е- Потоки событий. Уравнения Колмогорова - student2.ru t,

т.е. вероятность того, что время обслуживания не превосходит некоторой величины t, где μ – интенсивность потока обслуживания тре­бований в системе (среднее число требований, обслуженных в единицу времени).

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

p(Δt) = 1–et ≈ μλ Δt.

При анализе случайных процессов с дискретными состояниями пользуются графиком состояний, где прямоугольником изображаются состояния, а переходы из состояния в состояние – стрелками. У стрелок обычно проставляются значения интенсивностей λijij) перехода системы из состояния Si в состояние Sj, которые происходят под воздействием простейших потоков событий.

Рассмотрим систему, которая может находиться в двух состояниях: S0– система исправна; S1 – система находится в состоянии отказа и ремонтируется (рис. 8.1).

 
  Потоки событий. Уравнения Колмогорова - student2.ru

Рис. 8.1. Граф системы

Будем характеризовать состояние системы (S0,S1) вероятностями состояния р0 (t) и р1 (t). Очевидно, что

р0 (t) +р1 (t) = 1.

Найдем вероятность того, что система в момент (t+Δt) будет находиться в состоянии S0.

Это возможно, во-первых, в том случае, если система в момент времени t с вероятностью р0(t)находилась в состоянии S0 и за время Δtиз него не вышла. Вероятность выхода системы за время Δt из состояния S0 в состояние S1 определяется как λ· Δt. Противоположная вероятность (что система не выйдет из S0) определяется как (1 – λΔt). Вероятность того, что система, находившаяся в состоянии S0 с вероятностью р0(t), за время Δt не выйдет из него, равна по теореме умножения вероятностей

р0(t)(1 – λΔt).

Во-вторых, система в момент времени t находилась с вероятностью р1(t)в состоянии S1 и за интервал времени Δt с вероятностью μ·Δt перешла в состояние S0, т.е.

р1(t)· μΔt.

Вероятность р0(t + Δt) нахождения системы в состоянии S0 момент времени (t + Δt)по какому-либо из двух рассмотренных способов равна сумме рассмотренных вероятностей

р0(t + Δt) = р0(t) (1 – λΔt)+ р1(t) μΔt

Преобразуем соотношение к виду

Потоки событий. Уравнения Колмогорова - student2.ru

Переходя к пределу при Δt→0, получим

Потоки событий. Уравнения Колмогорова - student2.ru

По аналогии составляется уравнение, описывающее вероятность того, что система в момент (t + Δt)будет находиться в состоянии S1, но проще это найти из условия нормирования

р0 (t) +р1 (t) = 1.

С учетом этого условия система уравнений для двух состояний графа имеет вид

Потоки событий. Уравнения Колмогорова - student2.ru

Задав начальные условия, можно решить систему уравнений и найти систему функций времени рi(t), где i – номер состояния.

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

Потоки событий. Уравнения Колмогорова - student2.ru

Тогда система уравнений упрощается (стационарный режим)

Потоки событий. Уравнения Колмогорова - student2.ru

Откуда вероятности состояний установившегося процесса определяются как

Потоки событий. Уравнения Колмогорова - student2.ru Потоки событий. Уравнения Колмогорова - student2.ru

В частности, если μ=2; λ=1, то Р0=0,67; Р1=0,33. Таким образом, в среднем система будет находиться в рабочем состоянии 67%, а в состоянии ремонта 33% времени.

В общем случае система уравнений Колмогорова может быть составлена по следующему алгоритму.

1. В левой части каждого уравнения стоит производная вероятности i-го состояния.

2. В правой части каждого уравнения стоит:

2.1. Сумма произведений вероятностей всех состояний, из которых идут стрелки в i-е состояние, на интенсивности соответствующих потоков событий.

2.2. Минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность i-го состояния.

Система Колмогорова состоит из независимых уравнений и условия нормирования.

СМО с ожиданием

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

Задачи с очередями являются типичными в производствен­ных условиях, например при организации наладочных и ремон­тных работ, при многостаночном обслуживании и т.д.

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

Система состоит из nобслуживающих каналов. Каждый из них может одновременно обслуживать только одно требование. В систему поступает простейший (пуассоновский) поток требо­ваний с параметром Потоки событий. Уравнения Колмогорова - student2.ru . Если в момент поступления очередного требования в системе на обслуживании уже находится не мень­ше n требований (т.е. все каналы заняты), то это требование ста­новится в очередь и ждет начала обслуживания. Время обслуживания каждого требования tоб является слу­чайной величиной, которая подчиняется экспоненциальному закону распределения с параметром Потоки событий. Уравнения Колмогорова - student2.ru .

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

Замкнутая СМО с ожиданием

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

Такую систему можно классифицировать как многоканальную СМО (n – каналов) и ограниченной данной очереди l, причем n +l = m.

Граф состояний такой системы изображен на рис. 8.2.

Потоки событий. Уравнения Колмогорова - student2.ru

Рис. 8.2. Граф состояний многоканальной СМО с ограниченной очередью

Состояния данной системы означают:

S0 – отсутствие требований в системе;

S1 – одно требование обслуживается, очереди нет;

S2 – два требования обслуживаются, очереди нет;

…………………………………………………….

Sn– n требований обслуживаются, очереди нет;

Sn+1 – n требований обслуживаются, одно требование стоит в очереди;

…………………………………………………….

Sn+l– n требований обслуживаются, l требований стоят в очереди.

Система уравнений вероятностей состояний в стационарном режиме для цепочки S0 – Sn будет:

Потоки событий. Уравнения Колмогорова - student2.ru

Для цепочки состояний Sn+1 – Sn+lсистема уравнений стационарного режима будет:

Потоки событий. Уравнения Колмогорова - student2.ru

В качестве основных критериев, характеризующих качество функционирования рассматриваемой системы, выберем: 1) от­ношение средней длины очереди к наибольшему числу требова­ний, находящихся одновременно в обслуживающей системе – коэффициент простоя обслуживаемого объекта; 2) отношение среднего числа незанятых обслуживающих каналов к их общему числу – коэффициент простоя обслуживаемого канала.

Рассмотрим расчет необходимых вероятностных характе­ристик (показателей качества функционирования) замкнутой СМО.

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

PkkP0, (1 Потоки событий. Уравнения Колмогорова - student2.ru k Потоки событий. Уравнения Колмогорова - student2.ru n),

где αk= Потоки событий. Уравнения Колмогорова - student2.ru или αk= Потоки событий. Уравнения Колмогорова - student2.ru ;

Потоки событий. Уравнения Колмогорова - student2.ru ;

Потоки событий. Уравнения Колмогорова - student2.ru – интенсивность поступления требований в си­стему от одного источника;

Потоки событий. Уравнения Колмогорова - student2.ru об – средняя продолжительность обслуживания одного требования;

т – наибольшее возможное число требований, находящих­ся в обслуживающей системе одновременно (m=n+l);

п– число обслуживающих аппаратов;

Р0 – вероятность того, что все обслуживающие аппараты свободны.

2. Вероятность того, что в системе находится k требований при условии, когда их число больше числа обслуживающих ап­паратов:

Pk= Потоки событий. Уравнения Колмогорова - student2.ru kP0, (n Потоки событий. Уравнения Колмогорова - student2.ru k Потоки событий. Уравнения Колмогорова - student2.ru m),

где Потоки событий. Уравнения Колмогорова - student2.ru k= Потоки событий. Уравнения Колмогорова - student2.ru ( Потоки событий. Уравнения Колмогорова - student2.ru Потоки событий. Уравнения Колмогорова - student2.ru об)k или αk= Потоки событий. Уравнения Колмогорова - student2.ru .

3. Вероятность того, что все обслуживающие аппараты сво­бодны, определяется из условия

Потоки событий. Уравнения Колмогорова - student2.ru

4. Среднее число требований, ожидающих начала обслужи­вания (средняя длина очереди):

Потоки событий. Уравнения Колмогорова - student2.ru .

5. Коэффициент простоя требования в ожидании обслужи­вания:

a1= Потоки событий. Уравнения Колмогорова - student2.ru .

6. Вероятность того, что все обслуживающие аппараты заняты:

Pотк= Потоки событий. Уравнения Колмогорова - student2.ru .

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

A2= Потоки событий. Уравнения Колмогорова - student2.ru = Потоки событий. Уравнения Колмогорова - student2.ru .

8. Коэффициент полного простоя требований на обслуживании и в ожидании обслуживания:

a2= Потоки событий. Уравнения Колмогорова - student2.ru .

9. Среднее время простоя требования в очереди на обслуживание:

Tож=a1/ Потоки событий. Уравнения Колмогорова - student2.ru .

10. Среднее число свободных обслуживающих аппаратов:

A3= Потоки событий. Уравнения Колмогорова - student2.ru .

11 . Коэффициент простоя обслуживающих аппаратов:

a3 = Потоки событий. Уравнения Колмогорова - student2.ru .

12. Вероятность того, что число требований, ожидаю­щих обслуживания, больше некоторого числа В (вероятность того, что в очереди на обслуживание находится более В тре­бований):

P-B = Потоки событий. Уравнения Колмогорова - student2.ru = Потоки событий. Уравнения Колмогорова - student2.ru .

Рассмотрим пример расчета характеристик замкнутой СМО.

Пример 8.1. Оптовый склад строительных материалов обслу­живает шесть предприятий-потребителей материалов. Каждый из потребителей направляет на склад автомашину за мате­риалами в среднем один раз в смену (продолжительность сме­ны 8 ч). На складе имеется один автопогрузчик, который исполь­зуется только для погрузки материалов на прибывающие авто­машины. Прибывшая на склад автомашина становится в оче­редь, если автопогрузчик занят погрузкой другой автомашины. Обработка статистических данных о продолжительности погруз­ки одной автомашины и проверка соответствующей гипотезы по­казали, что продолжительность погрузки одной автомашины подчиняется показательному закону распределения и составля­ет в среднем 48 мин (0,1 смены). Статистическое исследование потока автомашин показа­ло, что число автомашин, поступающих на склад в единицу вре­мени, подчиняется пуассоновскому закону распределения. Требуется провести расчет характеристик функционирова­ния приведенной производственной системы как СМО.

Решение. Рассчитаем основные параметры системы для условий задачи.

Вероятность того, что все обслуживающие ап­параты свободны (на складе нет автомашин) определяется как P0, λ=1, μ=0,1.

Вероятность того, что на складе одна автомашина:

P1= Потоки событий. Уравнения Колмогорова - student2.ru 0,1P0=0,6P0,

а вероятность того, что на складе две автомашины (одна под погрузкой, а другая в очереди):

P2= Потоки событий. Уравнения Колмогорова - student2.ru 0,12P0=0,3P0.

Рассчитывая аналогично, получим: Р3=0,12Р0; Р4=0,036Р05= 0,0072Р0; Р6= 0,0007Р0. Так как сумма вероятнос­тей нахождения системы в любом из состояний равна 1, т.е.

Потоки событий. Уравнения Колмогорова - student2.ru =1,

то P0(1 + 0,6 + 0,3 + 0,12 + 0,036 + 0,0072 + 0,0007) = 2,0639; Р0 = 1.

Отсюда находим Р0 = 0,4845.

Дальнейшие расчеты затруднений не вызывают. Напри­мер, средняя длина очереди равна

А1 =(2 - 1)Р2 + (3 - 1)Р3 + (4 - 1)Р4 + (5 - 1)Р5 + (6 - 1) Р6; А = 0,3296.

Наши рекомендации