Главная » Бизнес » Структура и показатели эффективности систем массового обслуживания. Курсовая работа: Имитационное моделирование системы массового обслуживания К показателям эффективности использования смо относятся

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

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

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

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

показатели, характеризующие систему в целом: число n занятых каналов обслуживания, число обслуженных (λ b ), ожидающих обслуживание или получивших отказ заявок (λ c ) в единицу времени и т.д.;
вероятностные характеристики : вероятность того, что заявка будет обслужена (P обс) или получит отказ в обслуживании (P отк), что все приборы свободны (p 0) или определенное число их занято (p k ), вероятность наличия очереди и т.д.;
экономические показатели : стоимость потерь, связанных с уходом не обслуженной по тем или иным причинам заявки из системы, экономический эффект, полученный в результате обслуживания заявки, и т.д.

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

Многоканальная система с отказами

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

Смешанные системы

Система с ограничением на длину очереди .
Состоит из накопителя (очереди) и узла обслуживания. Заявка покидает очередь и уходит из системы, если в накопителе к моменту ее появления уже находятся m заявок (m – максимально возможноечисло мест в очереди). Если заявка поступила в систему и застала, хотя бы один канал свободным, она мгновенно начинает обслуживаться. Если в момент поступления заявки в систему все каналы заняты, то заявка не покидает систему, а занимает место в очереди. Заявка покидает систему не обслуженной, если к моменту её поступления в систему заняты все каналы обслуживания и все места в очереди.
Для каждой системы определяется дисциплина очереди. Это система правил, определяющих порядок поступления заявок из очереди в узел обслуживания. Если все заявки и каналы обслуживания равнозначны, то чаще всего действует правило «кто раньше пришел, тот раньше обслуживается».
Система с ограничением на длительность пребывания заявки в очереди .
Состоит из накопителя (очереди) и узла обслуживания. От предыдущей системы она отличается тем, что заявка, поступившая в накопитель (очередь), может ожидать начала обслуживания лишь ограниченное время Т ож (чаще всего это случайная величина). Если её время Т ож истекло, то заявка покидает очередь и уходит из системы не обслуженной.

Математическое описание СМО

СМО рассматриваются как некоторые физические системы с дискретными состояниями х 0 , х 1 , …, х n , функционирующие при непрерывном времени t . Число состояний n может быть конечным или счетным (n → ∞). Система может переходить из одного состояния х i (i= 1, 2, … , n) в другое х j (j= 0, 1, … ,n) в произвольный момент времени t . Чтобы показать правила таких переходов, используют схему, называемую графом состояний . Для типов перечисленных выше систем графы состояний образуют цепь, в которой каждое состояние (кроме крайних) связано прямой и обратной связью с двумя соседними состояниями. Это схема гибели и размножения.
Переходы из состояния в состояние происходят в случайные моменты времени. Удобно считать, что эти переходы происходят в результате действия каких-то потоков (потоков входных заявок, отказов в обслуживании заявок, потока восстановления приборов и т.д.). Если все потоки простейшие, то протекающий в системе случайный процесс с дискретным состоянием и непрерывным временем будет марковским.
Поток событий - это последовательность однотипных событий, протекающих в случайные моменты времени. Его можно рассматривать как последовательность случайных моментов времени t 1 , t 2 , … появления событий.
Простейшим называют поток, обладающий следующими свойствами:

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

В простейшем потоке интервалы времени Т 1 , Т 2 ,… между моментами t 1 , t 2 , … появления событий случайны, независимы между собой и имеют показательное распределение вероятностей f(t)=λe -λt , t≥0, λ=const, где λ - параметр показательного распределения, являющийся одновременно интенсивностью потока и представляющий собой среднее число событий, происходящих в единицу времени. Таким образом, t =M[T]=1/λ.
Марковские случайные события описываются обыкновенными дифференциальными уравнениями . Переменными в них служат вероятности состояний р 0 (t), p 1 (t),…,p n (t) .
Для очень больших моментов времени функционирования систем (теоретически при t → ∞) в простейших системах (системы, все потоки в которых – простейшие, а граф – схема гибели и размножения) наблюдается установившийся, или стационарный режим работы. В этом режиме система будет изменять свое состояние, но вероятности этих состояний (финальные вероятности ) р к , к= 1, 2 ,…, n, не зависят от времени и могут рассматриваться как среднее относительное время пребывания системы в соответствующем состоянии.

