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

УПРАВЛЕНИЕ, ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА

УДК 519.872

А. П. Кирпичников, А. С. Титовцев СИСТЕМЫ ОБСЛУЖИВАНИЯ С НЕОДНОРОДНЫМ ВХОДНЫМ ПОТОКОМ ТРЕБОВАНИЙ, ОТКАЗАМИ И ОЧЕРЕДЬЮ

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

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

Keywords: queuing system, flow of requirements, queue, serving device.

The problem of the optimum organization of service in СМО of this kind is solved at the set requirements to productivity. A new model of queuing systems - a combination of a multi-linear Erlang model, a multi-linear queuing system with limited queue and classical multi-linear queuing system is presented. Mathematical formalization of model in a quasi-stationaryy mode of functioning is performed.

The problem of optimal-governmental organizations of service in queuing systems of this type at the set requirements to productivity is solved.

Системы массового обслуживания (СМО), встречающиеся в повседневной практике, зачастую представляют собой сложные системы, имеющие во входном потоке требования разных типов. При проектировании объектов массового обслуживания с целью их правильной организации необходимо исследование методом математического моделирования. Известные на сегодняшний день классические модели СМО не позволяют в полной мере описать реальные объекты. Практический интерес имеют более сложные модели, являющиеся комбинациями ранее известных моделей СМО [1 - 3]. В этой связи авторами была предложена модель открытой многолинейной СМО с потерями и очередью. Граф состояний такой СМО приведён на рис.1. Это комбинация многолинейной модели Эрланга, многолинейной СМО с ограниченной очередью и классической многолинейной СМО [4 - 7]. Примером подобных систем могут служить обычные кассы с очередями. Люди, приходящие в кассу, представляют собой входной поток, содержащий требования разного типа: одни люди из-за отсутствия времени пользуются услугой только в том случае, если касса свободна, другие - в зависимости от количества людей в очереди, третьи - дожидаются обслуживания до конца. В работе приводятся конечные формулы общих зависимостей для вероятностных, числовых и временных характеристик открытой многолинейной СМО с потерями и очередью в установившемся режиме работы. Установившимся считается такой режим работы СМО, когда система бесконечно блуждает по всем возможным состояниям, но математические ожидания её числовых и временных характеристик остаются постоянными во времени. Первая и единственная известная авторам попытка математического описания работы комбинированных систем массового обслуживания была предпринята в работе [8], однако её автор, ввиду трудности задачи, ограничился лишь исследованием комбинации модели Эрланга и классической многолинейной СМО, менее интересной с точки зрения возможных приложений [9]. В настоящей работе формализация модели осуществлена по общей схеме, впервые предложенной в фундаментальной монографии [10].

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

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

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

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

Рис. 1 - Граф состояний СМО с неоднородным входным потоком требований, отказами и очередью

Потоки заявок каждого типа являются простейшими и имеют интенсивности X,, X 2, X 3 соответственно, суммарный поток с интенсивностью Л = Х 1 + X 2 + X 3 также является простейшим [например, 11]. Обозначим X = X.! +X 2 - входной поток требований после т-го состояния и X., - входной поток требований после (т + Б) -го состояния (также простейшие). Среднюю интенсивность обслуживания заявок одним обслуживающим устройством обозначим за /и.

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

X, X 2 X з Л X

рі =—; р2 =—; Рз =—; к = — = Рі +р2 +Рз; р = - = рі +р2.

и и и и и

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

Вероятность простоя системы

Р0

О т

Єт(—)+—г

р

т -р

Б + -

рі

т -рі

р = т

К

гда ет (Я) = - - неполная экспонента; вероятности состояний СМО в квазистационарном

¡=о

режиме функционирования

Р

К і

—Р0, О < і < т

Р0, т < і < т + Б

т) т!

— I Г—! —-Р0, і > т + Б

т

т) т!

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

т+Б-і р т

р = V р = —______________р

ГНЗН 7 п Гп

