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

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

Простейшим примером замкнутой СМО может служить работа дежурного электромонтера на объекте, имеющем п электроустановок.

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

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

Схема возможных состояний такой системы показана на рис. 1.13.

Рис. 1.13.

Система может иметь следующие состояния:

s 0 - все электроустановки исправны и электромонтер не занят их обслуживанием;

Sj - электромонтер обслуживает одну электроустановку, остальные электроустановки работают;

s 2 - две электроустановки неисправны, одна ремонтируется, вторая находится в очереди;

s k - к электроустановок неисправны, одна ремонтируется, к - 1 стоят в очереди;

s n - п электроустановок неисправны, одна ремонтируется, п - 1 ожидают ремонта.

Стрелки на схеме показывают переходы из одного состояния в другое с интенсивностями X и р.

При переходе системы из состояния s 0 в состояние Sj интенсивность потока неисправностей равна пХ (поток неисправностей всех работающих электроустановок).

При переходе системы из состояния Sj в состояние s 2 интенсивность потока неисправностей уже определяется п - 1 работающими электроустановками (одно изделие находится в ремонте) и т. д.

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

Такие СМО исследовал К. Пальм, который вывел и получил удобные и простые уравнения для определения вероятностей состояния системы:

Пример 1.15. Дежурный электромонтер на птицефабрике обслуживает 3 объекта. На каждом из объектов в сутки возникает по две неисправности. Процесс устранения неисправности занимает у электромонтера 1 ч. Необходимо рассчитать вероятности состояний, вероятность занятости электромонтера, абсолютную пропускную способность системы.

Все СМО, изученные в предыдущих разделах, обладали об­щим свойством - входящий поток заявок П вх и его интенсив­ность не зависели от состояний системы. Источник поступаю­щих заявок находился вне системы; Рассмотрим СМО, в кото­рых интенсивность потока поступающих заявок зависит от со­стояния системы. Такие СМО называют замкнутыми или сис­темами Энгсета по имени Т. Энгсета, который впервые дал их полный анализ.

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

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

где μ - интенсивность простейшего потока обслуживании.

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

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

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

Занумеруем состояния СМО по числу источников, находя­щихся в пассивном состоянии, т.е. по числу заявок, находя­щихся в очереди и под обслуживанием:

s 0 - все i источников находятся в активном состоянии,

канал свободен, очереди нет;

S 1 - один источник находится в пассивном состоянии, ка­нал обслуживает поданную этим источником заявку, очереди нет;

S 2 - два источника находятся в пассивном состоянии, за­явка, поданная одним из них, обслуживается, а заяв­ка, поданная другим источником, стоит в очереди;

S i - все i источников находятся в пассивном состоянии, заявка, поданная одним из них, обслуживается, а i-1 заявок, поданных остальными источниками, стоят в очереди.

Граф состояний приведен на рис. 10.1.

Из состояния s 0 в состояние S 1 систему переводит суммар­ный поток, слагающийся из потоков всех i активных источни­ков; поэтому интенсивность этого суммарного потока λ 01 = iλ . Из состояния S 1 в состояниеS 2 система переходит под воздей­ствием суммарного потока ужеi-1 потоков активных источни­ков, поскольку один источник находится в пассивном состоя­нии; следовательно, λ 12 = (i-1)λ и т.д. Из состоянияS i -1 в со­стояние Si систему переводит только один поток, порождаемый единственным источником, находящимся в активном состоя­нии (все остальные i-1 источников в пассивном состоянии);поэтому λ i -1 , I =λ. Таким образом, мы нашли все плотности вероятностей переходов системы по стрелкам слева направо. Интенсивности же потоков, переводящих СМО по стрелкам справа налево, все одинаковы и равны μ, поскольку все время работает один канал с интенсивностью обслуживания μ. Таким образом, λ k , k -1 =μ, k=1,…,i.

Как видно из структуры графа состояний данной СМО (рис. 10.1), в ней протекает процесс гибели и размножения. Тогда для определения предельных вероятностей состояний воспользуемся формулами (3.19) - (3.21) общего процесса гибе­ли и размножения. Подставим в формулу (3.21) , λ k -1, k =(I-(k-1))λ; , λ k , k -1 =μ;k=1,…,i;n=i. Получим:

где р = λ/μ - показатель нагрузки системы, порождаемой каж­дым источником заявок.