Система массового обслуживания состоит из следующих элементов (рисунок 5.6).

1 - входящий поток требований ω(t ) – совокупность требований к СМО на проведение определенных работ (заправка, мойка, ТО и др.) или оказание услуг (покупка изделий, деталей, материалов и др.). Входящий поток требований может быть постоянным и переменным.

Требования бывают однородные (одинаковые виды работ или услуг) и неоднородные (разные виды работ или услуг).

2 - очередь – требования, ожидающие обслуживания. Очередь оценивается средней длиной r – числом объектов или клиентов, ожидающих обслуживания.

Рисунок 5.6 – Общая схема системы массового обслуживания

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

4 - выходящий поток требований ω’(t ) – поток требований, прошедших СМО. В общем случае выходящий поток может состоять из требований обслуженных и необслуженных. Пример необслуженных требований: отсутствие нужной детали для автомобиля, находящегося в ремонте.

5- замыкание (возможное) СМО – состояние системы, при котором входящий поток требований зависит от выходящего.

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

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

1 По ограничениям на длину очереди:

СМО с потерями – требование покидает СМО необслуженным, если в момент его поступления все каналы заняты;

СМО без потерь – требование занимает очередь, даже если все каналы
заняты;

СМО с ограничениями по длине очереди m или времени ожидания: если существует ограничение на очередь, то вновь поступившее (m +1)-е требование выбывает из системы необслуженным (например, ограниченная емкость накопительной площадки перед АЗС).

2 По количеству каналов обслуживания п:

Одноканальные: n =1;

Многоканальные n ≥2.

3 По типу обслуживающих каналов:

Однотипные (универсальные);

Разнотипные (специализированные).

4 По порядку обслуживания:

Однофазовые – обслуживание производится на одном аппарате (посту);

Многофазовые – требования последовательно проходит несколько аппаратов обслуживания (например, поточные линии ТО; конвейерная сборка автомобиля; линия внешнего ухода: уборка → мойка → обсушка → полировка).

5 По приоритетности обслуживания:

Без приоритета – требования обслуживаются в порядке их поступления на СМО;

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

6 По величине входящего потока требований:

С неограниченным входящим потоком;

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

7 По структуре СМО:

Замкнутые – входящий поток требований при прочих равных условиях зависит от числа ранее обслуженных требований (комплексное АТП, обслуживающее только свои автомобили (5 на рисунке 5.6));

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

8 По взаимосвязи обслуживающих аппаратов:

С взаимопомощью – пропускная способность аппаратов непостоянна и зависит от занятости других аппаратов: бригадное обслуживание нескольких постов СТО; использование «скользящих» рабочих;

Без взаимопомощи – пропускная способность аппарата не зависит от работы других аппаратов СМО.

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

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

Интенссивность обслуживания

где ω - параметр потока требований.

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

A =ωg ,

(5.13)

где g - .

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

Вероятность того, что все посты свободны Р 0 , характеризует такое состояние системы, при котором все объекты исправны и не требуют проведения технических воздействий, т.е. требования отсутствуют.

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

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

Зависимости для определения названных параметров функционирования СМО определяются ее структурой.

где n зан - .

Время связи требования с системой:

СМО с потерями

t сист =gt д;

(5.16)

СМО без потерь

t сист =t д +t ож.

(5.17)

И =С 1 r +С 2 n сн +(С 1 +C 2)ρ,

(5.18)

где С 1 - стоимость простоя автомобиля в очереди;

r - средняя длина очереди;

С 2 -стоимость простоя обслуживающего канала;

n сн - количество простаивающих (свободных) каналов;

t ож - среднее время нахождения в очереди.

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

Пример. Станция технического обслуживания имеет один пост диагностирования (п= 1). Длина очереди ограничена двумя автомобилями (т= 2). Определить параметры эффективности работы диагностического поста, если интенсивность потока требований на диагностирование в среднем А =2 треб./ч, продолжительность диагностирования t д = 0,4 ч.

Интенсивность диагностирования μ=1/0,4=2,5.

Приведенная плотность потока ρ=2/2,5=0,8.

Вероятность того, что пост свободен,

P 0 =(1-ρ)/(1-ρ m +2)=(1-0,8)/(1-0,8 4)=0,339.

Вероятность образования очереди