/ . і і=т

т!

і -

т

і-Р.

т

Б, р = т

р * т .

вероятность полной загрузки накопителя

Р,

ПЗН

ад пт

V Р= —-Ро

і=т+Б

т!

і-

Р1

т

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

т-і

РНО = 2 Р = Єт-і (—)Р0 . і=0

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

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

Б

Р

Б

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

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

Р + Р + Р = і

ГНЗН ^ ГПЗН ^ гНО 1 •

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

вероятность отказа в обслуживании вновь прибывшей заявке

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

а = і-Р

Л (

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

среднее число требований, находящихся под обслуживанием

П = —РНО + рРНЗН + РіРПЗН = —(РНО + Рож

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

П2 = — (О - Рт-і ) + —(РНО + тРож );

дисперсия этой величины

средняя длина очереди

(ЗН БРт+Б ^ Р * т

, Р = т

осреднённый квадрат числа требований в очереди

І2 =

т-р

т + р т-р

Р - Е

Е +

2т Л

т-р

Р

т+Е

р * т

(Е + 1Х2Е +1),

6

НЗН

р = т

>+ +рі

Е2

- + -

т т -р1

(2Е + т +рі

V т -р1

Р,

ПЗН>

дисперсия числа требований в очереди

~2 _ |2 72.

О, = І - І ;

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

Кп| =(т - п) I;

коэффициент корреляции числа требований, находящихся под обслуживанием, и длины очереди

Гп1 =

К

ПІ .

среднее число требований в системе в целом

+ т -р)рнзн - ЕРт+Е 1 р* т

т -р

т +-

Е +1'

+ р1

Е 1

1+—+

т т -р1

Р,

ПЗН’

осреднённый квадрат числа требований в системе

к2 = ^ (РНО - Рт-1) + ^РНО + тРож Х

+

р

т -р

Г

т + р

2т +

V т-р.

2Е +1

Л (1 1 Л 1 +

Р - Е ГНЗН Е + 2т Р т+Е

р - т

(Е + 1)т +=-г1 Рнзн, р = т

+ р1

6

— + 2Е + т

1

т -р1

_/ _ч т + р1 2(т + Е) +-----—

т-р1

Р,

р * т

К

ПЗН’

дисперсия числа требований в системе

о? = к2 - к2;

среднее время обслуживания заявки одним каналом

П 1

^обсл « ;

А ^

р

осреднённый квадрат времени обслуживания заявки одним каналом

2

12 = — •

обсл 2 ’

й

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

-2 1

ф 2 = { =___— •

обсл обсл обсл 2 5

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

—=1 •

ожид Д 5

осреднённый квадрат времени ожидания обслуживания заявкой в очереди

1

12 = - < ‘‘ожид д

й

Е2 -1

2-Р^(Рнзм -ЕРт+Е)-Е(Е + 1)Р, т -р

т+Е

+

Рнзн, р = т

} +

Г Е 1 1

2р1 — +

- - і 1

Рпзн + Е(Е + 1)Р,

Дд

дисперсия времени ожидания обслуживания заявкой в очереди

т+Е

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

р

Рожи» (1 ) = 1 - Р7^е-тй 1

ч

— еЕ-1 (к 1) +

р1

т -р

т -р1

Чр1 J

(е (1 - Єе-1 (М ))-

+

р1 р

Е

-ТІ ЄЕ-1

т

т — р1 т — р

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

р

ґ М _ т-1 ^--й 1

'ожид^ _ е

ч

ҐП/ \

к еЕ-2

1р1 J

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

—=л

сист д 5

осреднённый квадрат времени пребывания заявки в системе

_2_

Дд

RPHO + РРНЗН + P1 ^ m + 1 ]РПЗН

+

1

+—< д

1

д

E + 1ГE -1

2т£_((1 + т - р)Рнзн - EPm+E) - E( + E + 1)P,

m-p

m+E

+ 1 рНЗН, p = m

} +

+

1

Дд

2p1

1

m m -p1

Рпзн + E

m+E

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

a2 = t2 -1

сист сист сист

Имитационное моделирование СМО данной архитектуры в системе GPSS World [12] показало, что при произвольно заданных значениях числа обслуживающих устройств m и ограничения длины очереди Е в выходном потоке обслуженных заявок наблюдается преобладание требований одних типов над заявками других типов. Задача оптимальной организации обслуживания заключается в том, чтобы по известным в качестве исходных данных интенсивностям входных потоков заявок всех типов и заданным требованиям к производительности СМО по каждому типу заявок рассчитать необходимое число обслуживающих устройств, а также ограничение по длине очереди для заявок 2-го типа. Для этого абсолютную пропускную способность СМО представим в виде трёх слагаемых, каждое из которых представляет собой количество обслуженных заявок определенного типа.

Д = Лрно + ^РНЗН + ^1РПЗН = ^ 1 (Рно + Рнзн + Рпзн ) +

+ ^2 (НО + РНЗН )+ ^3РНО = Д1 + Д2 + Д3 .

2

t

сист

Поскольку заявки 1-го типа обслуживаются при любых обстоятельствах, то задать требуемую производительность можно только для заявок 2-го и 3-го типов. Из последнего

/Д3 = Х 3РНО

выражения следует <

[Д2 = X 2

/Чз = РНО

или, в относительных единицах, < .

№ = РНО + РНЗН

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

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

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

Литература

1. Кирпичников, А.П. Открытая одноканальная система массового обслуживания с отказами и неограниченной очередью / А.П. Кирпичников, А.С. Титовцев // Вестник Казан. технол. ун-та. - 2006. -№4. - С. 78 - 85.

2. Кирпичников, А.П. Многоканальная система массового обслуживания с отказами / А.П. Кирпичников, И.Н. Валеев // Вестник Казан. технол. ун-та. - 2006. - №4. - С. 66 - 70.

3. Кирпичников, А.П. Замкнутые модели систем массового обслуживания с ограничениями / А.П. Кирпичников, Р.Ф. Гильмутдинов // Вестник Казан. технол. ун-та. - 2006. - №4. - С. 220 - 223.

4. Клейнрок, Л. Теория массового обслуживания / Л. Клейнрок. - М.: Машиностроение, 1979. - 432 с.

5. Ивченко, Г. И. Теория массового обслуживания / Г.И. Ивченко, В.А. Каштанов, И.Н. Коваленко. - М.: Высшая школа, 1982. - 256 с.

6. Альянах, И.Н. Моделирование вычислительных систем / И.Н. Альянах. - Л.: Машиностроение, 1988. - 224 с.

7. Вентцель, Е. С. Теория вероятностей / Е.С. Вентцель. - М.: Academia, 2005. - 576 с.

8. Cohen J.W. Certain Delay Problems for a Full Availability Trunk Group Loaded by Two Sources / Communications News. - 1956. Vol. 16, - P. 105 - 113.

9. Саати, Т. Элементы теории массового обслуживания и её приложения / Т. Саати. -М.: URSS, 2010. -520 с.

10. Кирпичников, А.П. Прикладная теория массового обслуживания / А.П. Кирпичников. Казань: Изд. КГУ, 2008. - 118с.

11. Тихоненко, О.М. Модели массового обслуживания в информационных системах / О.М. Тихоненко. -Минск.: Технопринт, 2003. - 328 с.

12. Боев, В.Д. Моделирование систем. Инструментальные средства GPSS WORLD / В.Д. Боев. - СПб.: БХВ-Петербург, 2004. - 360 с.

© А. П. Кирпичников - д-р физ.-мат. наук, зав. каф. интеллектуальных систем и управления информационными ресурсами КГТУ, kirpichnikov@kstu.ru; А. С. Титовцев - ст. препод. той же кафедры, notna6683@mail.ru.