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

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

2016 Управление, вычислительная техника и информатика № 3

УДК 519.872

DOI: 10.17223/19988605/36/6

Ю.И. Рыжиков, А.В. Уланов

ПРИМЕНЕНИЕ ГИПЕРЭКСПОНЕНЦИАЛЬНОЙ АППРОКСИМАЦИИ В ЗАДАЧАХ РАСЧЕТА НЕМАРКОВСКИХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

Представлены возможности применения гиперэкспоненциального распределения второго порядка (Н2) с параметрами произвольного (в том числе комплексного) типа в задачах расчета немарковских систем массового обслуживания. Результаты верифицированы с помощью альтернативных методов.

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

При исследовании немарковских процессов поступления и обслуживания заявок в многоканальных системах массового обслуживания (СМО) широко применяются распределения фазового типа (обозначаются Ph). К этим распределениям относятся взаимосвязанные параллельно-последовательные комбинации фаз прохождения заявок с показательно распределенными длительностями задержек в них. При фиксации номера фаз поступления или обслуживания заявок состояния СМО приобретают марковское свойство, что позволяет представить переходы между ними в виде дискретного марковского процесса с непрерывным временем. Идея метода фиктивных фаз была выдвинута еще А.К. Эрлангом. Порядком аппроксимации естественно считать количество сохраненных начальных моментов исходного распределения.

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

В последнее время возрастает интерес к гиперэкспоненциальному распределению, применение которого показало высокую эффективность при решении задач суммирования рекуррентных потоков [2], расчета СМО с «нетерпеливыми» заявками [3], джексоновских сетей массового обслуживания [4], при анализе систем управления запасами [5].

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

1. Особенности применения Д2-распределения

Гиперэкспоненциальное распределение второго порядка относится к распределениям фазового типа и предполагает выбор случайным процессом одной из двух альтернативных фаз. С вероятностью y процесс попадает в первую фазу и задерживается в ней случайное время, распределенное по экспоненциальному закону с параметром ць с вероятностью y2 = 1 - y процесс попадает во вторую фазу, где экспоненциальная задержка имеет параметр ц2.

Дополнительная функция ^-распределения имеет вид

Ё (г) = уге ^ + у 2 е ^.

Подбор параметров ^-распределения возможен по методу моментов [1]. Поскольку данное распределение трехпараметрическое (четвертый параметр у2 = 1 - у1), оно позволяет выровнять три начальных момента аппроксимируемого, что принято считать вполне достаточным [6].

В зависимости от значений выравниваемых моментов параметры ^-распределения могут принимать комплексные и «парадоксальные» значения. Исследование #2-аппроксимации исходного гамма-распределения с коэффициентом вариации и выявило, что:

- случай и > 1 дает вещественные параметры;

- при 1 > и > 1/ 42 параметры гиперэкспоненты вещественны, но парадоксальны: один из параметров {у}, у = 1, 2 будет отрицательным, а другой превысит единицу;

- строгое равенство и = 1/л/2 недопустимо (соответствует Е2 распределению Эрланга с последовательной сменой фаз и не может быть заменено на параллельную);

- при и < 1/ 42 имеем комплексные параметры #"2-аппроксимации.

Поскольку параметры гиперэкспоненты {у-}, у = 1, 2, интерпретируются как вероятности выбора случайным процессом одной из двух фаз, большинство специалистов по теории массового обслуживания рассматривают лишь тот случай, когда данные параметры определены на вещественном интервале [0, 1], что соответствует аппроксимации распределений с коэффициентом вариации и > 1. Именно поэтому для аппроксимации распределений с коэффициентом вариации и < 1 гипреэкспонента не используется, а применяется распределение Эрланга Ек. Однако обширная серия вычислительных экспериментов показала, что при расчете СМО с применением #"2-аппроксимации в области комплексных значений ее параметров потенциальная патология проявляется только в промежуточных результатах - вероятностях «фиктивных» микросостояний диаграммы переходов, на которые расщепляются «физические» состояния СМО. На этапе суммирования вероятностей микросостояний ярусов их комплексные части аннигилируются и компоненты результата расчета - вероятности числа заявок в системе - становятся вещественными.