Подставив эти значения α k ,k = 1, ..., i, в формулы (3.19) и (3.20) прип = i , найдем вероятности состояний:

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

Р зан = 1 – р 0

где p 0 - вероятность того, что канал свободен. Так кик произ­водительность канала - μ заявок в единицу времени, то абсо­лютная пропускная способность СМО

А = р зан μ = (1 – р 0) μ

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

ν= А = (1 – р 0) μ.

Так как каждая заявка рано или поздно будет обслужена каналом, то относительная пропускная способность СМО равна единице Q= 1.

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

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

(10.1)

Поскольку все эти заявки обслуживаются каналом, то

Формула (10.2) показывает, что средняя интенсивность входящего потока равна интенсивности ν выходящего потока.

Из формулы (10.2):

(10.3)

Среднее число источников в пассивном состоянии можно вычислить и без использования абсолютной пропускной способности, а именно как математическое ожидание случайной величины N пас, представляющей собой число источников в пассивном состоянии:

(10.4)

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

λ (к) = (i–k)λ;k= 0, 1, …,i– 1,i, представляющие собой интенсивности входящего потока заявок, когда система находится в состоянииS k . Закон распределения случайной величины λ имеет вид:

Поэтому математическое ожидание этой случайной величины

Так как = 1, то

(10.6)

Из формулы (10.4):

(10.7)

Подставив равенства (10.6) и (10.7) в равенство (10.5) и использовав формулу (10.1), получим:

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

Тогда среднее число
заявок, находящихся под обслуживанием,

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

Среднее число
заявок в очереди получим как разность между средним числом
заявок в системе (10.3) и средним числом заявок под обслуживанием
(10.8):

Полезной характеристикой системы Энгсета является веро­ятность р акт того, что произвольный источник находится в ак­тивном состоянии. Поскольку источник в активном состоянии готов подать заявку, то p акт называют стационарным коэффици­ентом готовности. Вероятность р акт также можно назвать (стационарным) коэффициентом активности. Выведем для этого коэффициента формулу.

Если СМО находится в состоянии s к (к = О, 1, ...,i), тоk ис­точников находятся в пассивном состоянии, а (i-К) источни­ков - в активном. Поэтому условная вероятность того, что произвольно выбранный источник находится в активном со­стоянии, при условии, что СМО пребывает в состоянии s k равна (i-k)/i. Так как события, состоящие в том, что СМО на­ходится в состоянияхs k , k = О, 1, ..., i, (с вероятностьюр k ) - несовместны и образуют полную группу, то для вычисленияp акт можно воспользоваться формулой полной вероятности 1:

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

(10.4), (10.З), (10.2):

____________________________________

Формула полной вероятности дает возможность вычислить вероятность р(Е) события Е, которое может наступить лишь при условии наступления одного из несовместных событий Но, Н 1 ,..., Н i , образующих полную группу. По этой формуле р(Е) равна сумме произведений вероятностей p(Н к), k = О, 1, ..., i, каждого из событий Н к, k = О, 1, ..., i, на соответствующую условную вероят­ность р(Е\Н k ) события Е:

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

Найдем среднее время
ожидания заявки в очереди. Пусть в какой-то момент времениt поступила заявка (один из источников, находящихся в активном состоянии, перешел в пассивное состояние). Какова вероятность того, что в этот момент СМО находилась в состоянии s k (k = О, 1, ..., i-1)? Подчеркнем, что k не может равняться i, поскольку при k =i СМО пребывает в состоянии s i , в котором все i источников пас­сивны, и потому ни один из них не может подать заявки. Для замкнутых систем входящий поток заявок в силу своей зависимо­сти от состояний СМО не является пуассоновским, и именно по­этому вероятности отличаются от вероятностей р k .

Для нахождения вероятностей рассмотрим событие Е, состоящее в том, что на элементарном участке времени (t, t+dt) появилась заявка. Событие Е может произойти при условии появления одной из i несовместных гипотез, образующих пол­ную группу:

Но - в момент поступления заявки СМО находилась в состоянии So;

Н 1 - в момент поступления заявки СМО находилась в состоянии s 1 ;

-в момент поступления заявки СМО находилась в состоянии s k ;

- в момент поступления заявки СМО находиласьв состоянии s i -1 .

Вероятности р(Но), р(Н 1 ), ..., p (H k ), ..., p (H i -1 ) этих гипотез до наступления события Е равны соответственно p 0 , p 1 , ..., р k , ..., P i -1 .

