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

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

УДК 519.872

А. П. Кирпичников, А. С. Титовцев

ОТКРЫТЫЕ СИСТЕМЫ ДИФФЕРЕНЦИРОВАННОГО ОБСЛУЖИВАНИЯ ПОЛИКОМПОНЕНТНЫХ ПОТОКОВ

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

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

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

A mathematical model of queuing systems of new type: open multichannel system of difference service of polycomponent flows is presented. Detailed mathematical formalization of this model in a quasistationary mode of functioning is performed.

В настоящей работе изучена математическая модель открытых систем массового обслуживания (СМО), сочетающая в себе многоканальную модель Эрланга (M/M/m/0), классическую модель многоканальной СМО (M/M/m), а также модель многоканальной СМО с ограниченной очередью (M/M/m/E). СМО, встречающиеся в повседневной практике, зачастую представляют собой сложные системы, имеющие во входном потоке требования разных типов. При проектировании объектов массового обслуживания с целью их правильной организации необходимо исследование методом математического моделирования. Известные на сегодняшний день классические модели СМО не позволяют в полной мере описать реальные объекты. Практический интерес имеют более сложные модели, являющиеся комбинациями ранее известных моделей СМО [1 - 3]. В этой связи авторами была предложена модель открытой многолинейной СМО, граф состояний которой впервые был опубликован в работе [4] (рис.1).

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

общих зависимостей для вероятностных, числовых и временных характеристик СМО в установившемся режиме работы. Установившимся считается такой режим работы СМО, когда система бесконечно блуждает по всем возможным состояниям, но математические ожидания её числовых и временных характеристик остаются постоянными во времени. Первая и единственная известная авторам попытка математического описания работы комбинированных систем массового обслуживания была предпринята в работе [9], однако её автор, ввиду трудности задачи, ограничился лишь исследованием комбинации модели Эрланга и классической многолинейной СМО, менее интересной с точки зрения возможных приложений [10]. В настоящей работе формализация модели осуществлена по общей схеме, разработанной в монографиях [11, 12].

Предположим, что рассматриваемая

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

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

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

второго типа получает отказ и выбывает из системы необслуженной;

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

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

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

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

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

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

X.. Я2 X.,

Рі =—; Р2 =—; Рз =—;

л

К = — =Р1 +Р2 + Рз.

л

л

X

Р = — = Р1 +Р2-л

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

вт (т + -

т!

Р

т-Р

Б + —

1-

Р1

Р1

т-Р1

Р ф т

т - Р1

Р = т

т К1

где вт (К) = У^- - неполная экспонента и ве-

і=0

роятности состояний СМО в квазистационарном режиме функционирования

К

Рі

—Р0, 0 < і < т

! 0’

~ У-т о Р І К

Р0, т < і < т + Б

Р1 І (РІБкт

т) т!

і-т-Б / ч Б

т

т) т!

Р0, і > т + Б

Для дальнейших расчётов удобно ввести также следующие базисные вероятностные характеристики СМО: вероятность неполной за-

грузки накопителя

т+Б-1 рт

Р = У Р = —- Р

1 и'зи / 1 і - 1 0

т!

НЗН ^ 1 і

і=т

1 -і-*-т

1 --Р-

т

Б, р = т

РФ т.

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

• \ Б

Р = У Р = — Р ^т'

рпзн - т! Р0

і=т+Б

вероятность немед-

1 -

т

Б

Б

+

т

Р0 =

Б

ленного

т—1

обслуживания

РНО = У Рі = Єт—1 (R)P0 ;

і=0

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

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

РНЗН + РПЗН + РНО = 1 . Формулы основных числовых характеристик системы такого рода, выраженные через её базисные вероятностные характеристики, имеют следующий вид,

Вероятность ожидания обслуживания заявкой в очереди Рож = р Рнзн +-^1Рпзн ; вероят-

К к

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

к

к — р1 к

Рп

П2 = К2

