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

С неограниченной очередью

Примером одноканальной СМО с неограниченной очередью является одна касса в универмаге.

Пусть поток заявок, поступающих в систему, имеет интенсивность λ, а поток обслуживания – интенсивность μ. Граф состояний подобной системы представлен на рис.3.

Рис. 3

На рис.3 введены следующие обозначения:

состояние S₀ – канал свободен;

состояние S₁ – канал занят, очереди нет;

состояние S₂ – канал занят, одна заявка стоит в очереди; …;

состояние S_k – канал занят, k-1 заявок стоит в очереди и т.д.

Таким образом, на рис.3 представлен процесс гибели и размножения для бесконечного числа состояний.

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

Рис. 4

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

Здесь , где p_i(t) – вероятность того, что в момент времени t СМО находится в состоянии S_i.

Решение полученной системы из n+1 уравнений имеет вид:

(10)

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

Как следует из первого уравнения системы (10), предельные вероятности СМО, представленной на рис.3, определяются соотношениями

(в скобках стоит сумма бесконечной геометрической прогрессии со знаменателем ρ). Если ρ<1, то эта сумма равна

.

Таким образом, предельная вероятность состояния S₀ СМО определяется соотношением .

Предельная вероятность любого состояния S_k СМО вычисляется по формуле (см. систему (10)):

. (11)

Т.к. ρ<1, то из последнего равенства следует, что вероятность p₀ наибольшая.

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

.

Среднее число заявок на обслуживании находят как среднее арифметическое взвешенное от двух состояний: канал свободен и каналом обслуживается одна заявка, т.е.

.

Сомножители 0 и 1 в этой системе означают, что в системе на обслуживании находятся ноль заявок, когда канал свободен, или одна заявка, когда канал занят. Вероятности того, что канал свободен или занят соответственно равны p₀ и 1- p₀. Следовательно

. (12)

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

.

Сумма называется бесконечной арифметико-геометрической прогрессией и вычисляется по формуле:

.

Таким образом получим

. (13)

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

. 14)

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

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

Решение. Найдем предельную интенсивность потока заявок:

Т.к. ρ<1, то очередь не может бесконечно возрастать и предельные вероятности существуют.

Предельная вероятность того, что у кассы нет ни одного покупателя

Соответственно вероятность того, что касса занята,

Среднее число заявок на обслуживании, в системе, в очереди найдем по приведенным выше формулам (12-14).

заявок,

заявок,

заявок.

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

мин.;

мин.;

мин.

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

.

Рассчитав предельные вероятности по вышеприведенной формуле, получим:

.

Упражнения

1. На телефонную линию приходит простейший поток вызовов с интенсивностью 0,9 выз./мин.; производительность линии 0,7 выз./мин. Вызов, пришедший на линию во время ее занятости, не обслуживается. Найти абсолютную пропускную способность линии, среднее время обслуживания одного вызова, вероятность отказа в обслуживании, среднее время пребывания заявки в системе.

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

3. Рассматривается круглосуточная работа пункта проведения профилактического осмотра автомашин с одним каналом. На осмотр и выявление дефектов каждой машины затрачивается в среднем 0,5 ч. На осмотр поступает в среднем 36 машин в сутки. Потоки заявок и обслуживаний – простейшие. В случае занятости канала машина покидает пункт осмотра необслуженной. Определить предельные вероятностные состояния и основные характеристики системы.

4. СМО состоит из одного телефонного аппарата. Интенсивность потока желающих воспользоваться телефонным аппаратом составляет 0,25 чел./мин. В среднем каждый человек разговаривает 3 мин. Предполагается, что очередь может быть неограниченной длины. Определить показатели эффективности СМО и вероятность того, что ожидают своей очереди не более двух человек.

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

ОТВЕТЫ К УПРАЖНЕНИЯМ

К главе 1: 1.1. p*=(1;0), q*=(0;1), v=0; 1.2. p*=(2/3;1/3), q*=(1/2;1/2), v=0,3. 2.1. p*=(1;0), q*=(1;0), v=2; 2.2. p*=(3/4;1/4), q*=(1/2;1/2), v=1/2; 2.3. p*=(1/3;2/3), q*=(2/9,7/9), v=8/3; 2.4. p*=(2/3;1/3), q*=(1/2;1/2;0), v=1;2.5. p*=(3/7;4/7), q*=(5/14;0;9/14), v=-1/7.

К главе 2: 1.A=0,394 выз./мин.; p_r=0,5625; мин; мин; 2. μ=0,5 ед./мин=30 ед./ч; Q=0,25; p_r=0,75; A = 22,5; 3. μ=2 маш./мин; p₀=0,571; p₁=0,429; Q=0,571; p_r=0,429; A = 0,857; ч; ч; 4. μ=1/3; ρ=0,75; p₀=0,25; p_зан=0,75; заявок; заявки; заявок; мин; мин; мин; P(k≤3)=0,4336; 5. λ=0,35; ρ=0,7; p₀=0,3; p_зан=0,7; ; ; ; ; P(k≤1)=0,375.

Библиографический список

1. Количественные методы в экономических исследованиях / Под ред. М.В. Грачевой [и др.] – М. : ЮНИТИ-ДАНА, 2004.

2. Костевич Л.С. Математическое программирование: информационные технологии оптимальных решений / Л.С. Костевич. – Минск : Новые знания, 2003.

3. Кузнецов А.В. Математическое программирование / А.В. Кузнецов, Н.И. Холод. – Минск : Вышейш. школа, 1984.

4. Красс М.С. Математика для экономических специальностей / М.С. Красс. – М. : Дело, 2002.

5. Кремер Н.Ш. Теория вероятностей и математическая статистика / Н.Ш. Кремер. – М. : ЮНИТИ, 2006.

6. Кузнецов Б.Т. Математические методы и модели исследования операций / Б.Т.Кузнецов. – М. : ЮНИТИ, 2005.