P оч =ρ 2 Р 0 =0,8 2 0,339=0,217.

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

P отк =ρ m +1 (1-ρ)/(1-ρ m +2)=0,8 3 (1-0,8)/(1-0,84)=0,173.

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

g =1-P отк =1-0,173=0,827.

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

А =2 0,827=1,654 треб./ч.

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

n зан =(ρ-ρ m +2)/(1-ρ m +2)=(0,8-0,8 4)/(1-0,8 4)=0,661=1-P 0 .

Среднее количество требовниий, находящихся вочереди,

Среднее время нахождения требования в очереди

t ож =r /ω=0,564/2=0,282 ч.

Пример. На автотранспортном предприятии имеется один пост диагностирования (п= 1). В данном случае длина очереди практически неограниченна. Определить параметры эффективности работы диагностического поста, если стоимость простоя автомобилей в очереди составляет С 1 = 20 ре (расчетных единиц) в смену, а стоимость простоя постов С 2 = 15 ре Остальные исходные данные те же, что и для предыдущего примера.

Вероятность того, что пост свободен

P 0 =1-ρ=1-0,8=0,2.

Вероятность образования очереди

P оч =ρ 2 Р 0 =0,8 2 0,2=0,128.

Относительная пропускная способность g =1, так как все намеченные автомобили пройдут через диагностический пост.

Абсолютная пропускная способность А =ω=2 треб./ч.

Среднее количество занятых постов n зан =ρ=0,8.

r =ρ 2 /(1-ρ)=0,8 2 /(1-0,8)=3,2.

Среднее время ожидания в очереди

t ож =ρ 2 /(1-ρ)/μ=0,8 2 /(1-0,8)/2,5=1,6.

Издержки от функционирования системы

И =С 1 r +С 2 n сн +(С 1 +C 2)ρ=20 3,2+15 0,2+(20+15) 0,8=95,0 ре/смену.

Пример. На том же автотранспортном предприятии число постов диагностирования увеличено до двух (n =2), т.е. создана многоканальная система. Так как для создания второго поста необходимы капиталовложения (площади, оборудование и т.д.), то цена простоя средств обслуживания увеличивается до С’ 1 =22 ре. Определить параметры эффективности работы системы диагностирования. Остальные исходные данные те же, что для предыдущего примера.

Интенсивность диагностирования и приведенная плотность потока остаются теми же: μ=2,5, ρ=0,8.

Вероятность того, что оба поста свободны,

Р 0 =1:
=0,294.

Вероятность образования очереди

P оч =ρ n Р 0 /n !=0,8 2 0,294/2=0,094,

т.е. на 37 % ниже, чем в предыдущем примере.

Относительная пропускная способность g =1, так как все автомобили пройдут через диагностические посты.

Абсолютная пропускная способность А =2 треб./ч.

Среднее количество занятых постов n зан =ρ=0,8.

Среднее количество требований, находящихся в очереди,

r =ρP оч /(n -ρ)=0,8 2 0,094/(2-0,8)=0,063.

Среднее время нахождения в очереди

t ож =P оч /(n -ρ)/μ=0,094/(2-0,8)/2,5=0,031.

Издержки от функционирования системы

И =С 1 r +С 2 n сн +(С 1 +C 2)ρ=20 0,063+22 1,2+(20+22) 0,8=61,26 ре/смену,

т.е. в 1,55 раза ниже, чем при тех же условиях для одного диагностического поста, главным образом за счет сокращения очереди автомобилей на диагностику и времени ожидания автомобилей более чем в 50 раз. Следовательно, строительство второго диагностического поста в рассматриваемых условиях целесообразно. Используя формулу (5.18) из условия И 1 =И 2 , можно оценить предельные значения цены простоя средств обслуживания при строительстве и оснащении второго диагностического поста, которая в рассмотренном примере составляет C 2 пр =39 ре.

Показатели эффективности СМО

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

Показатели, характеризующие систему с точки зрения потребителей :

P обс – вероятность обслуживания заявки,
t сист – время пребывания заявки в системе.

Показатели, характеризующие систему с точки зрения её эксплуатационных свойств :

λ b – абсолютная пропускная способность системы (среднее число обслуженных заявок в единицу времени),
P обс – относительная пропускная способность системы,
k з – коэффициент загрузки системы.

см. также Параметры экономической эффективности СМО

