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

УДК 007:681.518.2

Г. А. Попов

СООТНОШЕНИЯ ДЛЯ ХАРАКТЕРИСТИК МНОГОКАНАЛЬНЫХ СИСТЕМ С ПУАССОНОВСКИМИ ПОСТУПЛЕНИЯМИ

Исследуется один из частных классов многоканальных систем - системы с пуассонов-ским входящим потоком. Предположение пуассоновости входящего потока является типичным для многих моделей. Для указанных систем получены рекуррентные соотношения для преобразований Лапласа - Стильтеса совместного распределения длин очередей, остаточных времен обслуживаний и периода занятости, которые позволяют выразить эти характеристики через их маргинальные значения: через совместное распределение остаточных об-служиваний и периода занятости в моменты начал обслуживаний и в моменты поступлений вызовов, когда в системе нет очереди, точнее, не все приборы заняты. Таким образом, проблема анализа многоканальных систем с пуассоновскими входящими потоками сводится к проблеме нахождения маргинальных характеристик указанной системы. Через описанную характеристику системы выражаются все другие ее характеристики. Для каждого момента начала обслуживания вводится параметр: вектор номеров обслуживающих приборов, компоненты которого расположены в порядке возрастания длительностей остаточного обслуживания на соответствующих приборах - вектор порядка освобождения. Получена система интегральных соотношений, связывающая характеристики системы для всех векторов порядка освобождения приборов между собой.

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

Введение

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

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

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

Данная работа обобщает работу [1] на случай произвольного числа приборов. Приведем точные определения.

Рассматривается система массового обслуживания Ml G I r I да (r> 1) с дисциплиной FIFO обслуживания вызовов, т. е. в СМО, состоящую из r обслуживающих приборов, поступает пуассоновский поток вызовов; процессы поступлений и обслуживаний разных вызовов независимы в совокупности и независимы между собой; нет ограничений на процесс ожидания; длительности обслуживаний вызовов произвольны. Поступившие вызовы в случае занятости всех приборов становятся в очередь и в дальнейшем выбираются на обслуживание в порядке их поступления.

Пусть a > 0 - интенсивность поступлений вызовов; Bi (t) (Bi (+0) = 0) (1 < i < r ) - функция распределения длительностей обслуживаний вызовов на i-м приборе; pi - вероятность того, что при поступлении в свободную систему вызов выбирает для обслуживания i-й прибор

r

(^ pt = 1). Предполагается, что при занятости части приборов вызов выбирает для обслужива-

i=1

ния i-й прибор с вероятностью, пропорциональной pt.

Обозначим через В(г)(г,s,х) (0 < г < 1; 5 > 0; х = (х15х2,...,хг)) вероятность того, что в стационарном режиме, в момент окончания обслуживания +0 на 7-м приборе, в системе нет синих вызовов, с начала периода занятости (ПЗ) не было 5-катастроф, ау-й прибор для у Ф 7 (1 < у < г) будет

занят в течение времени, меньшем ху- (по поводу использования определений см. [2, 3]). Здесь

под ПЗ понимается промежуток времени, начинающийся с момента, когда в свободную систему (т. е. свободны все приборы) поступает вызов, и заканчивающийся первым моментом, когда все приборы свободны.

_ ад ___

Очевидно (см. [2, 3]), что В(г)( г, 5, х) = Е гкРк(г)(5, х), где Р/7)(5, х) определяется аналогично

к=1

В^7)(г, 5, х) с заменой требования отсутствия г-синих вызовов на следующее: в системе имеется

к вызовов. Функция В(г)(г, 5,х) (или, что то же самое, набор { Рк(г)(5, х), к > 0 }) однозначно определяет состояние системы в произвольный момент времени в стационарном режиме. Отметим, что при к < г в очереди нет вызовов, при к < г число компонентов у вектора х меньше г (равно к). Введем обозначения (Re X > 0; |г| < 1; Яе5 > 0 ; 7 = 1, г):

ад