Комплексный тип параметров ^-распределения подчеркивает фиктивный характер расщепления процесса на фазы. Допустимость таких параметров при исследовании случайных процессов была впервые отмечена Д. Коксом в 1955 г. [7]. В статье [8] авторы попытались дать вероятностную интерпретацию комплексных интенсивностей переходов между состояниями цепи Маркова.

Примеры различных диаграмм переходов для СМО с гиперэкспоненциальным распределением обслуживания или интервалов между заявками входящего потока приведены в [1, 3]. Дополнительным преимуществом #"2-аппркосимации по сравнению с эрланговской является более компактный вид диаграмм переходов марковизированных СМО. Например, для моделей с эрланговским обслуживанием ширина диаграммы (количество микросостояний на п-м ярусе) быстро растет по числу каналов п и порядку распределения к (табл. 1) [9].

Т а б л и ц а 1

Количество микросостояний на ярусах системы М1Ек1п

Число каналов п Число фаз обслуживания к

2 3 4 5 6

2 3 6 10 15 21

3 4 10 20 35 56

5 6 21 56 126 252

10 11 66 286 1001 3003

20 21 231 1771 10626 53130

30 31 496 5456 46376 324632

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

ации из включенных в табл. 1 распределений (Е6) составил 1/л/б « 0,408. Для расчета СМО с еще меньшим коэффициентом вариации могут потребоваться гораздо большие значения к.

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

Таким образом, достоинствами Н2-аппроксимации являются:

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

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

- удобство вычисления дополнительной функции распределения.

2. Расчет немарковских СМО

Перечислим основные этапы расчета немарковских СМО методом фиктивных фаз с помощью Н2-аппроксимации:

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

- подбор параметров Н2-распределения по рассчитанным на предыдущем шаге моментам;

- построение диаграммы переходов;

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

- суммирование вероятностей микросостояний по ярусам и получение распределения числа заявок в системе.

Рассмотрим возможности Н2-аппроксимации с произвольным типом параметров на примере одно-канальных СМО. Выполним расчет распределения {р,} числа заявок в одноканальной системе МЮ/1 методом вложенных цепей Маркова [1] и методом фиктивных фаз через Н2-аппроксимацию различных распределений обслуживания В(¿):

- гамма с параметром формы 0,5 (Г0,5) (коэффициент вариации и ~ 1,41);

- Гх,5 (и « 0,816);

- равномерного и на интервале [0; 2] (и ~ 0,577);

- вырожденного В (и = 0).

Среднее время обслуживания во всех случаях Ь1 = 1, коэффициент загрузки системы р = 0,7. Результаты расчета распределения числа заявок в системе {р,}, 7 = 0,20, приведены на рис. 1. Сплошной линией показаны результаты, полученные методом вложенных цепей Маркова, штриховой - методом фиктивных фаз через Н2-аппроксимацию.

В табл. 2 приведены параметры Н2-распределения, рассчитанные по трем начальным моментам исходного распределения В(¿).

Т а б л и ц а 2

Параметры ^-распределения

В(Г) У1 Н-2 В(Г) У1 Н-2

Г0,5 0,500 0,586 0,341 и 0,500+'0,866 0,150+'0,866 0,150-'0,866

Г1,5 -0,765 0,263 0,137 В 0,500+'0,141 0,200+'0,141 0,200-'0,141

Рис. 1. Распределение числа заявок в системе М/О/1

Из графиков видно очень хорошее согласие результатов расчета распределения числа заявок в системе даже в области комплексных и парадоксальных параметров аппроксимирующей время обслуживания гиперэкспоненты. Расстояние Колмогорова при Г0,5, Г15, и и В обслуживании составило {0,002; 0,0002; 0,0015; 0,0018} соответственно. Относительная погрешность на «хвостах» распределений, в области малых значений вероятностей, не превысила 15%.

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

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

Заключение

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

