Delay model based on shifted hyperexponential and Erlang distributions

Full Text

Введение

В теории массового обслуживания исследования систем G/G/1 актуальны в связи с тем, что они активно используются в современной теории телетрафика, к тому же нельзя получить решения для таких систем в конечном виде для общего случая.

Настоящая статья посвящена анализу СМО H₂/E₂/1 со сдвинутыми вправо от нулевой точки гиперэкспоненциальными (H₂) и эрланговскими (E₂) входными распределениями второго порядка и является логическим продолжением исследований [1–3]. В результате этого будем иметь новую СМО с запаздыванием во времени, которую обозначим через ${\text{H}}_{\text{2}}^{-}{\text{/E}}_2^{-}\text{/1}$ в отличие от обычной системы H₂/E₂/1. Рассматриваемая СМО относится к типу G/G/1. Всего систем со сдвинутыми законами распределений в теории массового обслуживания можно составить шестнадцать (4 × 4 = 16), если рассматривать четыре основных закона распределения: экспоненциальный, Эрланга, гиперэкспоненциальный и гиперэрланговский.

В работе [1] показано, что средняя задержка требований в очереди в системе M/M/1 с запаздыванием во времени меньше, чем в классической системе M/M/1 при одинаковом коэффициенте загрузки за счет того, что коэффициенты вариации времен $c_{\lambda }$ поступления  и обслуживания $c_{\mu }$ становятся меньше единицы при параметре запаздывания $t_0>0.$ Это связано с квадратичной зависимостью средней задержки от указанных коэффициентов вариаций. В авторских работах [2; 3] и других, этот факт также полностью подтвердился. Убедимся также в этом в случае рассматриваемой СМО, используя метод спектрального разложения решения интегрального уравнения Линдли, одна из форм которого дается в виде [4]:

$W\left(y\right)=\left\{\begin{array}{l}\underset{-\infty }{\overset{y}{\int }}W\left(y-u\right)\text{d}C\left(u\right)\text{,\hspace{1em}}y\ge \text{0};\\ \text{0,\hspace{1em}}y<\text{0.}\end{array}\right.$

Другой подход к решению интегрального уравнения Линдли использован в [5]. Здесь вместо термина «спектральное разложение» использована факторизация, а вместо функций ${\psi }_{+}\left(s\right)$ и ${\psi }_{-}\left(s\right)$ – компоненты факторизации ${\omega }_{+}\left(z,t\right)$ и ${\omega }_{-}\left(z,t\right)$ функции $1-z\chi \left(t\right).$

Такой подход для получения конечных результатов для рассматриваемых систем менее удобен, чем подход, описанный в [4] и проиллюстрированный многочисленными примерами для лучшего понимания. Метод спектрального разложения решения интегрального уравнения Линдли занимает важное место при исследовании систем G/G/1 и он широко используется.

Кроме этого метода в работе использован опыт аппроксимации законов распределений [6–9]. Полученные результаты хорошо согласуются с результатами экспериментальных исследований [10–12]. Результаты современных исследований по системам массового обслуживания приведены в работах [13–16].

1. Постановка задачи

В работе ставится задача нахождения решения для задержки требований в очереди в СМО ${\text{H}}_{\text{2}}^{-}{\text{/E}}_2^{-}\text{/1.}$ При кратком изложении метода спектрального разложения решения интегрального уравнения Линдли будем придерживаться подхода и символики автора классики теории массового обслуживания [4]. Суть решения методом спектрального разложения состоит в нахождении для выражения $F_{\lambda }^{*}\left(-s\right)F_{\mu }^{*}\left(s\right)-1$ представления в виде произведения двух множителей, которое давало бы рациональную функцию от s. Здесь $F_{\lambda }^{*}\left(s\right)$ и $F_{\mu }^{*}\left(s\right)$ соответственно преобразования Лапласа функций плотности распределения интервалов входного потока $f_{\lambda }\left(t\right)$ и времени обслуживания $f_{\mu }\left(t\right).$ Следовательно, для нахождения закона распределения времени ожидания необходимо следующее спектральное разложение: $F_{\lambda }^{*}\left(-s\right)F_{\mu }^{*}\left(s\right)-1=$${\psi }_{+}\left(s\right)/{\psi }_{-}\left(s\right),$ где ${\text{ψ}}_{+}\left(s\right)$ и ${\text{ψ}}_{-}\left(s\right)$ некоторые рациональные функции от s, которые можно разложить на множители. Функции ${\psi }_{+}\left(s\right)$ и ${\psi }_{-}\left(s\right)$ должны удовлетворять следующим условиям согласно [4]:

– для $\text{Re}\left(\text{s}\right)>\text{0}$ функция ${\psi }_{+}\left(s\right)$ является аналитической без нулей в этой полуплоскости;

– для $\text{Re}\left(\text{s}\right)<D$ функция ${\psi }_{-}\left(s\right)$ является аналитической без нулей в этой полуплоскости, где D – некоторая положительная константа, определяемая из условия: $\underset{t\to \infty }{\text{lim}}\frac{a\left(t\right)}{e^{-Dt}}<\infty .$

Кроме того, функции ${\psi }_{+}\left(s\right)$ и ${\psi }_{-}\left(s\right)$ должны удовлетворять следующим условиям:

$\begin{array}{l}\underset{\left|\text{s}\right|\to \infty ,\mathrm{Re}\left(s\right)>0}{\lim }\frac{{\psi }_{+}\left(s\right)}{s}=1;\\ \underset{\left|s\right|\to \infty ,\mathrm{Re}\left(s\right)<D}{\lim }\frac{{\psi }_{-}\left(s\right)}{s}=-1.\end{array}$ (2)

Для решения поставленной задачи необходимо вначале построить для рассматриваемой системы спектральное разложение вида $F_{\lambda }^{*}\left(-s\right)F_{\mu }^{*}\left(s\right)-1={\psi }_{+}\left(s\right)/{\psi }_{-}\left(s\right)$ с учетом условий (1), (2). Так для системы ${\text{H}}_{\text{2}}^{-}{\text{/E}}_2^{-}\text{/1}$ законы распределения интервалов входного потока и времени обслуживания задаются функциями плотности вида:

$f_{\lambda }\left(t\right)=\left\{\begin{array}{l}p{\lambda }_1{e}^{-{\lambda }_1(t-t_0)}+\\ +\left(1-p\right){\lambda }_2{e}^{-{\lambda }_2(t-t_0)},t>t_0,\\ \mathrm{0,}0\le t\le t_0,\end{array}\right.$ (3)

$f_{\mu }\left(t\right)=\left\{\begin{array}{l}4{\mu }^2\left(t-t_0\right)e^{-2\mu \left(t-t_0\right)},t>t_0,\\ \mathrm{0,}0\le t\le t_0.\end{array}\right.$ (4)

Здесь $t_0\ge 0$ – параметр сдвига закона распределения. Заметим также, что функция (4) – функция плотности нормированного распределения Эрланга второго порядка.

Преобразования Лапласа функций (3) и (4) будут соответственно:

$F_{\lambda }^{*}\left(s\right)=\left[p\frac{{\lambda }_1}{s+{\lambda }_1}+\left(1-p\right)\frac{{\lambda }_2}{s+{\lambda }_2}\right]e^{-t_{0}s}\text{ ;}$

$F_{\mu }^{*}\left(s\right)={\left(\frac{2\mu }{2\mu +s}\right)}^2{e}^{-t_{0}s}.$

Тогда спектральное разложение решения интегрального уравнения Линдли для рассматриваемой системы $F_{\lambda }^{*}\left(-s\right)F_{\mu }^{*}\left(s\right)-1={\psi }_{+}\left(s\right)/{\psi }_{-}\left(s\right)$ примет вид:

$\begin{array}{l}{F}_{\lambda }^{*}\left(-s\right)F_{\mu }^{*}\left(s\right)-1=\\ =\left[p\frac{{\lambda }_1}{{\lambda }_1-s}+\left(1-p\right)\frac{{\lambda }_2}{{\lambda }_2-s}\right]e^{t_{0}s}\times \\ \times {\left(\frac{2\mu }{2\mu +s}\right)}^2{e}^{-t_{0}s}-1=\\ =\left[p\frac{{\lambda }_1}{{\lambda }_1-s}+\left(1-p\right)\frac{{\lambda }_2}{{\lambda }_2-s}\right]{\left(\frac{2\mu }{2\mu +s}\right)}^2-1.\end{array}$ (5)

Выражение (5) получено на основании теоремы о запаздывании в теории преобразования Лапласа. Здесь показатели степени у экспонент в спектральном разложении обнуляются и таким образом операция сдвига во времени нивелируется. Таким образом, спектральные разложения решения интегрального уравнения Линдли для системы со сдвинутыми распределениями ${\text{H}}_{\text{2}}^{-}{\text{/E}}_2^{-}\text{/1}$ и для обычной системы H₂/E₂/1 будут идентичными. Это позволяет утверждать, что спектральное разложение будет инвариантным к операции сдвига в законах распределения.

Дальнейшее разложение выражения (5) даст окончательное спектральное разложение решения интегрального уравнения Линдли

$\frac{{\psi }_{+}\left(s\right)}{{\psi }_{-}\left(s\right)}=\frac{-s(s+s_1)(s+s_2)(s-s_3)}{({\lambda }_1-s)({\lambda }_2-s){(2\mu +s)}^2},$ (6)

т. к. многочлен 4-й степени в числителе выражения (5) можно представить в виде разложения $-s(s^3+c_2{s}^2+c_{1}s+c_0)$ с коэффициентами $c_2=4\mu -{\lambda }_1-{\lambda }_2,$ $c_1=4\mu (\mu -{\lambda }_1-{\lambda }_2)+$${\lambda }_1{\lambda }_2,$ $c_0=4\mu [{\lambda }_1{\lambda }_2+\mu ({\lambda }_{1}p-{\lambda }_1-{\lambda }_{2}p\left)\right].$  В свою очередь кубический многочлен $s^3+c_2{s}^2+c_{1}s+c_0$ с такими коэффициентами в стационарном режиме функционирования СМО при $\rho ={\overline{\tau }}_{\mu }/{\overline{\tau }}_{\lambda }<1$ имеет два действительных отрицательных корня $-s_1, -s_2$  и один положительный корень $s_3.$ Здесь ${\overline{\tau }}_{\lambda }$ и ${\overline{\tau }}_{\mu }$ – среднее значение интервалов поступления требований и среднее время обслуживания соответственно, а коэффициенты многочлена сформированы с помощью символьных операций Mathcad.

С учетом условий (1), (2) за функцию ${\psi }_{+}\left(s\right)$ примем

${\psi }_{+}\left(s\right)=s(s+s_1)(s+s_2)/{(s+2\mu )}^2,$

т. к. нули кубического многочлена $s=\mathrm{0,}$ $s=-s_1,$ $s=-s_2$ и полюс $s=-2\text{\hspace{0.17em}μ}$ лежат в области $\text{Re}\left(s\right)\le \mathrm{0,}$ а за функцию

${\text{ψ}}_{-}\left(s\right)=-({\lambda }_1-s)({\lambda }_2-s)/(s-s_3).$

Теперь выполнение условий (1) и (2) для построенных функций ${\psi }_{+}\left(s\right)$ и ${\psi }_{-}\left(s\right)$ очевидно. Далее по методике спектрального разложения найдем константу К:

$K=\underset{\left|s\right|\to 0}{\lim }\frac{{\psi }_{+}\left(s\right)}{s}=\underset{\left|s\right|\to 0}{\lim }\frac{(s+s_1)(s+s_2)}{{(s+2\text{μ)}}^2}=\frac{s_1{s}_2}{{\text{4μ}}^2}.$

Построим функцию ${\Phi }_{+}\left(s\right)=K/{\psi }_{+}\left(s\right),$ через которую найдем преобразование Лапласа функции плотности времени ожидания $W^{*}\left(s\right)=s{\Phi }_{+}\left(s\right).$

Окончательно

$W^{*}\left(s\right)=\frac{s_1{s}_2{\left(s+2\text{μ}\right)}^2}{{\text{4μ}}^2(s+s_1)(s+s_2)}.$ (7)

Производная от функции $W^{*}\left(s\right)$ со знаком минус в т. $s=0$ и даст среднюю задержку требований в очереди:

$\begin{array}{l}-\frac{d{W}^{*}\left(s\right)}{ds}{|}_{s=0}=-\frac{d}{ds}\left[\frac{s_1{s}_2{\left(s+2\text{μ}\right)}^2}{{\text{4μ}}^2(s+s_1)(s+s_2)}\right]|s=0=\\ =\frac{1}{s_1}+\frac{1}{s_2}-\frac{1}{\text{μ}}.\end{array}$

Тогда средняя задержка для системы ${\text{H}}_{\text{2}}^{-}{\text{/E}}_2^{-}\text{/1}$ будет равна:

$\overline{W}=\frac{1}{s_1}+\frac{1}{s_2}-\frac{1}{\text{μ}},$ (8)

где $s_1, s_2$ абсолютные значения отрицательных корней $-s_1$ и $-s_2$ кубического многочлена $s^3+c_2{s}^2+c_{1}s+c_0$ с приведенными выше коэффициентами. Таким образом, среднее время для системы ${\text{H}}_{\text{2}}^{-}{\text{/E}}_2^{-}\text{/1}$ однозначно определено в виде замкнутой формы (8).

2. Методика использования расчетной формулы (8)

Теперь предстоит определить все параметры формулы (8). Для этого определяем числовые характеристики сдвинутых распределений ${\text{H}}_{\text{2}}^{-}$ (3) и ${\text{E}}_2^{-}$ (4). Для этого воспользуемся свойством преобразования Лапласа функции плотности воспроизводить моменты:

$\begin{array}{l}-\frac{d{F}_{\lambda }^{*}\left(s\right)}{ds}{|}_{s=0}=\\ =-\frac{d}{ds}\left\{\left[p\frac{{\lambda }_1}{s+{\lambda }_1}+\left(1-p\right)\frac{{\lambda }_2}{s+{\lambda }_2}\right]e^{-t_{0}s}\right\}{|}_{s=0}=\\ =p{\lambda }_1^{-1}+(1-p){\lambda }_2^{-1}+t_0.\end{array}$

Отсюда среднее значение интервала между поступлениями требований:

${\overline{\tau }}_{\lambda }\text{=\hspace{0.17em}}p{\lambda }_1^{-1}+(1-p){\lambda }_2^{-1}+t_0 .$ (9)

Найдя вторую производную от преобразования $F_{\lambda }^{*}\left(s\right)$ при s = 0 определим 2-й начальный момент интервала между поступлениями

$\begin{array}{l}\overline{{\tau }_{\lambda }^2}=2[p{\lambda }_1^{-2}+(1-p\left){\lambda }_2^{-2}\right]+t_0^2+\\ +2t_0[p{\lambda }_1^{-1}+(1-p\left){\lambda }_2^{-1}\right].\end{array}$ (10)

Тогда квадрат коэффициента вариации:

$c_{\lambda }^2=\frac{\left[\right(1-p^2){\lambda }_1^2-2{\lambda }_1{\lambda }_{2}p(1-p)+p(2-p\left){\lambda }_2^2\right]}{{[t_0{\lambda }_1{\lambda }_2+(1-p){\lambda }_1+p{\lambda }_2]}^2}.$ (11)

Положив

${\lambda }_1=2p/({\overline{\tau }}_{\lambda }-t_0), {\lambda }_2=2(1-p)/({\overline{\tau }}_{\lambda }-t_0)$ (12)

и подставив (12) в (11) получим уравнение четвертой степени относительно параметра p. Решив его с учетом условия $0<p<1$ определяем параметр p:

$p=\frac{1}{2}\pm \sqrt{\frac{1}{4}-\frac{{({\overline{\tau }}_{\lambda }-t_0)}^2}{2[{({\overline{\tau }}_{\lambda }-t_0)}^2+c_{\lambda }^2{\overline{\tau }}_{\lambda }^2]}}.$ (13)

Подставив выражение (13) в (12) находим неизвестные параметры распределения (3) ${\lambda }_1, {\lambda }_2.$  При этом в качестве p можно выбрать любое из двух значений.

Остается определить числовые характеристики распределения (4). Среднее время обслуживания в системе ${\text{H}}_{\text{2}}^{-}/{\text{E}}_{\text{2}}^{-}/1$ равно

${\overline{\tau }}_{\mu }={\mu }^{-1}+t_0.$ (14)

Отсюда параметр µ распределения (4) будет равен $\mu =1/({\overline{\tau }}_{\mu }-t_0).$

Отсюда диапазон изменения параметра сдвига определится из условия $0<t_0<{\overline{\tau }}_{\mu }.$

Второй начальный момент времени обслуживания равен

$\overline{{\tau }_{\mu }^2}=t_0^2+\frac{2t_0}{\mu }+\frac{3}{2{\mu }^2}.$

Следовательно, коэффициент вариации времени обслуживания будет равен $c_{\mu }={\left[\sqrt{2}\left(1+\mu t_0\right)\right]}^{-1}.$

Таким образом, все параметры распределений (3) и (4) при задании значений ${\overline{\tau }}_{\lambda }, {\overline{\tau }}_{\mu }, c_{\lambda }, c_{\mu }, t_0$ в качестве входных данных для системы ${\text{H}}_{\text{2}}^{-}/{\text{E}}_{\text{2}}^{-}/1$ будут определены однозначно методом моментов.

Заметим, что коэффициенты вариации $c_{\lambda }>0$ и $c_{\mu }<1/\sqrt{2}$ при параметре сдвига $t_0>0.$ Таким образом, очевидно, что система ${\text{H}}_{\text{2}}^{-}/{\text{E}}_{\text{2}}^{-}/1$ также относится к типу G/G/1.

3. Результаты вычислительных экспериментов

В таблице приведены данные расчетов для системы ${\text{H}}_{\text{2}}^{-}/{\text{E}}_{\text{2}}^{-}/1$ для случаев малой, средней и высокой нагрузки $\rho =\mathrm{0,1};$ 0,5; 0,9 при $c_{\lambda }=2.$ Заметим, что обычная система H₂/E₂/1 применима при $c_{\lambda }\ge 1$ и $c_{\mu }=1/\sqrt{2},$ а система ${\text{H}}_{\text{2}}^{-}/{\text{E}}_{\text{2}}^{-}/1$ – при $c_{\lambda }>0$ и $c_{\mu }<1/\sqrt{2}.$ Таким образом, система ${\text{H}}_{\text{2}}^{-}/{\text{E}}_{\text{2}}^{-}/1$ применима для широкого диапазона изменения параметров, чем обычная система H₂/E₂/1 и расширяет ее возможности.

В правой колонке таблицы для сравнения приведены результаты для обычной системы H₂/E₂/1. Коэффициент загрузки в данном случае определяется отношением средних интервалов $\rho ={\overline{\tau }}_{\mu }/{\overline{\tau }}_{\lambda }.$ Расчеты, приведенные в таблице проведены для удобства для нормированного времени обслуживания ${\overline{\tau }}_{\mu }=1.$

 

Таблица. Результаты экспериментов для СМО ${\mathbf{\text{H}}}_{\mathbf{\text{2}}}^{\mathbf{-}}{\mathbf{\text{/E}}}_{\mathbf{2}}^{\mathbf{-}}\mathbf{\text{/1}}$

Входные параметры			Средняя задержка
$\rho$	$c_{\mu }$	$t_0$	для системы ${\text{H}}_{\text{2}}^{-}{\text{/E}}_2^{-}\text{/1}$	для системы H2/E2/1
0,1	0,071	0,9	0,001	0,141
	0,354	0,5	0,035
	0,636	0,1	0,114
	0,700	0,01	0,138
0,5	0,071	0,9	0,015	1,764
	0,354	0,5	0,472
	0,636	0,1	1,480
	0,700	0,01	1,735
0,9	0,071	0,9	0,748	20,016
	0,354	0,5	14,769
	0,636	0,1	19,157
	0,700	0,01	19,931

 

Система ${\text{H}}_{\text{2}}^{-}{\text{/E}}_2^{-}\text{/1}$ применима и в случае $c_{\lambda }<\mathrm{1,}$ в частности при $\rho =\mathrm{0,9,}$ $c_{\lambda }=\mathrm{0,2,}$ $t_0=\mathrm{0,9,}$ $c_{\mu }=\mathrm{0,071,}$ среднее время ожидания будет равно $\overline{W}=\mathrm{0,072}$ единиц времени, снизившись в несколько десятков раз по сравнению с обычной системой.

Заключение

Таким образом, по результатам работы можно сделать следующие выводы:

Операция сдвига во времени уменьшает коэффициенты вариаций интервала между поступлениями и времени обслуживания требований. В связи с тем, что среднее время ожидания в системе G/G/1 связано с коэффициентами вариаций интервалов поступления и обслуживания квадратичной зависимостью, среднее время ожидания в системе с запаздыванием будет меньше, чем в обычной системе при одинаковом коэффициенте загрузки. Например, для системы ${\text{H}}_{\text{2}}^{-}{\text{/E}}_2^{-}\text{/1}$ при загрузке $\rho =\mathrm{0,9}$ и параметре сдвига $t_0=\mathrm{0,9}$ коэффициент вариации интервалов поступления $c_{\lambda }$ уменьшается с 2 для обычной системы до 1,105, коэффициент вариации времени обслуживания $c_{\mu }$ уменьшается с $1/\sqrt{2}$ до 0,071, а время ожидания уменьшается с 20,016 единиц времени для обычной системы до 0,748 единиц времени для системы с запаздыванием.

С уменьшением значения параметра $t_0$ среднее время ожидания в системе ${\text{H}}_{\text{2}}^{-}{\text{/E}}_2^{-}\text{/1}$ стремится к среднему времени ожидания в обычной системе H₂/E₂/1. Это полностью подтверждает адекватность построенной математической модели массового обслуживания.

Основным преимуществом системы со сдвинутыми распределениями является расширения диапазона применимости по сравнению с обычной СМО. Так в данном случае диапазон для коэффициента вариации времени обслуживания $0<c_{\mu }\le 1/\sqrt{2}$ при параметре сдвига $t_0\ge 0.$

About the authors

Veniamin N. Tarasov

Povolzhskiy State University of Telecommunications and Informatics

Email: tarasov-vn@psuti.ru

Doctor of Technical Sciences, professor, head of the Department of Software and Management in Technical Systems

Russian Federation, Samara

Nadezhda F. Bakhareva

Povolzhskiy State University of Telecommunications and Informatics

Author for correspondence.
Email: bakhareva-nf@psuti.ru

Doctor of Technical Sciences, professor, head of the Department of Informatics and Computer Engineering

Russian Federation, Samara

References

Supplementary files