средняя

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

I =

р

т—р Е +1

(РНЗН ЕРт+Е)’ р ф т

2

Рнзн, р = т

+ р1

т т— р..

Р

ГПЗН’

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

I2 =

р т + рг

т — р т — р

6

Рнзн — Е Е +

2т

т — р

р ф т

Рнзн . р = т

+ р.

т т — р1

2Е +

т + р1

т — р

1

Р

ГПЗН>

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

к = КРно +

[(1 + т р)Рнзн ЕРт+Е ] рф

т — р

т

Е +1,0

т+ — Рнзн. р = т

!> +

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

к2 = к2 (Рно — Рт—1 ) + К(Рно + тРож ) +

т — р

1^2т + т+рІРнзн — Е Е + 2т| 1+ 1 I Р г т+Е , рф т

т — у _ 1 т—р/

' 2Е +1^

т + 6 ІРнзн, р = т

относительная пропускная способность системы я = 1- ротк; абсолютная пропускная способность системы А = ЛРНО +ХРНЗН +Х1РПЗН;

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

П = ^НО + РРНЗН + Р1РПЗН = ^(РНО + Рож ) осреднённый квадрат числа требований, находящихся под обслуживанием

+ р1

Е2 1

— + 2Е +—— т т —р

^т + р1 ^

2(т + Е)1 1

т — р

1 У

ПЗН’

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

I— п 1;

лом I обсл = — = —  осреднённый квадрат вре-

А ц

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

обсл ц2

Р

Е

+

Р

+

+

Р

НЗН

отк

ния заявкой в очереди t ожид = —; осреднён-

\_

Л'

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

t2 = -

ожид Л

1

ц(— - р) E2 -1

2-Р-(зн -EPm+E)-E(E + 1)P„ п -р

3—ц

РНЗН > р = —

Лц

2р1 1

^ m m-р1 J

РПЗН + E(E + 1)Р—

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

РожІМ--1©-"

Pi

( г

( e=-i(^it))+

—-р —-р] J

р

— -р1 — -р

-) eE-1 Пt)

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

р Дії

де

пускную способность СМО представим в ви-1+5] трёх слагаемых, каждое из которых пред-

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

А = ЛРНО + ^РНЗН + ^1РПЗН = ^1 (РНО + РНЗН + РПЗН )^ + Х 2 (РН0 + РНЗН )+Х зРНО = А1 + А 2 + Аэ-

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

[Л3 = X 3РНО

[Л2 = X2

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

^ожид

XeE-2(Xt)+X.|[ —| (ем -eE-2(X1t

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

= —; осреднённый квадрат времени пре-

А

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

t

F" = 2

сист

Лц

^РНО +рРНЗН +р11 — + 1 |РПЗН

1

Ц— -р)

E+1|E ц ^ 3m

1

2—4(1+—-р)Рнзн-ВР—* )( + E+1)Р-— -р

рФ —

1+1!:рн,

Лц

2р1

р = —

1

— — -р1

РПЗН + E(E + 1)э m

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

или, в

jq3 = РНО

[q2 = РНО + РНЗН

относительных

единицах,

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

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

1

+

q

+

E

+

+

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

Литература

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

2006. - № 4. - С. 78 - 85.

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

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

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

2007. - Т. 14 - Вып. 5. - С. 893 - 896.

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

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

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

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

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

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

2010. - 520 с.

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

12. Кирпичников, А.П. Методы прикладной теории

массового обслуживания / А. П. Кирпични-

ков. Казань: Изд. КГУ, 2011. - 200с.

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

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

15. Кирпичников, А.П. Методика оптимальной организации систем массового обслуживания с отказами и очередью. / Кирпичников А.П., Титовцев А.С. // Обозрение прикладной и промышленной математики. - 2008. - Т. 15 - Вып.

6. - С. 1090 - 1091.

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

2011. - Т. 14, № 5. - С. 154 - 162.

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