Непосредственно о качестве аппроксимации субслучайных (с малым коэффициентом вариации) величин не может идти и речи, поскольку плотность гиперэкспоненты в этом случае принимает отрицательные значения и вообще не удовлетворяет требованиям, предъявляемым к плотности распределения. Качество аппроксимации здесь возможно оценить опосредованно - через сопоставление распределения числа заявок в СМО, полученного через #2-аппроксимацию, с результатами, полученными альтернативными методами.

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

ЛИТЕРАТУРА

1. Рыжиков Ю.И. Алгоритмический подход к задачам массового обслуживания. СПб. : ВКА, 2013. 496 с.

2. Рыжиков Ю.И., Уланов А.В. Применение гиперэкспоненциальной аппроксимации в задачах суммирования потоков // Ин-

теллектуальные технологии на транспорте. 2015. № 4. С. 34-39.

3. Рыжиков Ю.И., Уланов А.В. Расчет гиперэкспоненциальной системы M/H2/n-H2 с заявками, нетерпеливыми в очереди //

Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2014. № 2(27). C. 47-53.

4. Цициашвили Г.Ш. Синергетический эффект в сети с гиперэкспоненциальными распределениями времен обслуживания //

Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2016. № 1 (34). C. 65-68.

5. Назаров А.А., Бронер В.И. Система управления запасами с гиперэкспоненциальным распределением объемов потребления

ресурсов // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2016. № 1(34). C. 43-49.

6. Кендалл М.Дж., Стьюарт А. Теория распределений : пер. с англ. М. : Наука, 1966. 587 с.

7. Cox D.R. A Use of Complex Probabilities in the Theory of Stochastic Process // Proc. of the Cambridge Phil. Soc. 1955. P. 313-323.

8. Bidabad B., Bidabad B. Complex Probability and Markov Stochastic Process // Proc. of the First Iranian Statistics Conference, Isfa-

han University of Technology. 1992. P. 1-8.

9. Рыжиков Ю.И. Развитие и сопоставление методов расчета многоканальных систем обслуживания // Труды всероссийской

конференции «XII Всероссийское совещание по проблемам управления» ВСПУ'2014 / Ин-т пробл. управл. М., 2014. С. 5208-5219.

Рыжиков Юрий Иванович, д-р техн. наук, профессор. E-mail: ryzhbox@yandex.ru Военно-космическая академия имени А.Ф. Можайского, Санкт-Петербургский институт информатики и автоматизации РАН Уланов Александр Викторович, канд. техн. наук. E-mail: ulanov246@rambler.ru Военно-космическая академия имени А. Ф. Можайского

Поступила в редакцию 3 мая 2016 г.

Ryzhikov Yuriy I. (Mozhaisky Military Space Academy, Saint-Petersburg Institute of Informatics and Automatization of Russian Academy of Science, Russian Federation), Ulanov Alexander V. (Mozhaisky Military Space Academy, Russian Federation). A use of hyperexponential distribution in non-markovian queuing systems analyses.

Keywords: hyperexponential distribution; approximation; complex parameters of distributions; numerical methods; non-markovian queuing systems.

DOI: 10.17223/19988605/36/6

In this paper we consider the application of second order hyperexponential distribution (H2) with complex-type parameters for analysis of non-markovian queuing systems. This distribution relates to the phase-type one and allows showing non-markovian queuing systems states and the transitions between them as discrete Markov process with continuous time. The complementary cumulative H2 distribution function is

F (t) = ^e+ y 2 e ^.

Using of H2 distribution for queuing system calculations is reasoned by following reasons:

- the possibility of saving the three initial moments of the original distribution that provides high accuracy in queuing system calculation;

- much more compact (compared to the Erlang approximation) view transition diagrams and as a consequence necessity to calculate the probabilities of a smaller number of microstates for systems with low coefficients of variation of the service time or the intervals between customers;

- simple calculating of complementary cumulative distribution function.

Since the parameters of ^-distributions {yj}, j = 1, 2, are interpreted as the probabilities of random select of one of two phases, most specialists in queuing theory considered only the case when these parameters are defined on a real interval [0; 1], which corresponds to the approximation of the distribution with a coefficient of variation u > 1.