Условные вероятности р(Е\Н k ), k = О, 1, ..., i-1, события Е при гипотезах Н к равны

p(Е\Н к) = (i – k)λdt, k = 0, 1, …, i – 1.

Вероятности , представляющие собой условные вероят­ности p (Hk \ E ) гипотез Н к при условии, что событие Е уже на­ступило, найдем по формулам Бейеса 1 (см., например, (9), с. 56):

Используя нормировочное условие
и формулу (10.4), получим:

(10.9)

Рассмотрим случайную величину Т ОЧ - время ожидания за­явки в очереди.

Если заявка поступает в систему при гипотезе Н 0 , т.е. когда СМО находится в состоянии s 0 то свободный канал немедлен­но принимает ее к обслуживанию, и ей не приходится стоять в очереди. Значит, условное математическое ожидание М]Т ОЧ |Н 0 ] случайной величины Т оч при гипотезе Но равно нулю: М]Т ОЧ |Н 0 ] = 0.

Заявка, поступившая в систему при гипотезе Н 1 , т.е. когда СМО находилась в состоянии s 1 , в котором канал занят и в очереди нет заявок, становится в очередь и ожидает в среднем время, равное среднему времени обслуживания каналом одной заявки
= 1/μ. ПоэтомуМ\Т ОЧ \ Н 1 ] = 1/μ.

Если заявка пришла в СМО при гипотезе Н 2 , т.е. когда сис­тема находилась в состоянии s 2 , в котором канал был занят и в

________________________________

1 Бейес Томас (1702 - 7.4.1761) - английский математик, член Лондонского королевского общества (1742). Основные труды относятся к теории вероятно­стей; в частности, Бейес поставил и решил одну из основных задач теории ве­роятностей (теорема Бейеса, опубл. 1763).

очереди стояла одна заявка, то пришедшей заявке надо будет ожидать в очереди среднее время 2/μ по 1/μ на заявку под об­служиванием и на заявку в очереди. Следовательно, М[Т ОЧ \Н 2 ] = 2/μ. И так далее. Наконец,M [ T оч \ Hi -1 ] = (i-1)/μ. Следовательно, по формуле полного математического ожида­ния (см., например, , с. 77) среднее время ожидания заявки в очереди

или, подставив сюда выражение по формулам (10.9), получим:

(10.10)

Покажем, что и в случае замкнутых систем имеет место формула:

(10.11)

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

Заменяя в формуле (10.10) μ через λ/р, вероятности p k - их выражениями через р ир 0 и применяя формулу (10.2), будем иметь:

В каждой из сумм в правой части этого равенства сделаем замену индекса суммирования

k + 1 =j , а затемj заменим наk :

Используя формулы для р к:

Отсюда, применяя формулу (10.4), нормировочное условие
и формулу (10.8), приходим к требуемой формуле (10.11):

Для среднего времени обслуживания одной заявки также справедлива формула, аналогичная формуле (10.11). В самом деле, применяя формулы (10.8) и (10.2), получим:

(10.12)

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

Так как среднее время пребывания заявки в системе
складывается из среднего времени ожидания заявки в очереди
и среднего времени ее обслуживания
, то из формул (10.11) и (10.12) получаем:

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

Параметры и характеристики функционирования замкнутой одноканальной СМО представлены в табл. 10.1 и 10.2.

3. Замкнутые СМО

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

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

Пусть n - число каналов обслуживания, s - число потенциальных заявок, n

Вероятность простоя системы определяется формулой

Р 0 = .

Финальные вероятности состояний системы:

P k = при k

Через эти вероятности выражается среднее число занятых каналов

P 1 +2P 2 +…+n(P n +P n+ 1 +…+P s) или

P 1 +2P 2 +…+(n-1)P n- 1 +n(1-P 0 -P 1 -…-P n-1).

Через находим абсолютную пропускную способность системы:

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

Пример 1. На вход трехканальной СМО с отказами поступает поток заявок с интенсивностью =4 заявки в минуту, время обслуживания заявки одним каналом t обсл =1/μ =0,5 мин. Выгодно ли с точки зрения пропускной способности СМО заставить все три канала обслуживать заявки сразу, причем среднее время обслуживания уменьшается втрое? Как это скажется на среднем времени пребывания заявки в СМО?

Решение. Находим вероятность простоя трехканальной СМО по формуле