Р7(5) = 1 е (¿); е{ = (0,0, ... ,1,0, ... 0) е В; если а = (а1,а2, ... ,аг) есть переста-

0 7

новка чисел

и а57 = (а7, а1, а2, ... , а7-1, а7+1, ... , аг) .

Далее, полагаем (т = (т1, т2, ... , тг); Хт = Х1т1 + Х2 т2 + ... + Х г тг)):

га (г, 5, Ха ) = |...{ в-Хт ГКЧЯ <а1)(г, 5, Т)ГГ Х(хак-1 <Так );

т7 >0,7Фа1 к=2 к=2

г г

Ра (5, Ха ) = |...{ в-Хт П d%^(s, т)Пх(Так_1 < Так );

т7 >0,7Фа1 к=2 к=2

(5, Ха ) = 14 в"Хт П т)Их(Хак-1 < Ч );

т7 >0,7Фа1 к=2 к=2

( ра(п-л) ^ , ( 1

V*

где Q^aJ)(s,x) определяется аналогично Рг^а11)(5, т), только соответствующие события рассматриваются не в момент окончания обслуживания, а в момент поступления вызова. Основной результат работы следующий.

Теорема 1. Для любой перестановки а = (а1,а2, ... ,аг) чисел (1, 2, ... ,г) справедливо соотношение (ЯеХ>0; |г| < 1; 5 > 0):

1 ад d

Vа (г, 5, Ха ) = — | —К (г, 5, Ха + 7^2) - VаSг(z, 5, Ха52 а + (7? + (П-Л )е2) +

2П -ад

г Г

+ Е ^5' ,

'=3

где при вычислении интеграла точка ^ = 0 обходится снизу (в комплексной плоскости);

г

Л = Е ^к; П = 5 + а - аг; ву есть г-мерный вектор, у которого все компоненты равны нулю, кро-

к=1

ме у-й, которая равна единице.

Доказательство теоремы 1. Введем в рассмотрение вспомогательную функцию ф^ (п, т, х) (7, 7 = 1, г ; т = (т1; т2, ... , тг); х = (х1; х2, ... , хг); п> 0): Ф^ (п, т, х) есть вероятность

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

Выпишем соотношения для вероятности ф^ (п, т, х), воспользовавшись методом введения

дополнительных событий [2, 3]:

- при 7 = ]

ад

Ф]}

0 к:кФ ]

- при 7 Ф7

_ _ ад

ф;, (п, т, 7) = П Х(0 <тк-т < 7к) е"^ [В; (тг +7}) - В} (тг )]{ dB] ^)Х(0 <тк - V, к Ф 7).

к:кФ 7,7 0

Предположим, что Р7

1 7 М-^) ,,

В (х) =

е

2п7 -7ад £

Из (1) получаем (I = 1, г ) (см. [1]):

__1 ад ад

Ф„

2П-ад 0

____1 ад 1 - е~7&7

Ф;7

кФ,,7 2П -ад 7Ь

Упорядочим {77,7 = 1,г } по возрастанию: 0 = 7 <7 < ... <7а и для а =

положим ^а = (^а1,^ ••• ,V ), 'а = (7а^7а2 , ••• ,7аг )-

Выпишем уравнения для функций га (г, s,Xа), для чего вначале выведем соотношения для функций Я1) (г, s,7).

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

1. В предыдущий момент окончания обслуживания система находилась в состоянии, описываемом вероятностью Я( 7)(г , s, т), и все приборы были заняты (вероятность этих событий равна (Я(;)(г,s, т) - р-^,!))гг-1); далее произошел переход из этого состояния в состояние,

описываемое вероятностью Я \г, s,7), и за время перехода не было s-катастроф и г-синих вызовов, т. е. не было (s + а(1 - г) )-катастроф (вероятность ф71 (5 + а(1 - г), т,7)). Просуммировав по

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

г 1 г _ _ _-. __

I- |•••{ П d%k [Я0)

7=1 г тк >0,кФ7 к=1,кФ7

2. В момент поступления последнего вызова в системе был свободен у-й прибор, а остальные приборы заняты, все вызовы красные, а поступивший вызов оказался красным (вероятность

QГ-|(s, т)гг 1г); затем произошел переход в состояние, описываемое вероятностью В1(1 г, ') (вероятность фу (п, т, ')). Сняв окраску обслуженного вызова, приходим к следующему выражению для искомой вероятности:

г г

у=1 тк >0,кФу к=1,кФу

Из

Е I4 П т)гг-1ф;7

_ 1 г Г _ _ _ _ __

В(1)(г,5,г) = -Е IП dТк [в(у)(г,5,т) -Р^,т)гг-1 ]ф;7(п,т,') +

г у=1 тк >0,кФу к=1,кФу

+Е 14 П фг-1ф;7

у=1 тк >0,кФу к=1,кФу

Найдем преобразование Лапласа - Стильтеса по г обеих частей равенства (6). Из (2) имеем:

def г , ч г г _ __1 ад

/а, = М е-Х"г"Пх(гак - < ^ак )П d Ч I-1 П ^ т1фа1а1(n, T, О = ^НО X

га. >0,7>2 к =2 к =2 ^ >0,кФ"1 к=2

Г _ _г . . Г

IП^/^(г,5,т) I |е-Ха'аПх(^- < Ч )Пх(Тк - V < 'к) =

тк >0,кФа! к=2 v>0, ^ >0,кФа! к=2 к=2

0^ Фа1

1 ад г _ ЕХк г

а Г -»с- г .о. ч Г Г Т-Г •» т-^ГУ. г ч Г •» _ Л'?-I-П

' __И И  к ' у

= — I d^alM;) I...| П^/^(г,5,т) I dve^+r1v • е кФа1 Пх^- <так) ,

2П 0 тк >0,кФа1 к=2 v>0, к=2

0^Фа1

где X а'а - скалярное произведение векторов Ха и 'а. Отсюда на основе определения функций га (г, ) получаем:

1 ад г _ Г т"2

/а1 = -1- I ^^М;) I ...I П ^В^, 5, т)Пх( 'ам < Ч )' е"^ I е"^-^ =

2П-ад тк >0,к Фа1 к=2 к=2 0

Г - Г , ч 1 _ е-№+п-Л)та2

' 1 Г 1 е

1 ад г _ Г , ч

= — I ^Н*) I ...I П d т„кВ (а1)( г, s, т)Пх(так-1 < так ) . + п Л

2П-ад тк >0,кФа1 к=2 к к = 2 + п - Л

1 ад га

= I d^Pа1

где Л= Е К . ^^ к

к Фа1

Далее, подобным же образом из (3) получаем:

г , , г г . Л

ХАПх

ак >и,к >2 к=2 к=2 тк >0,к Фа у

ж/ г , г г __ 1 ад

^ = |...| < 'ак )П d Ч И П ^ 5 ^(п т, Ц = -- I ^ X

г„, >0,к>2 к=2 к=2 тк>0,кФа,к =1,кФа, ^ -ад

I...I П d%kВ '')(г,5,т)• ^I...Iе-х«'«Пх('ак-1 <'"к)"* Х(т"к -т„1 <^) =

тк >0,к Фа у к=1,к Фа у Тк >0,кФау к=2

г

1 ад r __Г -к

1 J HS) J...J П ^ )(z, s,T) • J...Je"^ Пх(^ < tai). e^dt, x

Tk >0,k^aj k=1,k^aj Tk >0,i^aj

o™ J "-j 4 J J -»-A ik J J AA»^ U-k-1 k

-ад Tk >0,k^a, k=1,k*a . Tk >0,fc¿a, k=2