Задача . В вычислительный центр коллективного пользования с тремя ЭВМ поступают заказы от предприятий на вычислительные работы. Если работают все три ЭВМ, то вновь поступающий заказ не принимается, и предприятие вынуждено обратиться в другой вычислительный центр. Среднее время работы с одним заказом составляет 3 ч. Интенсивность потока заявок 0,25 (1/ч). Найти предельные вероятности состояний и показатели эффективности работы вычислительного центра.
Решение. По условию n=3, λ=0,25(1/ч), t об. =3 (ч). Интенсивность потока обслуживаний μ=1/t об. =1/3=0,33. Интенсивность нагрузки ЭВМ по формуле (24) ρ=0,25/0,33=0,75. Найдем предельные вероятности состояний:
по формуле (25) p 0 =(1+0,75+0,75 2 /2!+0,75 3 /3!) -1 =0,476;
по формуле (26) p 1 =0,75∙0,476=0,357; p 2 =(0,75 2 /2!)∙0,476=0,134; p 3 =(0,75 3 /3!)∙0,476=0,033 т.е. в стационарном режиме работы вычислительного центра в среднем 47,6% времени нет ни одной заявки, 35,7% - имеется одна заявка (занята одна ЭВМ), 13,4% - две заявки (две ЭВМ), 3,3% времени - три заявки (заняты три ЭВМ).
Вероятность отказа (когда заняты все три ЭВМ), таким образом, P отк. =p 3 =0,033.
По формуле (28) относительная пропускная способность центра Q = 1-0,033 = 0,967, т.е. в среднем из каждых 100 заявок вычислительный центр обслуживает 96,7 заявок.
По формуле (29) абсолютная пропускная способность центра A= 0,25∙0,967 = 0,242, т.е. в один час в среднем обслуживается 0,242 заявки.
По формуле (30) среднее число занятых ЭВМ k =0,242/0,33 = 0,725, т.е. каждая из трех ЭВМ будет занята обслуживанием заявок в среднем лишь на 72,5/3 =24,2%.
При оценке эффективности работы вычислительного центра необходимо сопоставить доходы от выполнения заявок с потерями от простоя дорогостоящих ЭВМ (с одной стороны, у нас высокая пропускная способность СМО, а с другой стороны - значительный простой каналов обслуживания) и выбрать компромиссное решение.