ρ = /μ =4/2=2, n=3,

Р 0 = = = 0,158.

Вероятность отказа определяем по формуле:

Р отк =Р n ==

P отк = 0,21.

Относительная пропускная способность системы:

Р обсл =1-Р отк 1-0,21=0,79.

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

А= Р обсл 3,16.

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

1,58, доля каналов, занятых обслуживанием,

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

Объединяя все три канала в один, получаем одноканальную систему с параметрами μ=6, ρ=2/3. Для одноканальной системы вероятность простоя:

Р 0 = = =0,6,

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

Р отк =ρ Р 0 = =0,4,

относительная пропускная способность:

Р обсл =1-Р отк =0,6,

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

А= Р обсл =2,4.

t СМО =Р обсл = =0,1 мин.

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

Пример 2. На вход трехканальной СМО с неограниченной очередью поступает поток заявок с интенсивностью =4 заявки в час, среднее время обслуживания одной заявки t=1/μ=0,5 ч. Найти показатели эффективности работы системы.

Для рассматриваемой системы n=3, =4, μ=1/0,5=2, ρ= /μ=2, ρ/n=2/3<1. Определяем вероятность простоя по формуле:

Р=.

P 0 = =1/9.

Среднее число заявок в очереди находим по формуле:

L=.

Среднее время ожидания заявки в очереди считаем по формуле:

Среднее время пребывания заявки в системе:

Т=t+ 0,22+0,5=0,72.

Пример 3. В парикмахерской работают 3 мастера, а в зале ожидания расположены 3 стула. Поток клиентов имеет интенсивность =12 клиентов в час. Среднее время обслуживания t обсл =20 мин. Определить относительную и абсолютную пропускную способность системы, среднее число занятых кресел, среднюю длину очереди, среднее время, которое клиент проводит в парикмахерской.

Для данной задачи n=3, m=3, =12, μ=3, ρ=4, ρ/n=4/3. Вероятность простоя определяем по формуле:

Р 0 =.

P 0 = 0,012.

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

Р отк =Р n+m = .

P отк =P n + m 0,307.

Относительная пропускная способность системы, т.е. вероятность обслуживания:

P обсл =1-P отк 1-0,307=0,693.

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

А= Р обсл 12 .

Среднее число занятых каналов:

.

Средняя длина очереди определяется по формуле:

L=

L= 1,56.

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

Среднее число заявок в СМО:

Среднее время пребывания заявки в СМО:

Т=М/ 0,36 ч.

Пример 4. Рабочий обслуживает 4 станка. Каждый станок отказывает с интенсивностью =0,5 отказа в час, среднее время ремонта t рем =1/μ=0,8 ч. Определить пропускную способность системы.

Эта задача рассматривает замкнутую СМО, μ=1,25, ρ=0,5/1,25=0,4. Вероятность простоя рабочего определяем по формуле:

Р 0 =.

P 0 = .

Вероятность занятости рабочего Р зан =1-Р 0 . А=(1-P 0)μ=0,85μ станков в час.

Решение задачи

Два рабочих обслуживают группу из четырех станков. Остановки работающего станка происходят в среднем через 30 мин. Среднее время наладки составляет 15 мин. Время работы и время наладки распределено по экспоненциальному закону.

Найдите среднюю долю свободного времени для каждого рабочего и среднее время работы станка.

Найдите те же характеристики для системы, в которой:

а) за каждым рабочим закреплены два станка;

б) два рабочих всегда обслуживают станок вместе, причем с двойной интенсивностью;

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

Возможны следующие состояния системы S:

S 0 – все станки исправны;

S 1 – 1 станок ремонтируется, остальные исправны;

S 2 – 2 станок ремонтируется, остальные исправны;

S 3 – 3 станок ремонтируется, остальные исправны;

S 4 – 4 станок ремонтируется, остальные исправны;

S 5 – (1, 2) станки ремонтируются, остальные исправны;

S 6 – (1, 3) станки ремонтируются, остальные исправны;

S 7 – (1, 4) станки ремонтируются, остальные исправны;

S 8 – (2, 3) станки ремонтируются, остальные исправны;

S 9 – (2, 4) станки ремонтируются, остальные исправны;

S 10 – (3, 4) станки ремонтируются, остальные исправны;

S 11 – (1, 2, 3) станки ремонтируются, 4 станок исправен;