In this article, it is showed the possibilities of the ^-approximation in the case when the original distribution coefficient of variation u < 1. In this case parameters of H2 distribution are complex. More detailed analysis of H2-approximation of the original gamma distribution with a coefficient of variation u shows that:

- if u > 1, then the parameters are real;

- if 1 > u >1/^2 , then the parameters are real, but the paradox: one of the parameters {yj}, j = 1, 2, is negative, and the other will exceed one;

- equality u = 1/V2 is unacceptable (because corresponds to the Erlang distribution with consistent phase-change and, accordingly, can not be replaced by parallel);

- when u <1/^2 , we have the complex parameters of H2 distribution.

However, when calculating the queuing system with H2-approximation in the field of complex values of the parameters of its potential pathology manifests itself only in the intermediate results - in the probabilities of "fictitious" microstate-transition diagram, which split the "physical" state of queuing systems. At the summation of probabilities of microstates tiers of complex parts are annihilated and the result of the calculation - the probability of the number of customers in the system - becomes real.

The paper compares the results of single-channel systems M/G/1 calculation invested by embedded Markov chain, which allows you to obtain an exact solution, with the results obtained by the fictitious phase using H2-approximation of non-exponential service time. Various initial distribution services - deterministic, gamma with shape parameters of 1.5 or 0.5, and even in the interval [0, 2] are considered. It is shown that the accuracy of the above-mentioned result is high enough. The maximum Kolmogorov distance was 0.002, and the relative error of the probability of rare events (about 10-5) did not exceed 15%.

At the same time the quality of approximation in the field of complex parameters H2 distribution is out of question because density of H2-distribution in this case is negative and in general does not satisfy the requirements of the probability density function. Quality of approximations here should be assessed indirectly - through comparison of the distribution of the number of customers in the queuing system, obtained through H2-approximation, with the results obtained by alternative methods.

REFERENCES

1. Ryzhikov, Yu.I. (2013) Algoritmicheskiy podkhod k zadacham massovogo obsluzhivaniya [A use of algorithm approach in the queuing theory]. Saint-Petersburg: VKA.

2. Ryzhikov, Yu.I. & Ulanov, A.V. (2015) Using hyperexponential approximation in the summation of flows problems. Intellektual'nye tekhnologii na transporte - Intelligent technologies on transport. 4. pp. 34-39. (In Russian).

3 Ryzhikov, Yu.I. & Ulanov, A.V. (2014) The method of calculating M/H2/n-H2 queuing system with impatient customers. Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel'naya tekhnika i informatika - Tomsk State University Journal of Control and Computer Science. 2(27). pp. 47-53. (In Russian).

4. Tsitsiashvili, G.Sh. (2016) Synergetic effect in network with hyperexponential distributions of service times. Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel'naya tekhnika i informatika - Tomsk State University Journal of Control and Computer Science. 1(34). pp. 65-68. (In Russian).

5. Nazarov, A.A. & Broner, V.I. (2016) Inventory model with hyperexponential distribution of demand's batch size. Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel'naya tekhnika i informatika - Tomsk State University Journal of Control and Computer Science. 1(34). pp. 43-49. (In Russian).

6. Kendall, M. & Stuart, A. (1966) Teoriya raspredeleniy [The advanced theory of statistics. Distribution theory]. Translated from English. Mosow: Nauka.

7. Cox, D.R. (1955) A Use of Complex Probabilities in the Theory of Stochastic Process. Proc. of the Cambridge Phil. Soc. pp. 313323. DOI: 10.1017/S0305004100030231

8. Bidabad, B. & Bidabad, B. (1992) Complex Probability and Markov Stochastic Process. Proc. of the First Iranian Statistics Conference. Isfahan: Isfahan University of Technology Publ. pp. 1-8.

9. Ryzhikov, Yu.I. (2014) [Progress and comparison of multichannel queuing systems calculations methods]. Proc. of the XII Russian Conference on Control Science. Moscow: Institute of Control Sciences. pp. 5208-5219. (In Russian).