Задача . В порту имеется один причал для разгрузки судов. Интенсивность потока судов равна 0,4 (судов в сутки). Среднее время разгрузки одного судна составляет 2 суток. Предполагается, что очередь может быть неограниченной длины. Найти показатели эффективности работы причала, а также вероятность того, что ожидают разгрузки не более чем 2 судна.
Решение. Имеем ρ = λ/μ = μt об. =0,4∙2=0,8. Так как ρ = 0,8 < 1, то очередь на разгрузку не может бесконечно возрастать и предельные вероятности существуют. Найдем их.
Вероятность того, что причал свободен, по (33) p 0 = 1 - 0,8 = 0,2, а вероятность того, что он занят, P зан. = 1-0,2 = 0,8. По формуле (34) вероятности того, что у причала находятся 1, 2, 3 судна (т.е. ожидают разгрузки 0, 1, 2 судна), равны p 1 = 0,8(1-0,8) = 0,16; p 2 = 0,8 2 ∙(1-0,8) = 0,128; p 3 = 0,8 3 ∙(1-0,8) = 0,1024.
Вероятность того, что ожидают разгрузку не более чем 2 судна, равна
P=p 1 +p 2 +p 3 = 0,16 + 0,128 + 0,1024 = 0,3904
По формуле (40) среднее число судов, ожидающих разгрузки
L jч =0,8 2 /(1-0,8) = 3,2
а среднее время ожидания разгрузки по формуле (15.42)
T оч =3,2/0,8 = 4 сутки.
По формуле (36) среднее число судов, находящихся у причала, L сист. = 0,8/(1-0,8) = 4 (сутки) (или проще по (37) L сист. = 3,2+0,8 = 4 (сутки), а среднее время пребывания судна у причала по формуле (41) T сист = 4/0,8 = 5 (сутки).
Очевидно, что эффективность разгрузки судов невысокая. Для ее повышения необходимо уменьшение среднего времени разгрузки судна t об либо увеличение числа причалов n .

Задача . В универсаме к узлу расчета поступает поток покупателей с интенсивностью λ = 81 чел. в час. Средняя продолжительность обслуживания контролером-кассиром одного покупателя t об = 2 мин. Определить:
а. Минимальное количество контролеров-кассиров п min , при котором очередь не будет расти до бесконечности, и соответствующие характеристики обслуживания при n=n min .
б. Оптимальное количество n опт. контролеров-кассиров, при котором относительная величина затрат С отн., связанная с издержками на содержание каналов обслуживания и с пребыванием в очереди покупателей, задаваемая, например, как , будет минимальна, и сравнить характеристики обслуживания при n=n min и n=n опт.
в. Вероятность того, что в очереди будет не более трех покупателей.
Решение.
а. По условию l = 81(1/ч) = 81/60 = 1,35 (1/мин.). По формуле (24) r = l/ m = lt об = 1,35×2 = 2,7. Очередь не будет возрастать до бесконечности при условии r/n < 1, т.е. при n > r = 2,7. Таким образом, минимальное количество контролеров-кассиров n min = 3.
Найдем характеристики обслуживания СМО при п = 3.
Вероятность того, что в узле расчета отсутствуют покупатели, по формуле (45) p 0 = (1+2,7+2,7 2 /2!+2,7 3 /3!+2,7 4 /3!(3-2,7)) -1 = 0,025, т.е. в среднем 2,5% времени контролеры-кассиры будут простаивать.
Вероятность того, что в узле расчета будет очередь, по (48) P оч. = (2,7 4 /3!(3-2,7))0,025 = 0,735
Среднее число покупателей, находящихся в очереди, по (50) L оч. = (2,7 4 /3∙3!(1-2,7/3) 2)0,025 = 7,35.
Среднее время ожидания в очереди по (42) T оч. = 7,35/1,35 = 5,44 (мин).
Среднее число покупателей в узле расчета по (51) L сист. = 7,35+2,7 = 10,05.
Среднее время нахождения покупателей в узле расчета по (41) T сист. = 10,05/1,35 = 7,44 (мин).
Таблица 1

Характеристика обслуживания	Число контролеров-кассиров
Характеристика обслуживания	3	4	5	6	7
Вероятность простоя контролеров-кассиров p 0	0,025	0,057	0,065	0,067	0,067
Среднее число покупателей в очереди T оч.	5,44	0,60	0,15	0,03	0,01
Относительная величина затрат С отн.	18,54	4,77	4,14	4,53	5,22

Среднее число контролеров-кассиров, занятых обслуживанием покупателей, по (49) k = 2,7.
Коэффициент (доля) занятых обслуживанием контролеров-кассиров
= ρ/n = 2,7/3 = 0,9.
Абсолютная пропускная способность узла расчета А = 1,35 (1/мин), или 81 (1/ч), т.е. 81 покупатель в час.
Анализ характеристик обслуживания свидетельствует о значительной перегрузке узла расчета при наличии трех контролеров-кассиров.
б. Относительная величина затрат при n = 3
C отн. = = 3/1,35+3∙5,44 = 18,54.
Рассчитаем относительную величину затрат при других значениях п (табл. 1).
Как видно из табл. 2, минимальные затраты получены при n = n опт. = 5 контролерах-кассирах.
Определим характеристики обслуживания узла расчета при n = n опт. =5. Получим P оч. = 0,091; L оч. = 0,198; Т оч. = 0,146 (мин); L сист. = 2,90; T снст. = 2,15 (мин); k = 2,7; k 3 = 0,54.
Как видим, при n = 5 по сравнению с n = 3 существенно уменьшились вероятность возникновения очереди P оч. , длина очереди L оч. и среднее время пребывания в очереди T оч. и соответственно среднее число покупателей L сист. и среднее время нахождения в узле расчета T сист., а также доля занятых обслуживанием контролеров k 3. Но среднее число занятых обслуживанием контролеров-кассиров k и абсолютная пропускная способность узла расчета А естественно не изменились.
в. Вероятность того, что в очереди будет не более 3 покупателей, определится как
= 1- P оч. + p 5+1 + p 5+2 + p 5+3 , где каждое слагаемое найдем по формулам (45) – (48). Получим при n=5:

Заметим, что в случае n=3 контролеров-кассиров та же вероятность существенно меньше: P(r ≤ 3) =0,464.

1. Показатели эффективности использования СМО:

Абсолютная пропускная способность СМО – среднее число заявок, которое смо-

жет обслужить СМО в единицу времени.

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

обслуживаемых СМО в единицу времени, к среднему числу поступивших за это же

время заявок.

Средняя продолжительность периода занятости СМО.

Коэффициент использования СМО – средняя доля времени, в течение которого

СМО занята обслуживанием заявок, и т.п.

2. Показатели качества обслуживания заявок:

Среднее время ожидания заявки в очереди.

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

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

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

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

Закон распределения времени пребывания заявки в СМО.

Среднее число заявок, находящихся в очереди.

Среднее число заявок, находящихся в СМО, и т.п.

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

Классификация систем массового обслуживания

По числу каналов СМО:

одноканальные (когда имеется один канал обслуживания)

многоканальные , точнее n -канальные (когда количество каналов n ≥ 2).

По дисциплине обслуживания:

1. СМО с отказами , в которых заявка, поступившая на вход СМО в момент, когда все

каналы заняты, получает «отказ» и покидает СМО («пропадает»). Чтобы эта заявка все же

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

2. СМО с ожиданием (неограниченным ожиданием или очередью ). В таких системах

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

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

Эти ограничения могут накладываться на длину очереди , т.е. максимально возможное

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

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

чению которого она выходит из очереди и покидает систему).

