Numerical-Analytical Delay Model Based on Qs With Operational Shift of Distribution Principles

封面

如何引用文章

全文:

详细

This article demonstrates results for a queuing system formed by right-shifting an Erlang distribution and a second-order hyperexponential distribution. As is known, the first distribution provides a coefficient of variation less than one, and the second one – more than one. From the general queuing theory, it is known that the average delay of requests in the queue in the QS G/G/1 is related to the coefficients of variation of arrival intervals and service times by a quadratic dependence, and the system we are considering belongs precisely to this type. An operational shift in the distribution laws leads to a multiple reduction in delay compared to a conventional system, and this value depends on the value of the shift parameter. To construct a mathematical model of the delay, the method of spectral solution of the Lindley integral equation for the system under consideration was applied. For the practical application of the obtained results, the standard method of oprobability theory moments is used. The obtained results of numerical and analytical modeling in Mathcad clearly confirm the adequacy of the proposed mathematical delay model.

全文:

Введение

В русскоязычной и англоязычной научной литературе авторами не обнаружено сведений о системах массового обслуживания (СМО), сформированных с помощью операционного сдвига законов распределений интервалов поступлений и времени обслуживания. Такие СМО с операционным сдвигом законов распределений в дальнейшем будем рассматривать как системы с запаздыванием по времени. Наиболее близко к этой тематике относятся работы [1; 2], в которых аппроксимация очередей к интернет ресурсам представлена как система с запаздыванием во времени.

Исследования по рассматриваемой тематике приведены во многих работах авторов, включая [3–6]. Используемый для этого метод наиболее полно с демонстрацией примеров описан в [7]. Данный метод используется во многих областях научных исследований, например [8; 9]. Кроме того, в работе использованы приемы и методы аппроксимации законов распределений [10–13]. Сравнительно новые результаты по СМО представлены в [14–17].

В работе [6] приведены полученные автором результаты по системе, сформированной функциями плотностей вида:

at=4λ2te2λt,

bt=qμ1eμ1t+1qμ2eμ2t.

Для нее получена следующая математическая модель задержки:

. (1)

Здесь σ1, σ2 – инверсные значения корней -  σ1, - σ2 многочлена третьей степени σ3c2σ2c1σc0 с коэффициентами   c2=4λμ1μ2, c1=4λ(μ1+μ2λ)μ1μ2c0=4λ2q(μ1μ2)+4λμ1(μ2λ)] включающими параметры распределений a(t) – интервалов поступлений и b(t) – времени обслуживания.

Все параметры выражения (١) определяются методом моментов через числовые характеристики распределений a(t) и b(t):

λ=1λτλ2¯=32λ2 τ¯μ=qμ1+1qμ2, τμ2¯=2qμ12+21qμ22 [6].

Здесь «–» стандартная операция усреднения для моментов.

Постановка и решение задачи

Теперь подвергнем распределения a(t) и b(t) операции сдвига вправо:

at=4λ2tt0e2λtt0,  t>t0,0,  0tt0,, (2)

bt=qμ1eμ1(tt0)+1qμ2eμ2(tt0),  t>t0,0,  0tt0.. (3)

В качестве новых законов распределений a(t) и b(t), формирующих СМО, будем рассматривать (2) и (3). Авторами ставится задача получения численно-аналитической модели задержки для системы, формируемой законами распределений (2) и (3).

Для решения поставленной задачи запишем изображения Лапласа для функций (2) и (3):

A*s=[2λ/(2λ+s)]2et0s, B*s=[qμ1s+μ1+1qμ2s+μ2]et0s.

Разложение выражения A*sB*s1=αs/βs на дробно-рациональные функции α(s) и β(s) приведет к равенству вида:

α(s)β(s)=2λ2λs2et0s×[qμ1s+μ1+1qμ2s+μ2]et0s1=s(s+σ1)(s+σ2)(sσ3)(2λs)2(s+μ1)(s+μ2), (4)

т.к. полином четвертой степени в числителе выражения (4) можно представить в виде разложения σ(σ3c2σ2c1σc0) с коэффициентами, которые приведены выше. Наша задача состоит в определении нулей и полюсов выражения (4). Здесь опущены не очень сложные математические выкладки.

Нужные нам нули полинома третьей степени σ3c2σ2c1σc0 (два действительных отрицательных числа) обозначим -σ1, -σ2, а одно положительное число σ3. Тогда дробно рациональные функции α(s) и β(s) из выражения (4) будут иметь вид:

αs=ss+σ1s+σ2s+μ1(s+μ2),

βs=(2λs)2(sσ3).

