Асимптотический анализ RQ-системы с N типами вызываемых заявок в предельном условии большой задержки заявок на орбите | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 48. DOI: 10.17223/19988605/48/2

Асимптотический анализ RQ-системы с N типами вызываемых заявок в предельном условии большой задержки заявок на орбите

Рассматривается RQ-система с несколькими типами вызываемых заявок. Основным методом исследования является метод асимптотического анализа, который позволяет в предложенной RQ-системе найти вид предельного распределения числа заявок, поступивших в систему в условии большой задержки заявок на орбите. На основе найденного распределения построено дискретное распределение (гауссовская аппроксимация). Определены условия применимости полученной аппроксимации в зависимости от значений параметров, определяющих систему, на основе численных экспериментов.

Asymptotic analysis of retrial queue with N types of outgoing calls under low rate of retrials condition.pdf RQ-системы характеризуются тем, что заявка, поступившая в систему, в случае занятости сервера остается в ней и пытается вновь занять обслуживающий прибор после некоторой случайной задержки на орбите. RQ-системы являются математическими моделями телекоммуникационных сетей связи, компьютерных сетей, систем в экономике и систем call-центров [1, 2]. В таких системах время простоя сервера должно быть уменьшено для повышения эффективности системы. Мы рассматриваем системы, в которых оператор не только принимает вызовы извне, но и выполняет исходящие вызовы в режиме простоя. Например, в call-центрах операторы могут получать поступающие вызовы, но как только они имеют свободное время и находятся в режиме ожидания, они могут выполнять исходящие вызовы [3, 4]. Такие системы будем называть RQ-системами с вызываемыми заявками, или системами с двумя классами заявок. В работах [5-7] рассматриваются марковские RQ-системы с вызываемыми заявками. Модель RQ-системы с двумя классами заявок и несколькими типами вызываемых заявок рассмотрена Саку-раи и Фунг-Дуком [8]. Для этой модели получен численный алгоритм расчета стационарного распределения состояний системы. В предложенной работе основным методом исследования является метод асимптотического анализа [9, 10], который позволяет в RQ-системе M/M/1/N c N типами вызываемых заявок найти вид предельного распределения числа поступивших заявок в системе в условии большой задержки заявок на орбите. На основе найденного распределения построено дискретное распределение (гауссовская аппроксимация), которое аппроксимирует дискретное распределение числа поступивших заявок в системе. 1. Описание математической модели и постановка задачи Рассмотрим однолинейную RQ-систему с несколькими типами вызываемых заявок, на вход которой поступает простейший поток заявок с параметром λ. Время обслуживания каждой поступившей заявки распределено по экспоненциальному закону с параметром μ1. Если поступившая заявка 13 А.А. Назаров, С.В. Пауль, О.Д. Лизюра застает прибор свободным, она занимает его для обслуживания. Если прибор занят, то заявка переходит на орбиту, где осуществляет случайную задержку, продолжительность которой имеет экспоненциальное распределение с параметром σ. С орбиты после случайной задержки заявка вновь обращается к прибору с повторной попыткой его захвата. Когда прибор свободен, он вызывает заявки извне. Рассматривается система с N типами вызываемых заявок. Прибор вызывает заявки типа n с интенсивностью αn. Время обслуживания вызванной заявки типа n распределено по экспоненциальному закону с параметром μn. Обозначим i(t) - число поступивших заявок в системе в момент времени t, без учета вызванной заявки, если она обслуживается на приборе. Процесс k(t) определяет состояние прибора в момент времени t следующим образом: 0, если прибор свободен; 1, если прибор занят обслуживанием поступившей заявки; n, если прибор занят обслуживанием вызванной заявки типа n, где n=2, N+1. Двумерный процесс {i(t), k(t)} является цепью Маркова с непрерывным временем. Введем обозначение P{i(t) = i, k(t) = k} = Pk(i) - стационарная вероятность того, что в момент времени t прибор находится в состоянии k и в системе находится i поступивших заявок. Для распределения вероятностей Pk(i) рассматриваемой RQ-системы составим систему уравнений Колмогорова: N+1N+1 -I λ+iσ + ^ an IpO(i)+ μιp1(i+1) + ∑μnpn(i) = 0, \\ n=2 У n=2 -(λ +μ )P(i) + λP(i -1) + λP (i -1) +iσP (i) = 0, (1) -(λ + μn ^^pn (i) + 'λpn (i-1) + αnp0 (i) = 0, n ='2,n + 1. ∞ _ Введем частичные характеристические функции H (и) = Σ ej^upk (i), где j ^/-1, к = 0, N +1. i=0 Тогда систему (1) перепишем в виде: N+1N+1 -| λ + ∑an IHo(и) + j'σHo'(и) + μιe-juHι(и) + ∑μnHn(и) = 0, \\ n= 2 У n= 2 -(λ + μ )H (и) + 7^е^иН (и) + ^еиН, (и) - jσH,,' (и) = 0, -(λ + μn )Н„ (и) + λe^"H^ (и) + a„H, (и) = 0, n = 2, N+1. Суммируя уравнения системы (2), получим уравнение (2) (3) 7.^,, (и) + (7. - μ е-и )H (и) + λ∑ H,^ (и) = 0. n=2 Характеристическая функция H(u) числа заявок для системы (2), (3) выражается через частич- N+1 ные характеристические функции H⅛(u) следующим равенством: H(и) = '^H (u). Аналитическое k=0 выражение для H(u) представлено в следующей теореме. Теорема 1. Характеристическая функция H(u) числа поступивших заявок в RQ-системе M/M/1/N с вызываемыми заявками имеет следующий вид: ! N +1 N +1 Vι =∑∑ αn, V2 =∑∑ in, Pn μ1 n=2 μ n n=2 θn H (и ) 1 + ν1 N+1 1 + ∑+1-----_ n n⅛ ц„+ λ(1 - е_) У λ T-----, θn = λ + μn - μi, λ+ μn nn1 αn 1 - ρ σ (ι+ν2 )+1 N+1 п n=2 1- Pn _ 1 - ре'и _ _1 - Рп-п _ σθn ? an (θn-λ) (4) где ρ = - μ1 Доказательство. Для доказательства теоремы 1 необходимо второе и третье уравнения системы (2) разрешить относительно функций H1(u) и Hn(u), n=2, N+1 соответственно. Подставляя полученные выражения в первое уравнение системы (2), мы получим обыкновенное дифференциальное уравнение с разделяющимися переменными относительно функции H0(u). Решая дифференциальное уравнение, получаем функцию H0(u) в явном виде с точностью до мультипликативной константы. 14 Асимптотический анализ RQ-системы с N типами вызываемых заявок Подставляем H0(u) в выражения для функций H1(u) и Hn(u), n=2, N+1 и суммируем все полученные N+1 функции согласно равенству H(u) = LH (u). Константу интегрирования определяем из условия k=0 нормировки H(0) = 1. Теорема доказана. Применяя обратное преобразование Фурье к найденной характеристической функции (4), мож- 1 ? ■ - но записать распределение вероятностей P(i) в виде P(ι) = - I e ^j^'H(u)du, i = 0,∞ . Однако нахож-2π J -к дение аналитического выражения этих интегралов вряд ли возможно, следовательно, целесообразно использовать методы численного интегрирования. Численные расчеты, в свою очередь, требуют больших затрат вычислительных ресурсов. В настоящей работе на основе применения метода асимптотического анализа, ставится задача построения аналитической аппроксимации распределения P(i) и с помощью численных экспериментов проведение анализа точности. 2. Асимптотика первого порядка Решение системы (2), (3) найдем с помощью метода асимптотического анализа при условии большой задержки заявок на орбите (σ → 0). Результат сформулируем в виде следующей теоремы. Теорема 2. Пусть i(t) - число поступивших заявок в RQ-системе с N типами вызываемых заявок, тогда для последовательности характеристических функций выполняется равенство Iim Mej^'i^‘) σ = ej'"κι, (5) σ→0 где λμ ν + λ N+1 α n = L^ ∙ (6) (7) K1 =- μ1 - λ n=2 μ n Доказательство. Обозначим σ = ε и сделаем в системе (4) следующие замены: и = εw, Hk(u) = Fk(w,ε), к = 0, N +1, получим следующую систему уравнений: -| λ+∑αn IfO(w,ε>+ j w + μιe-jwεf1 (w,e) + ∑μnFn(w,e) = 0, к n~n J δw ↑~i -(λ + μι )F1 (W, ε) + Fi (w, ε) + Fo (w, ε) - j ε) = 0, -(λ+μn)Fn(W,ε)+λFn(W,ε)+αnF0(W,ε) =0, n=2,N +1, N+1 λF0(W,ε)+(λ -μ1e-jWε)F1(W,ε) + λLFn(W,ε) =0. n=2 В системе (7) сделаем предельный переход при ε → 0. Обозначив F (W) =limF (W,ε), k =0,N +1, поkε→0 k лучим -μιiξ (w) - jF0 (w) + 7.F0 (W) = 0, -μ^F≈(w)+anFo(w) = 0, n = '2, n+1, λFo (w) - (μι - λ)Fι (w) + λ^ Fn (w) = 0. (8) n=2 15 А.А. Назаров, С.В. Пауль, О.Д. Лизюра Будем искать решение системы уравнений (8) в следующем виде: Fk (w) = Φ(w), k = 0, N+1, где rk - это вероятность того, что прибор находится в состоянии k. L N+1 .Φ'( w) Nr1 λ ÷∑; -∙ J '0+iΦ(W) r0+∑ k''k=o∙ Φ'(w) -μ1r - j------r0 + λr0 = 0, 1 1 Φ(w)0 0 -μnrn + -nr0 = 0, n = 2, n +1, λr0- (μ1- λ)r1+ λ∑ rn = 0∙ n=2 n n=2 (9) (10) Φ'(w) Так как отношение j----- не зависит от w, функция Φ(w) имеет следующий вид: Φ(w) = cxp*∕wκ∣[, Φ(w) что соотносится с (5), где параметр κ1 будет найден ниже. Систему (10) перепишем в виде: -[ λ + ∑+;-, 0 - К.Г0 +∑+; μ krk = 0, \\ n= 2 J k =1 -μ1r. + К1Г0 + λθ0 = 0, -μnrn+ -nr0 = 0, n=2, n+1, λr0 - (И1 - λ)r1 + λ∑ rn = 0∙ n=2 (11) N+1 Запишем условие нормировки для распределения вероятностей состояний прибора: ∑ r = 1. k=0 Выписывая 3 и 4 уравнения системы (11) совместно с условием нормировки, получим систему -μnrn+ -nr0 = 0, n=2, n+1, N+1 - λ}r1 + λ∑ rn = 0, λr0 - (μ1 n=2 N + 1 ∑ rk = 1, k=0 (12) _ ^+1 α n = 2, N +1, где ν = ∑ -n. n=2 μ n 2 Подставляя полученное решение в систему (11) получаем значение параметра: к =---1----• Теоре- 1 μ1 - λ μ1 - λ решение которой имеет вид: r =-------, 0 μ1(1+ ν) _ 'λ -„ (μ1 - Х) ^1 , rn Z, X , 1 μ1 n μ1μn(1+ ν) ма доказана. Асимптотика первого порядка определяет среднее значение числа поступивших заявок в системе. Для более детального исследования процесса i(t) следует рассмотреть асимптотику второго порядка. 3. Асимптотика второго порядка Основной результат анализа асимптотики второго порядка представим в виде теоремы. Теорема 3. Пусть i(t) - число поступивших заявок в RQ-системе с N типами вызываемых заявок, тогда имеет место предельное равенство: IimMexpI jwyfσ i(t) - κ1 = exp|(j^) j, (13) 16 Асимптотический анализ RQ-системы с N типами вызываемых заявок где _ λμ1 (μ1 - λ)(ν1 - λν2) + λ2 (μ1 + λν1 _N+1 _NA1 On^ κ2 = (.. л ∖2 , ν1 =∑ , ν2 ~∑ 2’ N+1 (μ1 - λf n=2μn n=2μn (14) Доказательство. В системе (2), (3) сделаем следующие замены: Hk(u) = eχp I-Ju ^K7 j Hk^kuk, перепишем систему (14) в виде: L ‰ (2^ • dH02^(u) -1λ+∑α"+κ11 hO (u)+jσ-- N+1 + μ1e-^uHf^ (u) + ∑Hn (u) = 0, n=2 dH (2) (u) -(λ + μ )H(2') (u) + λ^∙^uH^2^ (u) + (λey + K )H^2^ (u) - Jσ---^^-k = 0, 1 1 1 1 O du -(λ + μn )H^^^ (u) + λe^uH^^^ (u) + a„Hy^ (u) = 0, n = 2,^^, λHO2^ (u) + (λ - μ1e-yu )H1^^ (u) + λ∑ H(2k (u) = 0. n=2 В предельном условии большой задержки на орбите обозначим σ = ε2, введем следующие замены: u = wε, H(u) = Fl:.'^'k (w, ε), k = O, N +1, в результате получим систему: -[ λ ÷∑∑; ÷ K,] fo-2) (wε)+ε ^f^ (15) + μ1e-^wε F;(2) (w, ε) + ∑ Fnnn (w, ε) = 0, n=2 -(λ + u)A (w,ε) + λe^wε Fn^n(w,ε) + (λe^wε + K1)FO^2k(w,ε) - jε ^F0''(W, ε) = 0, ∂w -(λ + μn )F(^^ (w, ε) + λe^wε (w, ε) + a„Fo(2) (w, ε) = 0, n = 1, N+1, λ,F0,^^ (w, ε) + (λ - μ1e-jwε) (w, ε) + λ∑ F(^^ (w, ε) = 0. n=2 (16) Найдем решение системы (16) в следующем виде: Fk^'> (w, ε) = Φ2 (w) {Γk + Jwεfk} + o (ε2), k = 0, N +1. Подставляя разложение (17) в систему (16), учитывая (11) и выполняя несложные преобразования, получим (17) Ґ ^n?1 Ъ n?1 Φ2' (w) -1 κ1+ λ+∑αn fO +∑μkfk = μ1r1 --j^τrO к n=2 J t~! wΦ2(w) ф' (w) (K1 + λ)f, - μ1f1 = -λrO, - λr1 + rO,, wΦ (w) -μnfn + αnf0 =-λrn , n = 2, n + 1, N+1 λfo- (μ1- λλ∕1+ λ∑ f„ = -μ1r1. n=2 Т/Т “ Φ2' (w) Из полученной системы можем сделать вывод, что выражение -2---- не зависит от w, следовательwΦ (w) f ( но, функцию Φ2(w) можно представить в виде: φ(w) = expI >, что соотносится с (13). Перепишем последнюю систему в виде: N+1N+1 -| κ1 + λ +Σ αn I fO +Σ μkfk = μ1r1 + κ2rO, \\ n=2 J k=1 17 А.А. Назаров, С.В. Пауль, О.Д. Лизюра (κ1+λ)f0 - μ1 f1 = -λr0 -λr1-κ2r0, -μnfn + αnf0 = -λrn , n = 2, n + 1, λf0 - (Ц1 - λ)f1 + λІ fn = -μ1r1. (18) n=2 Подставляя значения вероятностей rk в систему (18), получим следующие выражения для функций fn: = λ(l+ Vj f = , + λ(μ,-λ)α. n=2-N71 f и, - λ. f μ, (I + V,) μ, - ■>. ’ μ,f μ,μ2(l + V,) ’ ’ ’ N+1αN+1α где ν = , V = Подставляя эти выражения во второе уравнение системы (18), мы получим n=2μn n=2μn искомый параметр К2. Нужно отметить, что неизвестная величина f0 уже не входит в выражение для К2, поэтому он однозначно определяется равенством _х^(^ - λ)(ν - λ^2)+λλ (μ + λν) κ 2 = (И1 - λ)2 ■ Теорема доказана. Теорема 3 показывает, что асимптотическое распределение вероятностей числа поступивших заявок в RQ-системе с несколькими типами вызываемых заявок является гауссовским с параметрами K1.∕σ и K2.∕σ, что позволяет для допредельного распределения P(∕) построить аппроксимацию, в частности аппроксимацию P(2)(∕) вида (19) P(2)(∕) = (L(∕ + 0,5) - L(∕ - 0,5))(1 - L(-0,5))-1, где L(x} - функция нормального распределения с параметрами К1./а и K2.∕σ. 4. Точность аппроксимации Точность аппроксимации P(2)(∕) определим с помощью расстояния Колмогорова i Δ = max 2 0≤i≤N І(p

Ключевые слова

RQ-система, вызываемые заявки, метод асимптотического анализа, предельное условие большой задержки, гауссовская аппроксимация, retrial queue, outgoing calls, asymptotic analysis method, low rate of retrials condition, Gaussian approximation

Авторы

ФИООрганизацияДополнительноE-mail
Назаров Анатолий АндреевичТомский государственный университетдоктор технических наук, профессор, заведующий кафедрой теории вероятностей и математической статистики Института прикладной математики и компьютерных наукnazarov.tsu@gmail.com
Пауль Светлана ВладимировнаТомский государственный университеткандидат физико-математических наук, доцент кафедры теории вероятностей и математической статистики Института прикладной математики и компьютерных наукpaulsv82@mail.ru
Лизюра Ольга ДмитриевнаТомский государственный университетмагистрант кафедры теории вероятностей и математической статистики Института прикладной математики и компьютерных наукoliztsu@mail.ru
Всего: 3

Ссылки

Artalejo J.R., Gomez-Corral A. Retrial queueing systems: a computational approach. Berlin : Springer, 2008. 320 p.
Falin G., Templeton J.G.C. Retrial queues. CRC Press, 1997. 320 p.
Bhulai S., Koole G. A queueing model for call blending in call centers // IEEE Transactions on Automatic Control. 2003. V. 48 (8). P. 1434-1438.
Aguir S., Karaesmen F., Aksin O.Z., Chauvet F. The impact of retrials on call center performance // OR Spectrum. 2004. V. 26 (3). P. 353-376.
Artalejo J.R., Phung-Duc T. Markovian retrial queues with two-way communication // Journal of industrial and management optimization. 2012. V. 8 (4). P. 781-806.
Artalejo J.R., Phung-Duc T. Single server retrial queues with two-way communication // Applied Mathematical Modelling. 2013. V. 37 (4). P. 1811-1822.
Phung-Duc T., Rogiest W. Two-way communication retrial queues with balanced call blending // Lecture Notes in Computer Science. 2012. V. 7314. P. 16-31.
Sakurai H., Phung-Duc T. Two-way communication retrial queues with multiple types of outgoing calls // TOP: An Official Jour nal of the Spanish Society of Statistics and Operations Research. 2015. V. 23 (2). P. 466-492.
Nazarov A.A., Paul S.V., Gudkova I. Asymptotic analysis of Markovian retrial queue with two-way communication under low rate of retrials condition. // 31th European Conference on Modelling and Simulation. 2017. P. 687-693.
Nazarov A., Phung-Duc T., Paul S. Heavy Outgoing Call Asymptotics for MMPP/M/1/1 Retrial Queue with Two-Way Communication // Communications in Computer and Information Science. 2017. V. 800. P. 28-41.
 Асимптотический анализ RQ-системы с N типами вызываемых заявок в предельном условии большой задержки заявок на орбите | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 48. DOI: 10.17223/19988605/48/2

Асимптотический анализ RQ-системы с N типами вызываемых заявок в предельном условии большой задержки заявок на орбите | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 48. DOI: 10.17223/19988605/48/2