S 12 – (1, 2, 4) станки ремонтируются, 3 станок исправен;

S 13 – (1, 3, 4) станки ремонтируются, 2 станок исправен;

S 14 – (2, 3, 4) станки ремонтируются, 1 станок исправен;

S 15 – все станки ремонтируются.

Граф состояний системы…

Данная система S является примером замкнутой системы, так как каждый станок является потенциальным требованием, превращаясь в реальное в момент своей поломки. Пока станок работает, он находится в блоке задержки, а с момента поломки до момента окончания ремонта – в самой системе. Каждый рабочий является каналом обслуживания.

Если рабочий занят, он налаживает μ-станков в единицу времени, пропускная способность системы:

Средняя доля свободного времени для каждого рабочего ≈ 0,09.

Среднее время работы станка ≈ 3,64.

а) За каждым рабочим закреплены два станка.

Вероятность простоя рабочего определяется по формуле:

Вероятность занятости рабочего:

Если рабочий занят, он налаживает μ-станков в единицу времени, пропускная способность системы:

Средняя доля свободного времени для каждого рабочего ≈ 0,62.

Среднее время работы станка ≈ 1,52.

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

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

Сравнение 5 ответов:

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

Заключение

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

Возможность применения теории принятия решений в системах массового обслуживания определяется следующими факторами:

1. Количество заявок в системе (которая рассматривается как СМО) должно быть достаточно велико (массово).

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

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

4. Структура СМО, т.е. набор поступающих требований и последовательность обработки заявки, должна быть жестко зафиксирована.

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

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

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

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

Список литературы

1) http://www.5ballov.ru.

2) http://www.studentport.ru.

3) http://vse5ki.ru.

4) http://revolution..

5) Фомин Г.П. Математические методы и модели в коммерческой деятельности. М: Финансы и статистика, 2001.

6) Гмурман В.Е. Теория вероятностей и математическая статистика. М: Высшая школа, 2001.

Остальных состояний системы. В результате получим систему уравнений: Решение этой системы будет иметь вид: (4) ,…, (5) 4. Основные понятия и классификация систем массового обслуживания Заявкой (или требованием) называется спрос на удовлетворение какой-либо потребности (далее потребности предполагаются однотипными). Выполнение...

2-3 Поиск литературы 7 1 7 2-4 Разработка модели разветвленной СМО 6 1 6 3 Поиск литературы завершен 3-6 Изучение литературы по теории массового обслуживания 10 1 10 4 Модель разработана 4-5 Разработка алгоритма программы 10 1 10 5 Алгоритм программы разработан 5-7 Выбор среды программиро-вания и создание программы 30 1 ...

Очередь длины k, остается в ней с вероятностью Pk и не присоединяется к очереди с вероятностью gk=1 - Pk,". именно так обычно ведут себя люди в очередях. В системах массового обслуживания, являющихся математическими моделями производственных процессов, возможная длина очереди ограничена постоянной величиной (емкость бункера, например). Очевидно, это частный случай общей постановки. Некоторые...

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

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

· расчетно-кассовые узлы в банках, на предприятиях;

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

· станции технического обслуживания автомобилей; АЗС;

· аудиторские фирмы;

· отделы налоговых инспекций, занимающиеся приёмкой и проверкой текущей отчетности предприятий;

· телефонные станции и т. д.

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

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

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

1. В зависимости от условий ожидания начала обслуживания различают:

СМО с потерями (отказами);

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

В СМО с отказами требования, поступающие в момент, когда все каналы обслуживания заняты, получают отказ и теряются. Классическим примером системы с отказами является телефонная станция. Если вызываемый абонент занят, то требование на соединение с ним получает отказ и теряется.

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

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

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

2. По числу каналов обслуживания СМО делятся на:

- одноканальные;

- многоканальные.

3. По месту нахождения источника требований СМО делятся на:

- разомкнутые, когда источник требования находится вне системы;

- замкнутые, когда источник находится в самой системе.

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

Возможны и другие признаки классификации СМО, например по дисциплине обслуживания, однофазные и многофазные СМО и др.

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

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

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

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

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

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

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

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

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

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

т.е. вероятность того, что время обслуживания не превосходит некоторой величины t, определяется формулой (8.44), где р - параметр экспоненциального закона распределения времени обслуживания требований в системе, т.е. величина, обратная среднему времени обслуживания :

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

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

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

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

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

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

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

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

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

