Research of streams in system M|GI|? with repeated references the method of limiting decomposition..pdf В классической теории массового обслуживания существует не так много моделей, исследование которых удаётся выполнить аналитическими методами и получить окончательные результаты в виде формул для вероятностно-временныххарактеристик исследуемых систем. Это, прежде всего, марковские системы, процесс изменения состояний которых определяется цепями Маркова, то есть дискретными марковскими процессами [1], однолинейные полумарковские системы, исследование которых реализуется методом вложенных цепей Маркова [2], в частности, известна формула Поллачека - Хинчина [3], а также формулы Эрлангадля N-линейных систем с произвольным временем обслуживания [4], процесс изменения состояний которых является немарковским и даже немарковизируемым.В этих моделях входящие потоки определены классом стационарных пуассоновских либо рекуррентных потоков [5].В то же время многочисленные исследования реальных потоков в различныхпредметных областях, позволили сделать вывод о существенной неадекватностиклассических моделей потоков (пуассоновских и рекуррентных) реальным данным. Например, потоки обращений в торговые или страховые компании [6]. При построении математических моделей таких компаний нужно учитывать, что потокклиентов, повторно обращающихся в ту же компанию, очевидно, не является пуассоновским. Построению и исследованию математических моделей таких потоков в СМО с экспоненциальным временем обслуживания посвящены работы [6 -10]. Вместе с тем, исследованию потоков в СМО с неограниченным числом обслуживающих приборов с произвольным временем обслуживания, а также многофазных СМО уделяется мало внимания. Для анализа таких систем разработкановых методов исследования несомненно является актуальной.В настоящей работе предлагается метод предельной декомпозиции [11] для анализа потоков в СМО с неограниченным числом обслуживающих приборов и повторным обращением.1 Работа выполнена при поддержке АВЦП «Развитие научного потенциала высшей школы (2009 -2010 годы)» Федерального агентства по образованию РФ по проекту «Разработка методов исследования немарковских систем массового обслуживания и их применения к сложным экономическим системам и компьютерным сетям связи».Исследование потоков в системе M|GI|∞ с повторными обращениями 571. Постановка задачиРассмотрим систему массового обслуживания (СМО) с неограниченным числом обслуживающих приборов, на вход которой поступает простейший с параметром ƒ поток заявок. Время обслуживания на каждом приборе имеет произвольную функцию распределения B(x), одинаковую -----для всех приборов. Заявка, завершившая обслуживание, с вероятностью 1 - r покидает систему, а с вероятностью r обращается к системе для повторного обслуживания (рис. 1).Ґлn(t)B x ( )B x ( )B x ( ) r r 1 - r r 1 - r Рис. 1. СМО с неограниченным числом приборовс повторными обращениями заявокСтавится задача исследования суммарного s(t) и двумерного {ƒ(t), n(t)} потоков в рассматриваемой системе, где n(t) - число повторных обращений, реализованных за время t, v(t) - число первичных обращений реализованных за время t, s(t) = Ґн(t) - n(t) .2. Метод предельной декомпозицииДля решения поставленной задачи предлагается метод предельной декомпозиции [11]. Суть этого метода заключается в следующем.Входящий пуассоновский поток делится на N независимых простейших потоков с параметром ƒ ⁄ N, заявки каждого потока направляются для обслуживания на соответствующий прибор. Таким образом, получаем совокупность N независимыходнолинейных СМО. Будем полагать, что эти СМО с отказами (рис. 2). То естьновая заявка, поступившая в систему, занятую обслуживанием, теряется.B(x) r 1 - r Ґл/NРис. 2. Однолинейная СМО с отказоми повторными обращениями заявокПри N → ∞ вероятностью потерь заявок можно пренебречь, и тогда суммарные характеристики совокупности N однолинейных СМО сходятся к характери58 С.П. Моисеева, И.А. Ананина, А.А. Назаровстикам исходной модели. Таким образом, задача нахождения распределения вероятностей числа обращений в бесконечнолинейной СМО сводится к решениюзадачи нахождения распределения вероятностей числа обращений в однолинейной СМО с отказами.3. Исследование однолинейной СМО с отказамии повторным обращениемОбозначим s(t,N) - число обращений, реализованных за время t в однолинейной СМО. Тогда P(s,t) = P{s(t, N) = s} - распределение вероятностей суммарного числа обращений к прибору за время t.Введем следующие обозначения: k(t) - состояние прибора, 0 прибор свободен, ( )1 прибор занят; k t ⎧ − = ⎨ − ⎩z(t) - длина интервала от текущего момента времени t до момента окончаниятекущего обслуживания, если прибор занят, то есть k(t) = 1 ; P1(s, z,t, N) = P{k(t) = 1, z(t) < z, s(t, N) = s} - вероятность того, что суммарноечисло обращений равно s, прибор занят и до конца обслуживания остается времени меньше z; P0 (s,t, N) = P{k(t) = 0, s(t, N) = s} - вероятность того, что суммарное числообращений равно s и прибор свободен.Составим ҐДt-методом прямую систему дифференциальных уравнений Колмогорова [12]. По формуле полной вероятности запишем равенстваP0 (s,t t, N) P0 (s,t, N)(1 t) (1 r)P1(s, t,t, N) o( t); N Ґл - ҐД = − ҐД - − ҐД - ҐД P1(s, z − ҐДt,t - ҐДt, N) = P1(s, z,t, N) − P1(s,ҐДt,t, N) - P1(s −1,ҐДt,t, N)rB(z) P0 (s 1,t, N) tB(z) o( t)NҐл- − ҐД - ҐД .Откуда получаем систему дифференциальных уравнений0 10( , , ) (1 ) ( , 0, , )( , , )P s t N r P s t N P s t N t z N ЎУ − ЎУ Ґл = −ЎУ ЎУ; (1)1( , , , ) 1( , , , ) 1( ,0, , ) 1( 1,0, , )( )P s z t N P s z t N P s t N rB z P s t N t z z z ЎУ ЎУ ЎУ ЎУ −= − - ЎУ ЎУ ЎУ ЎУP0 (s 1,t, N)B(z)NҐл- − . (2)Рассмотрим функции0 ( ) 0 ( )0s , , , , n x P s t N H x t N ЎДҐТ = ; (3)1 ( ) 1 ( )0s , , , , , , n x P s z t N H x z t N ЎДҐТ = . (4)Тогда из (1), (2) следует, что H1(x, z,t, N) и H0 (x,t, N) удовлетворяют системедифференциальных уранений в частных производных первого порядка [13]: Исследование потоков в системе M|GI|∞ с повторными обращениями 590 10( , , ) (1 ) ( , 0, , )( , , )H xt N r H x t N H x t N t z N ЎУ − ЎУ Ґл = −ЎУ ЎУ, 1 1 10( , , , ) ( , , , ) ( ,0, , )( ( ) 1) ( ,, ) ( )H x z t N H x z t N rxB z H x t N H x t N x B z t z z N ЎУ ЎУ ЎУ Ґл − = − ЎУ ЎУ ЎУ, решение которой будем искать в виде20 0H (x,t, N) 1 1 F (x,t) (N )N= - - Ґп − ; (5)21 1H (x, z,t, N) 1 F (x, z,t) (N )N= - Ґп − . (6)Тогда уравнения для F1(x, z,t) , F0 (x,t) имеют вид 0( , )(1 ) ( , )F x t r h x t t ЎУ= −Ґл - −ЎУ; (7)1( , , ) 1( , , )( ) ( ( ) 1) ( , )F x z t F x z t xB z rxB z h x t t z ЎУ ЎУ− =Ґл - −ЎУ ЎУ, (8)где h(x,t) = ЎУF1(x,0,t) ЎУz .Решение дифференциального уравнения первого порядка в частных производных первого порядка (8) определяется решением системы обыкновенных дифференциальных уравнений для характеристических кривых [13]11 1 () ( () 1)(,)dt dz dF xB z rxB z h x t = − Ґл - −.Найдем два первых интеграла этой системы. Один из них найдем из уравнения−dt = dz .Отсюда, z = C1 − t . (9)Другой первый интеграл находим из уравненияdF1 = [ҐлxB(z) - (rxB(z) −1)h(x,t)]dt .Откуда, подставляя (9), получаем равенство1 2 [ 1 ]0( ) ( ( ) 1) ( , )tF = C - Ўт ҐлxB z - rxB C − s − h x s ds которое перепишем в виде1 1 [ 1 1 ]0( , , ) ( ) ( ) ( ( ) 1) ( , )tF x z t = ҐХ C - Ўт ҐлxB C − s - rxB C − s − h x s ds , или, учитывая, что С1 определяется из равенства (9), общее решение F1(x,z,t)уравнения (8) запишем следующим образом: 1 [ ]0( , , ) ( ) ( ) ( ( ) 1) ( , )tF x z t = ҐХ z - t - Ўт ҐлxB z - t − s - rxB z - t − s − h x s ds ; (10)00( , ) (1 ) ( , )tF x t = С − Ґлt - − r Ўт h x s ds , (11)где ƒ(z) - произвольная дифференцируемая функция.60 С.П. Моисеева, И.А. Ананина, А.А. НазаровДля определения частного решения уравнения (8) необходимо воспользоваться начальными условиями. Из (3), (4) и (10) имеем, что 1 10( , ,0) ( ) ( ) (1 ( ))1zF x z R z z B y dy r Ґл= =ҐХ = −− Ўт ; 0 ( ,0) 01F x С R b r Ґл= = −.Таким образом, частное решение уравнения (8) принимает вид 1 [ ]0 0( , , ) (1 ( )) ( ) ( ( ) 1) ( , )1z t t F x z t B y dy xB z t s rxB z t s h x s ds r Ґл = − - Ґл - − - - − −− Ўт Ўт .Дифференцируя это тождество по z в нуле, получаем интегральное уравнение0(,) ( )() ( )(,)1 1th x t x B t rx b t s h t s ds r r Ґл Ґл = - Ґл − - −− − Ўт .Решение относительно функции h(x,t) интегрального уравнения можно получить через преобразования Фурье [14]. Обозначив0e j tb(t)dt B ( )ЎДЎт Ґб = ∗ Ґб , 0h(x,t)e j tdt ( )ЎДЎт Ґб = ϕ Ґб , получаем равенство( ) ( 1) ( )1 1 ()x B r rxB ∗∗Ґл Ґб ϕ Ґб = −− − Ґб .Следовательно, выражение для h(x,t) принимает вид ( , ) 1 ( )2h x t e j t d ЎД− Ґб −ЎД= ϕ Ґб Ґб Ґр Ўт . (12)Подставляя найденное решение h(x,t) интегрального уравнения в (10), (11), при z имеем00( , ) (1 ) ( , )1b t F x t t r h x s ds r Ґл= − − Ґл - −− Ўт ; 10( , ) ( 1) ( , )1b t F x t xt rx h x s ds r Ґл= -Ґл - −− Ўт , где h(x,t) определяется равенством (12). Откуда1 00( , ) ( , ) ( , ) ( 1) ( 1) ( , )tF x t = F x t - F x t = x − Ґлt - r x − Ўт h x s ds . (13)4. Исследование потока в СМО с неограниченным числомобслуживающих приборовПроизводящая функция суммарного числа обращений в рассматриваемойСМО определяется выражением( , ) n(t ) lim { (n1(t) n2 (t) nN (t ))}NG x t Mx Mx - - ЎжЎД= = .Исследование потоков в системе M|GI|∞ с повторными обращениями 61В силу того, что все ni , i=1…N , независимы и одинаково распределены, имеем( , ) lim ( ( , , ))NNG x t H x t N ЎжЎД= .Учитывая (5), (6), получаем( ) 0 ( ) 1 ( ), lim 1 1 , 1 , , 1NNG x t F x t F x t ЎжЎД N N N = ⎛ - - ЎД - Ґп⎛ ⎞ ⎞ ⎜ ⎜ ⎟ ⎟⎝ ⎝ ⎠ ⎠.При z( , ) lim 1 1 ( , ) 1NNG x t F x t ЎжЎД N N = ⎛ - - Ґп⎛ ⎞ ⎞ ⎜ ⎜ ⎟ ⎟⎝ ⎝ ⎠ ⎠.Таким образом, с учетом (13) имеем{ }0( , ) exp ( , ) exp ( 1) ( 1) ( , ) .tG x t F x t x t r x h x s ds ⎧⎪ ⎪⎫ = = ⎨ − Ґл - − ⎬⎩⎪ ⎭⎪Ўт .В случае экспоненциального времени производящую функцию можно переписать следующим образом: ( ) 2(1 )2( , ) exp 1 ( 1) 11 (1 )(1 )G x t t x r x e rx t rx r rx ⎧ − Ґл − −Ґм − ⎫= ⎨Ґл − − ⎬⎩ − Ґм − − ⎭.Полученное выражение совпадает с ранее полученными результатами для бесконечнолинейных систем массового обслуживания с повторным обращением и экспоненциальным временем обслуживания [8].5. Исследование двумерного потокав системе СМО с повторным обращениеми неограниченным числом обслуживающих приборовРассмотрим исходную СМО, но уже разделяя повторные и первичные обращения. Обозначим: n(t) - число повторных обращений, реализованных за время t, v(t) - число -----первичных обращений, реализованных за время t.Будем рассматривать двумерный немарковский процесс {v(t),n(t)}.Для соответствующей одномерной СМО аналогично z(t) - длина интервала от текущего момента времени t до момента окончания текущего обслуживания, еслиприбор занят, то есть k(t) = 1 .Обозначим: P1(v,n, z,t, N) = P{k(t) = 1, v(t) = v, z(t) < z, n(t, N) = n} , P0 (v, n,t, N) = P{k(t) = 0, v(t) = v, n(t, N) = n} , где P1(ν,n,z,t,N) - вероятность того, что число первичных обращений равно v, повторных - n, прибор занят и до конца обслуживания остается времени меньше z; P0(ν,n,z,t,N) - вероятность того, что число первичных обращений равно v , повторных - n и прибор свободен.Для вышеуказанных распределений вероятностей, применяя формулу полнойвероятности, запишем равенстваP0 (v, n,t t, N) P0 (v,n,t, N)(1 t) (1 r)P1(v,n, t,t, N) o( t)NҐл- ҐД = − ҐД - − ҐД - ҐД , 62 С.П. Моисеева, И.А. Ананина, А.А. НазаровP1(v,n, z − ҐДt,t - ҐДt, N) = P1(v,n, z,t, N) − P1(v,n,ҐДt,t, N) - P1(v,n −1,ҐДt,t, N)rB(z) P0 (v 1, n,t, N) tB(z) o( t)NҐл- − ҐД - ҐД , откуда получаем систему дифференциальных уравнений Колмогорова0 10( , , , ) (1 ) ( , , 0, , )( , , , )P v n t N r P v n t N P v n t N t z N ЎУ − ЎУ Ґл = −ЎУ ЎУ; (14)1( , , , , ) 1( , , , , ) 1( , ,0, , ) 1( , 1,0, , )( )P v n z t N P v n z t N P v n t N rB z P v n t N t z z z ЎУ ЎУ ЎУ ЎУ −= − - ЎУ ЎУ ЎУ ЎУP0 (v 1, n,t, N)B(z)NҐл- − . (15)Рассмотрим функции0 00 0v n ( , , , ) ( , , , )v n x y P v n t N G x y t N ЎД ЎД= ҐТҐТ = ; (16)1 10 0v n ( , , , , ) ( , , , , )v n x y P v n z t N G x y z t N ЎД ЎД= ҐТҐТ = . (17)Тогда из (14),(15) следует, что G1(x,y,z,t,N) и G0(x,y,t,N) удовлетворяют системедифференциальных уравнений в частных производных0 10( , , , ) (1 ) ( , , 0, , )( , , , )G x y t N r G x y t N G x y t N t z N ЎУ − ЎУ Ґл = −ЎУ ЎУ; (18)1( , , , , ) 1( , , , , ) 1( , ,0, , )( ( ) 1)G x y z t N G x y z t N rB z y G x y t N t z z ЎУ ЎУ ЎУ− = − ЎУ ЎУ ЎУG0 (x, y,t, N)x B(z)NҐл- , (19)решение которой будем искать в виде20 0G (x, y,t, N) 1 1 F (x, y,t) (N )N= - - Ґп − ; (20)21 1G (x, y, z,t, N) 1 F (x, y, z,t) (N )N= - Ґп − . (21)Тогда уравнения для F1(x, z,t) и F0(x,t) запишутся как 0 ( , , ) 1( , ,0, )(1 )F x y t F x y t r t z ЎУ ЎУ= Ґл − −ЎУ ЎУ; 1( , , , ) 1( , , , ) 1( , ,0, )( ) ( ( ) 1)F x y z t F x y z t xB z ryB z F x y t t z z ЎУ ЎУ ЎУ− =Ґл - −ЎУ ЎУ ЎУ.Обозначим ЎУF1(x, y,0,t) ЎУz = h(x, y,t) .Таким образом, систему для F0, F1 перепишем в виде0( , , )(1 ) ( , , )F x y t r h x y t t ЎУ= Ґл − −ЎУ; 1( , , , ) 1( , , , )( ) ( ( ) 1) ( , , )F x y z t F x y z t xB z ryB z h x y t t z ЎУ ЎУ− =Ґл - −ЎУ ЎУ. (22)Исследование потоков в системе M|GI|∞ с повторными обращениями 63Решение дифференциального уравнения в частных производных первого порядка (22) определяется решением системы обыкновенных дифференциальныхуравнений вида1 .1 1 () ( () 1)(, ,)dt dz dF xB z ryB z h x y t = − Ґл - −Найдем два первых интеграла этой системы. Один из них из уравнения−dt = dz.Отсюда z = C1 − t . (23)Другой первый интеграл находим из уравненияdF1 = [ҐлxB(z) - (ryB(z) −1)h(x, y,t)]dt .Откуда получаем равенство1 2 [ ]0( , , , ) ( ) ( ( ) 1) ( , , )tF x y z t = C - Ўт ҐлxB z - ryB z − h x y s ds .Следовательно, общее решение (32) можно записать в виде1 1 [ 1 1 ]0( , , , ) ( ) ( ) ( ( ) 1) ( , , )tF x y z t = ҐХ C - Ўт ҐлxB C − s - ryB C − s − h x y s ds .или, учитывая, что C1 определяется из равенства (22), общее решение уравнения(21) запишем в виде1 [ ]0( , , , ) ( ) ( ) ( ( ) 1) ( , , )tF x y z t = ҐХ z - t - Ўт ҐлxB z - t − s - ryB z - t − s − h x y s ds . (23)где ƒ(z) - произвольная дифференцируемая функция, Для определения частного решения уравнения (22) необходимо воспользоваться начальными условиями: 0 ( )00, 0, 0, , ,0, ( ), 0, 0.v n P v n N R N v n ⎧ > > = ⎨ = = ⎩( )1 ( )10, 0, 0, , , ,0, , , 0, 0.v n P v n z N R z N v n ⎧ > > = ⎨ = = ⎩Рассмотрим стационарное распределение вероятностей состояния прибора.Из (16) следует, что выполняются равенстваG0 (1,1,t, N) = R0 (N) ; (24)G1(1,1, z,t, N) = R0 (z, N) . (25)Поэтому из (17), (18) очевидно следует, что R0(N), R1(z,N) являются решениемсистемы уравнений( ) 1 ( )00, ( ) 1R N R N r N z Ґл ЎУ= −ЎУ; (26)1 ( ) 1 ( ) ( ) 1 ( ) ( )0, 0, 0, ( ) 0R z N R N R N rB z R N B z z z z N ЎУ ЎУ ЎУ Ґл − - - ЎУ ЎУ ЎУ. (27)64 С.П. Моисеева, И.А. Ананина, А.А. НазаровОтсюда получаем равенство1 ( , ) 1 (0, ) ( ) 1 (0, ) ( ) 1 (0, ) ( )1 0R z N R N R N R N rB z r B z z z z z ЎУ ЎУ ЎУ ЎУ− - - − ЎУ ЎУ ЎУ ЎУ, или 1 ( , ) 1 (0, ) ( ( ))1R z N R N B z z z ЎУ ЎУ= −ЎУ ЎУ.Учитывая (26), получим( )( )1 ( ( ))0, 1 ( )1R z N B z R N z N r ЎУ Ґл = −ЎУ −, ( )( )1 0 ( ( ))0, () 11zR z N R N B s ds N r Ґл = −− Ўт . (28)С учетом условия нормировки при z, имеем систему двух линейных алгебраических уравненийR0 (N) - R1(ЎД, N) = 1, 1 ( ) 0 ( , ) ( )1R N b R N N r Ґл ЎД −, решение которой имеет вид ( )0 ( )1( )1N r R N b N r −Ґл - −, 1( , ) ( )1R N b b N r Ґл ЎД Ґл - −. (28)Следовательно, в силу (28) запишем( )( )( )1 ( )0 0( , ) 1 ( ) 1 ( )(1 ) 1 1b z z R z N B s ds B s ds N r b N r b N r Ґл Ґл Ґл = − = −− Ґл - − Ґл - − Ўт Ўт .Устремляя N и используя формулы (20), (21), получаем1 1 10( , , ,0) ( ) ( ) (1 ( ))1zF x y z R z C B s ds r Ґл= =ҐХ = −− Ўт ; 0 ( , ,0) 01F x y R b r Ґл= −.Таким образом, частное решение (23) принимает вид 1 [ ]0 0( , , , ) (1 ( )) ( ) ( ( ) 1) ( , , )1z t t F x y z t B w dw xB z t s ryB z t s h x y s ds r Ґл = − - Ґл - − - - − −− Ўт Ўт .Дифференцируя это тождество по z в нуле, получаем интегральное уравнениеотносительно h(x, y, t): 0( , , ) ( ) ( ) ( ) ( , , )1 1th x y t x B t ry b t s h x y s ds r r Ґл Ґл = - Ґл − - −− − Ўт , (29)Исследование потоков в системе M|GI|∞ с повторными обращениями 65где b(t s) B( z t s) z z=0 − = ЎУ - − ЎУ .Решение h(x,y,t) интегрального уравнения (29) записывается через преобразования Фурье0( , xy) h(x, y,t)e j tdt ЎДϕ Ґб = Ўт Ґб в виде( ) ( 1) ( )1 1 ()x B r ryB ∗∗Ґл Ґб ϕ Ґб = −− − Ґб .Следовательно, ( , ) 1 ( )2h x t e j t d ЎД− Ґб −ЎД= ϕ Ґб Ґб Ґр ЎтПодставляя решение интегрального уравнения в (23), при z имеем00( , , ) (1 ) ( , , )1b t F x y t t r h x y s ds r Ґл= − − Ґл - −− Ўт , 10( , , ) ( 1) ( , , )1b t F x y t xt ry h x y s ds r Ґл= -Ґл - −− Ўт . (30)Откуда1 00( , , ) ( , , ) ( , , ) ( 1) ( 1) ( , , )tF x y t = F x y t - F x y t = x − Ґлt - r y − Ўт h x y s ds .Учитывая (20), (21), получаем выражение для производящей функции двумерного потока обращений в рассматриваемой СМО: { }0( , , ) exp ( , , ) exp ( 1) ( 1) ( , , ) .tG x y t F x y t x t r y h x y s ds ⎧⎪ ⎪⎫ = = ⎨ − Ґл - − ⎬⎪⎩ ⎭⎪Ўт .Так как производящая функция G(x,z,t) двумерного распределения P(ν,n,t) не равна произведению производящих функций одномерных распределений, то, очевидно, потоки являются зависимыми и анализ таких потоков необходимо проводить лишь только совместно.ЗаключениеТаким образом, в работе построена математическая модель потоков в системемассового обслуживания с неограниченным числом обслуживающих приборов и повторным обращением. Методом предельной декомпозиции исследованы суммарный и двумерный потоки обращений в рассматриваемой системе массовогообслуживания. Получены выражения для производящих функций исследуемыхпотоков. Показано, что результаты исследования являются обобщением ранее известных частных случаев, а именно для экспоненциального времени обслуживания [8, 9].Полученные результаты могут быть использованы при проведении анализапотоков различных социально-экономических систем, где наблюдается эффектповторного обращения, например в страховых и торговых компаниях.66 С.П. Моисеева, И.А. Ананина, А.А. Назаров

Скачать электронную версию публикации