В СМО с ожиданием и в СМО смешанного типа применяются различные схемы об-

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

По ограничению потока заявок:

замкнутые и открытые .

Если поток заявок ограничен и заявки, покинувшие систему, могут в нее возвращать-

ся, то СМО является замкнутой , в противном случае – открытой .

По количеству этапов обслуживания:

однофазные и многофазные

Если каналы СМО однородны, т.е. выполняют одну и ту же операцию обслужива-

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

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

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

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

расчетно-кассовые узлы в банках, на предприятиях;
персональные компьютеры, обслуживающие поступающие заявки или требования на решение тех или иных задач;
станции технического обслуживания автомобилей; АЗС;
аудиторские фирмы;
отделы налоговых инспекций, занимающиеся приёмкой и проверкой текущей отчетности предприятий;
телефонные станции и т. д.

	Узлы	Требования

Больница	Санитары	Пациенты
Производство
Аэропорт	Выходы на взлетно-посадочные полосы Пункты регистрации	Пассажиры

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

Рис. 1

Генератор заявок – объект, порождающий заявки: улица, цех с установленными агрегатами. На вход поступает поток заявок (поток покупателей в магазин, поток сломавшихся агрегатов (машин, станков) на ремонт, поток посетителей в гардероб, поток машин на АЗС и т. д.).
Диспетчер – человек или устройство, которое знает, что делать с заявкой. Узел, регулирующий и направляющий заявки к каналам обслуживания. Диспетчер:

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

Очередь – накопитель заявок. Очередь может отсутствовать.
Узел обслуживания состоит из конечного числа каналов обслуживания. Каждый канал имеет 3 состояния: свободен, занят, не работает. Если все каналы заняты, то можно придумать стратегию, кому передавать заявку.
Отказ от обслуживания наступает, если все каналы заняты (некоторые в том числе могут не работать).

Кроме этих основных элементов в СМО в некоторых источниках выделяются также следующие составляющие:

терминатор – уничтожитель трансактов;

склад – накопитель ресурсов и готовой продукции;

счет бухгалтерского учета – для выполнения операций типа «проводка»;

менеджер – распорядитель ресурсов;

Классификация СМО

Первое деление (по наличию очередей):

СМО с отказами;
СМО с очередью.

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

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

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

Итак, например, рассматриваются следующие СМО:

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

Типы ограничения очереди могут быть комбинированными.

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

Естественно, поток заявок, порожденный самой системой, будет зависеть от системы и ее состояния.

Кроме этого СМО делятся на открытые СМО и замкнутые СМО.

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

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

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

одноканальные;
многоканальные.

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

Основными характеристиками системы массового обслуживания любого вида являются:

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

Входной поток требований

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

А i – время поступления между требованиями – независимые одинаково распределенные случайные величины;

E(A) – среднее (МО) время поступления;

λ=1/E(A) – интенсивность поступления требований;

Характеристики входного потока:

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

Дисциплина очереди

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

Очередь имеет имя.

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

первым пришел – первый обслуживаешься;

first in first out (FIFO)

самый распространенный тип очереди.