1. Введем в рассмотрение параметр α = l/m. Заметим, что если α/n < 1, то очередь не может расти безгранично. Это условие имеет следующий смысл: l - среднее число требований, поступающих за единицу времени, 1/m - среднее время обслуживания одним каналом одного требования, тогда α = l · 1/m - среднее число каналов, которое необходимо иметь, чтобы обслуживать в единицу времени все поступающие требования. Поэтому условие α/ n < 1 означает, что число обслуживающих каналов должно быть больше среднего числа каналов, необходимых для того, чтобы за единицу времени обслужить все поступившие требования. Важнейшие характеристики работы СМО:

(8.46)

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

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

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

(8.49)

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

(8.50)

6. Средняя длина очереди:

7. Среднее число свободных от обслуживания каналов:

(8.52)

8. Коэффициент простоя каналов:

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

10. Коэффициент загрузки каналов.

ЧАСТЬ 3.

Модель М/М/1/N

разомкнутыми (или открытыми)

.

N > k заявок.

, где k

; ; ; …;

; ; .

В общем виде

или

для всех . Здесь

. (3.1.1)

Сводка формул

; ;

(факториальные многочлены);

; ; ;

; ; ; ;

; ; ;

; ; ;

; ;

;

;

; ;

;

;

; .

Модель М/М/m//N

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

Граф такой системы имеет вид, изображенный на рис. 11 (на языке символики Кендалла – это система М/М/m//N). Вычисляя вероятности стационарных состояний системы обычным образом, имеем

; ; ;

; ;

; … ;

; ;

,

так что в общем виде

при ;

при

или при ; при

Где – биномиальные коэффициенты. Ясно, что при этом

.

Для случая очереди нет, и тогда имеем особенно простую зависимость (формула бинома Ньютона)

Сводка формул

;

при ;

при ;

; ;

; ;

; ; ; ;

; ; ;

; ;

;

; ;

;

;

;
;

; ; ; ;

; .

Сводка формул

; ;

; ;

; ;

; ;

; ; ; ;

.

Модель М/М/m/Е/N

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

метров может быть сведена к любому из них. Предположим, что в системе имеется конечное число требований, m обслуживающих приборов (каналов) и, кроме того, конечное число мест для ожидания, что общее число требований в очереди не может превышать E . Предположим также, что , при этом все требования, поступающие в систему тогда, когда в ней уже имеется заявок, теряются и немедленно возвращаются в группу поступающих так, как будто бы они были полностью обслужены (на языке символики Кендалла – это система М/М/m/E/N). Граф состояний такой СМО имеет вид, изображенный на рис. 13. При эта модель переходит в модель зам-кнутой многоканальной СМО, рассмотренную в § 3.2, а при в модель Энгсета.

Решение уравнений Колмогорова в данном случае вполне аналогично тому, которое было получено в § 3.2 для модели М/М/m//N, так что запишем сразу его конечный результат, которым является связка формул

при ;

при

.

Сводка формул

;

при ;

при ;

; ;

; ;

; ;

;

; ; ; ;

;

; ;

;

;

.

Сводка формул

;

при ;

при ;

; ;

;

; ;

; ; ; ;

; ; ;

;

; ;

.

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

ЧАСТЬ 3.

МОДЕЛИ ЗАМКНУТЫХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

Модель М/М/1/N

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

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

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

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

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

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

ным . Или, что то же самое, ‑ это среднее время нахождения одного требования в источнике заявок от окончания обслуживания и до его возвращения обратно в систему. В этом случае физический смысл интенсивности , очевидно, заключается в том, что она определяет среднее число возвращений в единицу времени (своего рода частоту возвращений) одной заявки после обслуживания обратно в систему. И тогда, в свою очередь, общая интенсивность поступающих в систему требований равна , где k – номер состояния системы, то есть число заявок, реально в ней находящихся, как в очереди, так и под обслуживанием. Граф такой системы изображен на рис. 10. В рамках символики Кендалла такие системы массового обслуживания обозначают аббревиатурой М/М/1//N, в которой последний символ означает полное (предельное) число заявок в системе.

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

Применяя общие формулы расчета вероятностей стационарных состояний для процесса гибели и размножения, изображенного на графе состояний (рис. 10), имеем

; ; ; …;

; ; .

В общем виде

или

для всех . Здесь

– так называемые факториальные многочлены или обобщенные степени . Ясно, что при этом

Документы