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

Министерство образования  и науки Российской федерации

Федеральное государственное  бюджетное образовательное учреждение высшего профессионального образования

«Комсомольский-на-Амуре  государственный

технический университет»

 

Факультет экономики и  менеджмента

Кафедра экономики и финансов

 

 

 

 

Контрольная работа

По дисциплине «Теория  систем массового обслуживания»

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

 

Студент группы   2ЭКб2Ка-1                                                       Бузмакова И.А.

Преподаватель                                                                        

 

 

 

2012

Введение

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

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

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

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

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

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

 

 

1 Одноканальная СМО с отказами в обслуживании

 

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

Работу одноканальной  СМО n=1 можно представить в виде размеченного графа состояний (1.1).

Переходы СМО из одного состояния S₀ в другое S₁ происходят под действием входного потока заявок с интенсивностью λ, а обратный переход – под действием потока обслуживания с интенсивностью μ.

 λ

S0

S1

 

 μ

S₀ – канал обслуживания свободен; S₁ – канал занят обслуживанием;

Рис. 1.1 Размеченный граф состояний одноканальной СМО

Запишем систему дифференциальных уравнений Колмогорова для вероятностей состояния по изложенным выше правилам:

Откуда получим дифференциальное уравнение для определения вероятности  р₀(t) состояния S₀:

Это уравнение можно решить при начальных условиях в предположении, что система в момент t=0 находилась в состоянии S₀, тогда р₀(0)=1, р₁(0)=0.

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

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

Вероятность р₀(t) уменьшается с течением времени и в пределе при t→∞ стремится к величине

а вероятность р₁(t) в то же время увеличивается от 0, стремясь в пределе при t→∞ к величине

Эти пределы вероятностей могут быть получены непосредственно  из уравнений Колмогорова при  условии

Функции р₀(t) и р₁(t) определяют переходный процесс в одноканальной СМО и описывают процесс экспоненциального приближения СМО к своему предельному состоянию с постоянной времени характерной для рассматриваемой системы.

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

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

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

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

В пределе при t→∞ практически уже при t>3τ значение относительной пропускной способности будет равно

Абсолютная пропускная способность, определяющая число заявок, обслуживаемых  в единицу времени в пределе  при t→∞, равна:

Соответственно доля заявок, получивших отказ, составляет в этих же предельных условиях:

 а общее число не обслуженных заявок равно

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

 

 

 

 

 

 

 

 

 

2. Одноканальная СМО с ограниченной длиной очереди

 

В коммерческой деятельности чаще встречаются СМО с ожиданием (очередью).

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

Граф этой СМО представлен  на рис. 2.1 .

 S_m

S₃

S₂

S₁

S₀

 λ λ λ λ ... λ

 μ μ μ μ ... μ

 

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

Состояния СМО можно представить  следующим образом:

S₀ - канал обслуживания свободен,

S, - канал обслуживания занят, но очереди нет,

S₂ - канал обслуживания занят, в очереди стоит одна заявка,

S₃ - канал обслуживания занят, в очереди стоят две заявки,

S_m+1 - канал обслуживания занят, в очереди все т мест заняты, любая следующая заявка получает отказ.

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

p₁ = ρ * ρ_о

p₂=ρ^{2 *} ρ₀

p_k=ρ^k * ρ₀

P_m+1 = p^m=1 * ρ₀

p₀=[1+ρ+ρ²+ρ³+...+ρ^m+1]^-1

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

ρ= (1- ρ )

(1- ρ^m+2)

Эта формула справедлива  для всех р, отличных от 1, если же р = 1, то р₀ = 1/(т + 2), а все остальные вероятности также равны 1/(т + 2). Если предположить т = 0, то мы переходим от рассмотрения одноканальной СМО с ожиданием к уже рассмотренной одноканальной СМО с отказами в обслуживании. Действительно, выражение для предельной вероятности р₀ в случае т = 0 имеет вид:

p_о ⁼ μ / (λ+μ)

И в случае λ ⁼ μ имеет величину р₀ = 1 / 2.

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

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

Состояния S_m+1:

P_отк = p_m+1 = ρ^m+1 * p₀

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

Q = 1- p_отк = 1- ρ^m+1 * p₀

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

A = Q * λ

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

L_оч-= M(k).

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

1 - в очереди стоит одна  заявка,

2 - в очереди две заявки,

т-в очереди все места заняты

Вероятности этих значений определяются соответствующими вероятностями  состояний, начиная с состояния  S₂. Закон распределения дискретной случайной величины к изображается следующим образом:

 

k	1	2		m
pi	p2	p3		pm+1

 

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

L_оч = 1* p₂ +2* p₃ +...+ m* p_m+1

В общем случае при p ≠1 эту сумму можно преобразовать, пользуясь моделями геометрической прогрессии, к более удобному виду:

L_оч = p² * 1- p^m * (m-m*p+1) _* p₀

( 1- p )²

В частном случае при р = 1, когда все вероятности p_k оказываются равными, можно воспользоваться выражением для суммы членов числового ряда

1+2+3+ m = m(m+1)

2

Тогда получим формулу

L’_оч = m(m+1) _* p₀ = m(m+1) (p=1).

2 2(m+1)

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

Т_оч = L_оч/А (при р ≠ 1) и Т¹_оч = L’_оч /А(при р = 1).

Такой результат, когда оказывается, что Т_оч ~ 1/ λ, может показаться странным: с увеличением интенсивности потока заявок как будто бы должна возрастать длина очереди и уменьшается среднее время ожидания. Однако следует иметь в виду, что, во-первых, величина L_оч является функцией от λ и μ и, во-вторых, рассматриваемая СМО имеет ограниченную длину очереди не более m заявок.