Какая структура данных подойдет для описания такой очереди? Массив плох (ограничен). Можно использовать структуру типа СПИСОК.

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

Вы как программисты должны уметь делать списки двусторонние, односторонние.

Действия со списком:

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

Структура, известная как СТЕК. Может быть описан структурой массив или список;

случайный отбор заявок;
отбор заявок по критерию приоритетности.

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

Характеристики очереди

ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая длина очереди»);
длина очереди.

Механизм обслуживания

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

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

Для аналитического описания характеристик процедуры обслуживания оперируют понятием «вероятностное распределение времени обслуживания требований».

S i – время обслуживания i -го требования;

E(S) – среднее время обслуживания;

μ=1/E(S) – скорость обслуживания требований.

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

Коэффициент использования СМО

N ·μ – скорость обслуживания в системе, когда заняты все устройства обслуживания.

ρ=λ/(N μ) – называется коэффициентом использования СМО , показывает, насколько задействованы ресурсы системы.

Структура обслуживающей системы

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

Пример. Кассы в магазине.

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

Пример. Медицинская комиссия.

Комбинированное обслуживание – обслуживание вкладов в сберкассе: сначала контролер, потом кассир. Как правило, 2 контролера на одного кассира.

Итак, функциональные возможности любой системы массового обслуживания определяются следующими основными факторами :

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

Основные критерии эффективности функционирования СМО

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

вероятность немедленного обслуживания поступившей заявки (Р обсл =К обс /К пост);
вероятность отказа в обслуживании поступившей заявки (P отк =К отк /К пост);

Очевидно, что Р обсл + P отк =1.

Потоки, задержки, обслуживание. Формула Поллачека–Хинчина

Задержка – один из критериев обслуживания СМО, время проведенное заявкой в ожидании обслуживания.

D i – задержка в очереди требования i ;

W i =D i +S i – время нахождения в системе требования i .

(с вероятностью 1) – установившаяся средняя задержка требования в очереди;

(с вероятностью 1) – установившееся среднее время нахождения требования в СМО (waiting).

Q(t) – число требований в очереди в момент времени t;

L(t) – число требований в системе в момент времени t (Q(t) плюс число требований, которые находятся на обслуживании в момент времени t.

Тогда показатели (если существуют)

(с вероятностью 1) – установившееся среднее по времени число требований в очереди;

(с вероятностью 1) – установившееся среднее по времени число требований в системе.

Заметим, что ρ<1 – обязательное условие существования d, w, Q и L в системе массового обслуживания.

Если вспомнить, что ρ= λ/(N μ), то видно, что если интенсивность поступления заявок больше, чем N μ, то ρ>1 и естественно, что система не сможет справиться с таким потоком заявок, а следовательно, нельзя говорить о величинах d, w, Q и L.

К наиболее общим и нужным результатам для систем массового обслуживания относятся уравнения сохранения

Следует обратить внимание, что упомянутые выше критерии оценки работы системы могут быть аналитически вычислены для систем массового обслуживания M/M/N (N >1), т. е. систем с Марковскими потоками заявок и обслуживания. Для М/G/ l при любом распределении G и для некоторых других систем. Вообще распределение времени между поступлениями, распределение времени обслуживания или обеих этих величин должно быть экспоненциальным (или разновидностью экспоненциального распределения Эрланга k-го порядка), чтобы аналитическое решение стало возможным.

Кроме этого можно также говорить о таких характеристиках, как:

абсолютная пропускная способность системы – А=Р обсл *λ;
относительная пропускная способность системы –

Еще один интересный (и наглядный) пример аналитического решения – вычисление установившейся средней задержки в очереди для системы массового обслуживания M/G/ 1 по формуле:

В России эта формула известна как формула Поллачека– Хинчина, за рубежом эта формула связывается с именем Росса (Ross).

Таким образом, если E(S) имеет большее значение, тогда перегрузка (в данном случае измеряемая как d ) будет большей; чего и следовало ожидать. По формуле можно обнаружить и менее очевидный факт: перегрузка также увеличивается, когда изменчивость распределения времени обслуживания возрастает, даже если среднее время обслуживания остается прежним. Интуитивно это можно объяснить так: дисперсия случайной величины времени обслуживания может принять большое значение (поскольку она должна быть положительной), т. е. единственное устройство обслуживания будет занято длительное время, что приведет к увеличению очереди.

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

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