Из выражения (4) для всех систем с операционным сдвигом следует одно общее свойство, выражающееся в том, что операционный сдвиг не влияет на спектральное решение, т.е. последнее остается инвариантным к операции сдвига законов распределений у СМО. Это вытекает из свойства запаздывания изображения Лапласа и из специфики выражения A*sB*s1=αs/βs, где присутствуют противоположные знаки у перед комплексной частотой s. Теперь, после того, как найдены составляющие спектрального решения α(s) и β(s), а также определены их нули и полюса, мы можем утверждать, что они удовлетворяют всем требованиям спектрального решения [7].

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

Спектральные решения для обычной системы и системы с операционным сдвигом будут совпадать, и, следовательно, численно-аналитическая модель задержки (1) справедлива и для системы с операционным сдвигом. При этом надо учесть тот факт, что числовые характеристиками сдвинутых распределений (2) и (3) и параметры этих распределений становятся функционально зависимыми от параметра сдвига.

Для применения в дальнейшем формулы (1) для расчета средней задержки, через изображения Лапласа запишем начальные моменты до второго порядка.

Для закона распределения (3):

λ=λ-1+t0 τλ2¯=t02+2t0λ+32λ2cλ=[21+λt0] 1. (5)

Для закона распределения (3)

τ¯μ=qμ11+(1q)μ21+t0

τμ2¯=2[qμ12+(1q)μ22]+t02+2t0[qμ11+(1q)μ21],

cμ2=[(1q2)μ122μ1μ2q(1q)+q(2q)μ22][t0μ1μ2+(1q)μ1+qμ2]2. (6)

Из уравнений моментов (5) и (6) определяем параметры распределений (2) и (3). Из них следует, что параметры μ, cμ,t0 связаны ограничением cμ1t0/τ¯μ, 0<t0<τ¯μ. Таким образом, система E2/H2/1, сформированная операционным сдвигом распределений (2) и (3) применима при выполнении ограничений

cμ1t0/τ¯μ, 0<t0<τ¯μ. (7)

Функциональная зависимость коэффициентов вариаций интервалов поступлений и времени обслуживания cλ и cμ от параметра сдвига t0 явно прослеживается из выражений (5) и (6), и как будет видно из следующего раздела, полностью подтверждается при численном расчете.

Алгоритм применения выражения (1) для дальнейших расчетов относительно прост. Через заданные начальные моменты распределений из уравнений (5) и (6) последовательно определяем все параметры выражения (1) [6].

Численные эксперименты в Mathcad

На рисунке 1 представлен вариант расчета среднего времени ожидания для случая высокой нагрузки, равной 0,95 при коэффициенте вариации времени обслуживания, равном 2 и параметре сдвига 0,99. Из программы на Mathcad хорошо прослеживается алгоритм применения расчетной формулы (1). В таблице 1 представлены результаты серии численных расчетов в Mathcad.

 

Рисунок 1. Пример численного расчета в программе Mathcad

 

В таблице 1 приведены результаты численных расчетов в Mathcad для указанной системы с операционным сдвигом законов распределений (обозначена S2) при значениях параметра сдвига t0 от 0,001 до 0,99 для случаев умеренной и высокой нагрузки (ρ=0,6; 0,95) для сравнительно малого значения коэффициента вариации времени обслуживания значения  соответственно для обычной системы (обозначена S1).

 

Таблица 1. Результаты серии численных расчетов в Mathcad

Входные параметры

Среднее время ожидания

ρ

cλ

cμ

t0

для системы S2

для системы S1

0,6

0,287

1,010

0,99

0,764

3,212

0,495

1,500

0,5

1,702

0,672

1,818

0,1

2,865

0,703

1,990

0,01

3,176

0,707

1,998

0,001

3,208

0,95

0,042

1,010

0,99

9,690

42,570

0,371

1,500

0,5

22,471

0,640

1,900

0,1

37,980

0,700

1,990

0,01

42,098

0,706

1,999

0,001

42,522

 

Заключение

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

Адекватность предложенной численно-аналитической модели задержки в системе с операционным сдвигом подтверждается несколькими факторами. Во-первых результаты расчетов таблицы 1 полностью подтверждают общую теорию систем G/G/1 в части функциональной зависимости задержки от коэффициентов вариаций. Во-вторых, поведение задержки в зависимости от величины параметра сдвига свидетельствует о сохранении свойства непрерывности для указанных СМО, обычных и с операционным сдвигом. Кроме того, результаты по системам с запаздыванием по времени согласуются с данными имитационного моделирования [18].

×

作者简介

Veniamin Tarasov

Povolzhskiy State University of Telecommunications and Informatics

编辑信件的主要联系方式.
Email: v.tarasov@psuti.ru