П X(T«k "4 < 4 ).

k*U k k

Отсюда следует (тг+1 = + ад):

1 ад r _

/aj = — J ^Pa,

2n

-ад Tk >0,k*ajk=1,k*aj k*1,j

ад

exP{- Z "ak (Tak "Ta1 - (¡S + ЯК^ J e ^^ ^ X(Ta ^ - Ta1 < taj < - Ta1 ) :

k*W 0 j

= 2- J ^Pa, (-S) J ...J П dTiR(aj )(z, S, T) • П X(Tak 1 <Tak ) • ^ ^

a.-,, ..... п ~Tk" v-S,T) .ПХ(Та,<Та ) • e ' X

-ад

0,k^Uj '

eXp{-Ta (¡S + "a. )} - expí-la (¡S ++ "a. )} - Z 4V -a-№+4- Z V K.+O'S+Aa , )T

k

¡S + "a,

Тогда последние соотношения можно переписать в следующем виде:

1 ад

/aj = 2" J d^Paj (-¡S){raSj a + (Я - A)e2 + (¡S + "a, )ej ) -

2п -ад

- ras,

Аналогично доказывается соотношение

r r r

1

J...J Пe~Xínx(V, <tai) J...J ПT)R)(z,s,^(n,t,t) = — J ^(-S) x

k>0,k>2 k=2 k=2 Tk>0,k>2 k=2 2П -ад

.. Pa К ) - Pa

¡S + n-Л

X

r r r r ____1 адР„

X J...J Пe""nX(tak-, < tak )Пdtat J...J П ^)(S,Т^^П,T t) = - J dSX

tt >0,k>2 k=2 k=2 k=2 Tk>0,k>2 k=1,k2П-ад ¡S + "a

X {PaS,

j j j J j j

Совершенно такие же соотношения справедливы и для )(5,т) с заменой Ра С?Д) на да (5,Х).

Из определения функции га (г, ) и из (6)-(9) следует:

га (г, ) ^ Ра1(-7^) | га (г,^а ) - га (г; ^а Л7^ + п - Л)е2) +

2п -ад -[ z

-1 0

¡S+n-Л

vPa,

+ Z---X

j >1 ¡S + "a,

x

x

x>

+zr

raS,

aS j'^j+1'

+

+ea8,

VS ¡^j+U

1

где öa (^ S,Xa ) = 4a (s' Xa )--Pa (s> Xa ) •

Так как при Ren > ReЛ функции (»S + n— Л) 1 и ra(z,s,»S + т) (Rex > 0) аналитичны

в области { S : Im < 0}, а функции ßk (—/£,) (к = 1, r ) аналитичны в области { S : Im > 0}, то при Re Л < Ren имеют место соотношения

1 "7 ra

W dSßa^—Ф Л = ra (Z, S, Xa S

1 z (»S + n — Л) a z

1 7 ea

2П—L^^ßa' (—/^ »¡ + n —Л = ^ (z>S' Xa )ßa! (П — Л);

_1_ +J d § r^^) = 0;

2п —ж /^ + П — Л

-1 +f dS raSk (z,S,^ + T) = 0.

2n —L 7^ + n —Л

Из (10)-(14) следует:

ra

Г1 ßa, (n — Л) ^

1 +L

—ßai(n—Л)еа (z, S, Xa ) zr—1 = — J d S

1 —LHl

ßa HS)'

X ra (z, s, Xa + (/% + n — Л)^) — zr—1ßa1 (—»SPa (z, s, Xa + (/% + П — Л)^)]

—E

j >1 »S + XaS

1 — -

ßa

J + n — Л

raS, (Z' S' XaS, a + (n — Л)е2 + (/'S + Xa, ) —

—^'öaS (z, S, XaS a + (л — Л>2 + (»S + Xa )}

J J J J

- <

1 —-

ßa HS)'

X raS, (Z' S' XaS а + (n — Л)е2 + (/'S + Xa, )ej+1 ) —

—zr—1ßa1 (—/S)eaS, (Z' S' XaS а + (n — Л)е + + \ ^j^}

В полосе 0 < 1тЯе(п-Л) все подынтегральные функции аналитичны. Поэтому, воспользовавшись определением функции va (г, 5,Ха), из (15) получаем

1 +L 1

^ Н S,Xa ) =— J d S(Va (Z' S' Xa + + n — -- —

2n—L /S + n —Л

E (VaS, (Z' ^ XaS, a + (n — Л)е2 + (»S + Xa, )ej ) — VaS, (Z' S' XaS а + (Л — Л)е2 + 0'S + Xa, )ej +1) ' XC/ < r)) X

X

z

z

X

z

z

L

1

z

X

z

1 I 1 1 г ,

-$ = I А (г'5' Ха + Ке2)~.--ХД уа8, 5 а + (П - Л)е2 + Ке] ) -

"^а] ' 2П-со ]=^ ' '

-уа5 ] (г, 5, ] а + (п - Л)е2 + Ке]+1)) ,