Head of Software and Management in Technical Systems Department, Doctor of Technical Science, Professor

俄罗斯联邦, Samara

Nadezhda Bakhareva

Povolzhskiy State University of Telecommunications and Informatics

Email: n.bahareva@psuti.ru

Head of Informatics and Computer Technics Department, Doctor of Technical Science, Professor

俄罗斯联邦, Samara

参考

  1. Novitzky S. et al. Limiting the oscillations in queues with delayed information through a novel type of delay announcement. Queueing Systems, 2020, vol. 95, pp. 281–330. DOI: https://doi.org/ 10.1007/s11134-020-09657-9
  2. Novitzky S. et al. Nonlinear dynamics in queueing theory: determining the size of oscillations in queues with delay. SIAM Journal on Applied Dynamical Systems, 2019, vol.18, no. 1, pp. 279–311.
  3. Tarasov V.N. Extension of the class of queueing systems with delay. Avtomatika i telemekhanika, 2018, no.12, pp. 57–70. (In Russ.)
  4. Tarasov V.N., Ahmetshina E.G. Average waiting time in the H2/H2/1 queuing system with delay. Vestnik Samarskogo gosudarstvennogo tekhnicheskogo universiteta. Seriya: Fiziko-matematicheskie nauki, 2018, vol. 22, no. 4. pp. 702–713. (In Russ.)
  5. Tarasov V.N. Queuing systems with a time lag. Informacionnye tekhnologii, 2021, vol. 27, no. 6, pp. 291–298. (In Russ.)
  6. Tarasov V.N. Spectral decomposition for QS-based delay model with Erlang and hyperexponential distributions. Physics of Wave Processes and Radio Systems, 2022, vol. 25, no. 3, pp. 24–28. (In Russ.)
  7. Kleinrock L. Queuing theory. Ed by V.I. Neimona. Transl. From English. Moscow: Mashinostroeinie, 1979, 432 p. (In Russ.)
  8. Do T.V., Chakka R., Sztrik J. Spectral expansion solution methodology for QBD-M processes and applications in future internet engineering. Studies in Computational Intelligence, 2016, vol. 479, pp. 131–142. doi: 10.1007/978-3-319-00293-4-11
  9. Ma X.A. et al. Spectral method for two-dimensional ocean acoustic propagation. Journal of Marine Science and Engineering, 2021, no. 9, pp. 1–19. DOI: https://doi.org/ 10.3390/jmse9080892
  10. Aliev T.I. Fundamentals of discrete system modeling. Saint Petesburgs: SPbGU ITMO, 2009, 363 p. (In Russ.)
  11. Aliev T.I. Approximation of probability distributions in queueing models. Nauchno-tekhnicheskij vestnik informacionnyh tekhnologij, mekhaniki i optiki, 2013, vol. 84, no. 2, pp. 88–93. (In Russ.)
  12. Myskja A. An improved heuristic approximation for the GI/GI/1 queue with bursty arrivals. Teletraffic and datatraffic in a Period of Change: ITC-13. Elsevier Science Publishers, 1991. pp. 683–688.
  13. Whitt W. Approximating a point process by a renewal process: two basic methods. Operation Research, 1982, vol. 30, no. 1, pp. 125–147.
  14. Gromoll H.C., Terwilliger B., Zwart B. Heavy traffic limit for a tandem queue with identical service times. Queueing Systems, 2018, vol. 89, no. 3, pp. 213–241.
  15. Jacobovic R., Kella O. Asymptotic independence of regenerative processes with a special dependence structure. Queueing Systems, 2019, vol. 93, pp. 139–152. doi: 10.1007/s11134-019-09606-1
  16. Wang L., Kulkarni V. Fluid and diffusion models for a system of taxis and customers with delayed matching. Queueing Systems, 2020, vol. 96, pp. 101–131. doi: 10.1007/s11134-020-09659-7
  17. Legros B. M/G/1 queue with event-dependent arrival rates. Queueing Systems, 2018, vol. 89, no. 3, pp. 269–301.
  18. Tarasov V.N., Bahareva N.F. Simulation model of a QS with hyperexponential distribution in the GPSS WORLD environment. Infokommunikacionnye tekhnologii, 2022, vol. 20, no. 4, pp. 7–13. (In Russ.)

补充文件

附件文件
动作
1. JATS XML
2. Figure 1. Example of numerical calculation in Mathcad programme

下载 (553KB)

版权所有 © Tarasov V.N., Bakhareva N.F., 2024

Creative Commons License
此作品已接受知识共享署名-非商业性使用-禁止演绎 4.0国际许可协议的许可。