где в интеграле по д точка д = 0 обходится (в комплексной плоскости) снизу, и полагаем:

^а5г (^ 5 V а + (П - Л)е2 + 7дег+1) =

Из (16) после перемены порядка суммирования под интегралом получаем утверждение теоремы.

Из теоремы 1, аналогично [1], выводится утверждение теоремы 2.

Теорема 2. Для любого набора а справедливо соотношение

V*

Частный случай соотношения (17) при г = 2 приведен в [1].

Заключение

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

СПИСОК ЛИТЕРА ТУРЫ

1. Попов Г. А. Взаимосвязь общих и маргинальных характеристик состояния двухканальной системы с простейшим потоком поступления вызовов / Вестн. Астрахан. гос. техн. ун-та. Сер.: Управление, вычислительная техника и информатика. 2017. № 3. С. 7-19.

2. Гнеденко Б. В. и др. Приоритетные системы обслуживания. М.: Изд-во МГУ, 1973. 448 с.

3. Климов Г. П. Стохастические системы обслуживания. М.: Наука, 1966. 242 с.

Статья поступила в редакцию 04.10.2017

ИНФОРМАЦИЯ ОБ АВТОРЕ

Попов Георгий Александрович - Россия, 414056, Астрахань; Астраханский государственный технический университет; д-р техн. наук, профессор; зав. кафедрой информационной безопасности; popov@astu.org.

G. A. Popov

RELATIONS FOR CHARACTERISTICS OF MULTI-CHANNEL SYSTEMS

WITH POISSON ACCIDENTS

Abstract. The article describes a special class of multichannel systems with Poisson incoming flows. The assumption of poissonity of the incoming flow is typical for many models. For these systems there are found recurrent relations for Laplace-Styltjes transformations of joint distribution of the queue lengths, residual time of services and a busy period, which allow to express these characteristics through their marginal values: joint distribution of residual services and a busy period at the moment of the beginning of services and in the moments of calling-in, when the system has no queue, or rather, not all devices are busy. Thus, the problem of analysis of multi-channel systems with Poisson incoming flows is reduced to the problem of finding marginal characteristics of the specified system. All other system characteristics can be expressed through the described characteristics of the system. For every moment of the service beginning there is introduced a parameter: the vector of the numbers of servicing devices, components of which are arranged in the increasing order of residual duration of service on the respective devices - the vector of order release devices. The obtained system of integral relations, linking the system characteristics of all vectors of the order of release of the devices among themselves.

Key words: queuing system, multichannel systems, simple incoming flow, precise ratios.

REFERENCES

1. Popov G. A. Vzaimosviaz' obshchikh i marginal'nykh kharakteristik sostoianiia dvukhkanal'noi sistemy s prosteishim potokom postupleniia vyzovov [Interrelation of the common and marginal features of a two-channel system with a simple flow of incoming calls]. Vestnik Astrakhanskogo gosudarstvennogo tekhnicheskogo universiteta. Seriia: Upravlenie, vychislitel'naia tekhnika i informatika, 2017, no. 3, pp.7-19.

2. Gnedenko B. V. i dr. Prioritetnye sistemy obsluzhivaniia [Priority serving systems]. Moscow, Izd-vo MGU, 1973. 448 p.

3. Klimov G. P. Stokhasticheskie sistemy obsluzhivaniia [Stochastic serving systems]. Moscow, Nauka Publ., 1966. 242 p.

The article submitted to the editors 04.10.2017

INFORMATION ABOUT THE AUTHOR

Popov Georgiy Aleksandrovich - Russia, 414056, Astrakhan; Astrakhan State Technical University; Doctor of Technical Sciences, Professor; Head of the Department of Information Security; popov@astu.org.