Модель задержки на основе сдвинутых гиперэкспоненциального и эрланговского распределений

Обложка

Цитировать

Полный текст

Аннотация

Настоящая статья посвящена выводу результатов для средней задержки требований в очереди для системы массового обслуживания, образованной двумя потоками с законами распределения интервалов в виде сдвинутых вправо гиперэкспоненциального и эрланговского распределений второго порядка. В теории массового обслуживания исследования систем G/G/1 актуальны в связи с тем, что не существует решения в конечном виде для общего случая. Поэтому в качестве произвольного закона распределения G при исследовании таких систем используют различные частные законы распределений. В данном случае использование гиперэкспоненциального закона распределения обеспечивает коэффициент вариации интервалов входного потока больше единицы, а распределения Эрланга – меньше единицы. Для решения поставленной задачи использован метод спектрального разложения решения интегрального уравнения Линдли, который играет важную роль в теории массового обслуживания. Данный метод позволил получить решение для средней задержки требований в очереди для рассматриваемой системы в замкнутой форме. Как известно, остальные характеристики системы массового обслуживания являются производными от средней задержки требований.

Полный текст

Введение

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

Настоящая статья посвящена анализу СМО H2/E2/1 со сдвинутыми вправо от нулевой точки гиперэкспоненциальными (H2) и эрланговскими (E2) входными распределениями второго порядка и является логическим продолжением исследований [1–3]. В результате этого будем иметь новую СМО с запаздыванием во времени, которую обозначим через H2/E2/1 в отличие от обычной системы H2/E2/1. Рассматриваемая СМО относится к типу G/G/1. Всего систем со сдвинутыми законами распределений в теории массового обслуживания можно составить шестнадцать (4 × 4 = 16), если рассматривать четыре основных закона распределения: экспоненциальный, Эрланга, гиперэкспоненциальный и гиперэрланговский.

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

Wy=yWyudCu, y0;0, y<0.

Другой подход к решению интегрального уравнения Линдли использован в [5]. Здесь вместо термина «спектральное разложение» использована факторизация, а вместо функций ψ+s и ψs – компоненты факторизации ω+z,t и ωz,t функции 1zχ(t).

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

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

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

В работе ставится задача нахождения решения для задержки требований в очереди в СМО H2/E2/1. При кратком изложении метода спектрального разложения решения интегрального уравнения Линдли будем придерживаться подхода и символики автора классики теории массового обслуживания [4]. Суть решения методом спектрального разложения состоит в нахождении для выражения Fλ*sFμ*s1 представления в виде произведения двух множителей, которое давало бы рациональную функцию от s. Здесь Fλ*s и Fμ*s соответственно преобразования Лапласа функций плотности распределения интервалов входного потока fλ(t) и времени обслуживания fμ(t). Следовательно, для нахождения закона распределения времени ожидания необходимо следующее спектральное разложение: Fλ*sFμ*s1=ψ+s/ψs, где ψ+s и ψs некоторые рациональные функции от s, которые можно разложить на множители. Функции ψ+s и ψs должны удовлетворять следующим условиям согласно [4]:

– для Res>0 функция ψ+s является аналитической без нулей в этой полуплоскости;

– для Res<D функция ψs является аналитической без нулей в этой полуплоскости, где D – некоторая положительная константа, определяемая из условия: limtateDt<.

Кроме того, функции ψ+s и ψs должны удовлетворять следующим условиям:

lims,Res>0ψ+ss=1;lims,Res<Dψss=1. (2)

Для решения поставленной задачи необходимо вначале построить для рассматриваемой системы спектральное разложение вида Fλ*sFμ*s1=ψ+s/ψs с учетом условий (1), (2). Так для системы H2/E2/1 законы распределения интервалов входного потока и времени обслуживания задаются функциями плотности вида:

fλt=pλ1eλ1(tt0)++1pλ2eλ2(tt0),t>t0,0,0tt0, (3)

fμt=4μ2tt0e2μtt0,t>t0,0,0tt0. (4)

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

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

Fλ*s=pλ1s+λ1+1pλ2s+λ2et0s ;

Fμ*s=2μ2μ+s2et0s.

Тогда спектральное разложение решения интегрального уравнения Линдли для рассматриваемой системы Fλ*sFμ*s1=ψ+s/ψs примет вид:

Fλ*sFμ*s1==pλ1λ1s+1pλ2λ2set0s××2μ2μ+s2et0s1==pλ1λ1s+1pλ2λ2s2μ2μ+s21. (5)

Выражение (5) получено на основании теоремы о запаздывании в теории преобразования Лапласа. Здесь показатели степени у экспонент в спектральном разложении обнуляются и таким образом операция сдвига во времени нивелируется. Таким образом, спектральные разложения решения интегрального уравнения Линдли для системы со сдвинутыми распределениями H2/E2/1 и для обычной системы H2/E2/1 будут идентичными. Это позволяет утверждать, что спектральное разложение будет инвариантным к операции сдвига в законах распределения.

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

 ψ+sψs=s(s+s1)(s+s2)(ss3)(λ1s)(λ2s)(2μ+s)2, (6)

т. к. многочлен 4-й степени в числителе выражения (5) можно представить в виде разложения s(s3+c2s2+c1s+c0) с коэффициентами c2=4μλ1λ2, c1=4μ(μλ1λ2)+λ1λ2, c0=4μ[λ1λ2+μ(λ1pλ1λ2p)].  В свою очередь кубический многочлен s3+c2s2+c1s+c0 с такими коэффициентами в стационарном режиме функционирования СМО при ρ=τ¯μ/τ¯λ<1 имеет два действительных отрицательных корня s1, s2  и один положительный корень s3. Здесь τ¯λ и τ¯μ – среднее значение интервалов поступления требований и среднее время обслуживания соответственно, а коэффициенты многочлена сформированы с помощью символьных операций Mathcad.

С учетом условий (1), (2) за функцию ψ+(s) примем

ψ+(s)=s(s+s1)(s+s2)/(s+2μ)2,

т. к. нули кубического многочлена s=0, s=s1, s=s2 и полюс s=2 μ лежат в области Re(s)0, а за функцию

ψs=(λ1s)(λ2s)/(ss3).

Теперь выполнение условий (1) и (2) для построенных функций ψ+s и ψs очевидно. Далее по методике спектрального разложения найдем константу К:

K=lims0ψ+ss=lims0(s+s1)(s+s2)(s+2μ)2=s1s22.

Построим функцию Φ+s=K/ψ+(s), через которую найдем преобразование Лапласа функции плотности времени ожидания W*s=sΦ+s.

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

W*s=s1s2s+2μ22(s+s1)(s+s2). (7)

Производная от функции W*s со знаком минус в т. s=0 и даст среднюю задержку требований в очереди:

dW*sds|s=0=ddss1s2s+2μ22(s+s1)(s+s2)|s=0==1s1+1s21μ.

Тогда средняя задержка для системы H2/E2/1 будет равна:

W¯=1s1+1s21μ, (8)

где s1, s2 абсолютные значения отрицательных корней s1 и s2 кубического многочлена s3+c2s2+c1s+c0 с приведенными выше коэффициентами. Таким образом, среднее время для системы H2/E2/1 однозначно определено в виде замкнутой формы (8).

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

Теперь предстоит определить все параметры формулы (8). Для этого определяем числовые характеристики сдвинутых распределений H2 (3) и E2 (4). Для этого воспользуемся свойством преобразования Лапласа функции плотности воспроизводить моменты:

dFλ*sds|s=0==ddspλ1s+λ1+1pλ2s+λ2et0s|s=0==pλ11+(1p)λ21+t0.

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

τ¯λ= pλ11+(1p)λ21+t0 . (9)

Найдя вторую производную от преобразования Fλ*(s) при s = 0 определим 2-й начальный момент интервала между поступлениями

τλ2¯=2[pλ12+(1p)λ22]+t02++2t0[pλ11+(1p)λ21]. (10)

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

cλ2=[(1p2)λ122λ1λ2p(1p)+p(2p)λ22][t0λ1λ2+(1p)λ1+pλ2]2. (11)

Положив

λ1=2p/(τ¯λt0),   λ2=2(1p)/(τ¯λt0) (12)

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

p=12±14(τ¯λt0)22[(τ¯λt0)2+cλ2τ¯λ2]. (13)

Подставив выражение (13) в (12) находим неизвестные параметры распределения (3) λ1, λ2.  При этом в качестве p можно выбрать любое из двух значений.

Остается определить числовые характеристики распределения (4). Среднее время обслуживания в системе H2/E2/1 равно

τ¯μ=μ1+t0. (14)

Отсюда параметр µ распределения (4) будет равен μ=1/(τ¯μt0).

Отсюда диапазон изменения параметра сдвига определится из условия 0<t0<τ¯μ.

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

τμ2¯=t02+2t0μ+32μ2.

Следовательно, коэффициент вариации времени обслуживания будет равен cμ=[21+μt0]1.

Таким образом, все параметры распределений (3) и (4) при задании значений τ¯λ, τ¯μ, cλ, cμ, t0 в качестве входных данных для системы H2/E2/1 будут определены однозначно методом моментов.

Заметим, что коэффициенты вариации cλ>0 и cμ<1/2 при параметре сдвига t0>0. Таким образом, очевидно, что система H2/E2/1 также относится к типу G/G/1.

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

В таблице приведены данные расчетов для системы H2/E2/1 для случаев малой, средней и высокой нагрузки ρ=0,1; 0,5; 0,9 при cλ=2. Заметим, что обычная система H2/E2/1 применима при cλ1 и cμ=1/2, а система H2/E2/1 – при cλ>0 и cμ<1/2. Таким образом, система H2/E2/1 применима для широкого диапазона изменения параметров, чем обычная система H2/E2/1 и расширяет ее возможности.

В правой колонке таблицы для сравнения приведены результаты для обычной системы H2/E2/1. Коэффициент загрузки в данном случае определяется отношением средних интервалов ρ=τ¯μ/τ¯λ. Расчеты, приведенные в таблице проведены для удобства для нормированного времени обслуживания τ¯μ=1.

 

Таблица. Результаты экспериментов для СМО H2/E2/1

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

Средняя задержка

ρ

cμ

t0

для системы H2/E2/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

 

Система H2/E2/1 применима и в случае cλ<1, в частности при ρ=0,9, cλ=0,2, t0=0,9, cμ=0,071, среднее время ожидания будет равно W¯=0,072 единиц времени, снизившись в несколько десятков раз по сравнению с обычной системой.

Заключение

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

Операция сдвига во времени уменьшает коэффициенты вариаций интервала между поступлениями и времени обслуживания требований. В связи с тем, что среднее время ожидания в системе G/G/1 связано с коэффициентами вариаций интервалов поступления и обслуживания квадратичной зависимостью, среднее время ожидания в системе с запаздыванием будет меньше, чем в обычной системе при одинаковом коэффициенте загрузки. Например, для системы H2/E2/1 при загрузке ρ=0,9 и параметре сдвига t0=0,9 коэффициент вариации интервалов поступления cλ уменьшается с 2 для обычной системы до 1,105, коэффициент вариации времени обслуживания cμ уменьшается с 1/2 до 0,071, а время ожидания уменьшается с 20,016 единиц времени для обычной системы до 0,748 единиц времени для системы с запаздыванием.

С уменьшением значения параметра t0 среднее время ожидания в системе H2/E2/1 стремится к среднему времени ожидания в обычной системе H2/E2/1. Это полностью подтверждает адекватность построенной математической модели массового обслуживания.

Основным преимуществом системы со сдвинутыми распределениями является расширения диапазона применимости по сравнению с обычной СМО. Так в данном случае диапазон для коэффициента вариации времени обслуживания 0<cμ1/2 при параметре сдвига t00.

×

Об авторах

Вениамин Николаевич Тарасов

Поволжский государственный университет телекоммуникаций и информатики

Email: tarasov-vn@psuti.ru

доктор технических наук, профессор, заведующий кафедрой программного обеспечения и управления в технических системах

Россия, Самара

Надежда Федоровна Бахарева

Поволжский государственный университет телекоммуникаций и информатики

Автор, ответственный за переписку.
Email: bakhareva-nf@psuti.ru

доктор технических наук, профессор, заведующий кафедрой программного обеспечения и управления в технических системах

Россия, Самара

Список литературы

  1. Тарасов В.Н., Бахарева Н.Ф., Блатов И.А. Анализ и расчет системы массового обслуживания с запаздыванием // Автоматика и телемеханика. 2015. № 11. С. 51–59. DOI: https://doi.org/10.1134/S0005117915110041
  2. Тарасов В.Н. Расширение класса систем массового обслуживания с запаздыванием // Автоматика и телемеханика. 2018. № 12. С. 57–70. DOI: https://doi.org/10.1134/S0005117918120056
  3. Тарасов В.Н. Анализ и сравнение двух систем массового обслуживания с гиперэрланговскими входными распределениями // Радіоелектроніка, інформатика, управління. 2018. № 4. С. 61–70. DOI: https://doi.org/10.15588/1607-3274-2018-4-6
  4. Клейнрок Л. Теория массового обслуживания / пер. с англ. под ред. В.И. Неймана. М.: Машиностроение, 1979. 432 с.
  5. Бочаров П.П., Печинкин А.В. Теория массового обслуживания. М.: РУДН, 1995. 529 c.
  6. Алиев Т.И. Основы моделирования дискретных систем. СПб.: СПбГУ ИТМО, 2009. 363 с.
  7. Алиев Т.И. Аппроксимация вероятностных распределений в моделях массового обслуживания // Научно-технический вестник информационных технологий, механики и оптики. 2013. № 2 (84). С. 88–93. URL: https://ntv.ifmo.ru/ru/article/4127/approksimaciya_veroyatnostnyh_raspredeleniy_v_modelyah_massovogo_obsluzhivaniya.htm
  8. 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: proc. of congress. Copenhagen, Denmark. 19–26 June 1991. P. 683–688. URL: https://gitlab2.informatik.uni-wuerzburg.de/itc-conference/itc-conference-public/-/raw/master/itc13/myskja911.pdf?inline=true
  9. Whitt W. Approximating a point process by a renewal process, I: Two basic methods // Operation Research. 1982. Vol. 30, no. 1. P. 125–147. DOI: https://doi.org/10.1287/opre.30.1.125
  10. Малахов С.В., Тарасов В.Н. Экспериментальные исследования производительности сегмента программно-конфигурируемой сети // Интеллект. Инновации. Инвестиции. 2013. № 2. С. 81–85.
  11. Тарасов В.Н., Липилина Л.В., Бахарева Н.Ф. Автоматизация расчета характеристик систем массового обслуживания для широкого диапазона изменения их параметров // Информационные технологии. 2016. Т. 22, № 12. С. 952–957. URL: http://novtex.ru/IT/it2016/it1216_web-952-957.pdf
  12. Проектирование и моделирование сетей ЭВМ в системе OPNET MODELER / В.Н. Тарасов [и др.]. Самара: ПГАТИ, 2008. 233 с.
  13. Jennings O.B., Pender J. Comparisons of ticket and standard queues // Queueing Systems. 2016. Vol. 84, no. 1–2. P. 145–202. DOI: https://doi.org/10.1007/s11134-016-9493-y
  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–4. P. 213–241. DOI: https://doi.org/10.1007/s11134-017-9560-z
  15. Legros B. M/G/1 queue with event-dependent arrival rates // Queueing Systems. 2018. Vol. 89, no. 3–4. P. 269–301. DOI: https://doi.org/10.1007/s11134-017-9557-7
  16. Jacobovic R., Kella O. Asymptotic independence of regenerative processes with a special dependence structure // Queueing Systems. 2019. Vol. 93, no. 1–2. P. 139–152. DOI: https://doi.org/10.1007/s11134-019-09606-1

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML

© Тарасов В., Бахарева Н., 2022

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution 4.0 International License.

СМИ зарегистрировано Федеральной службой по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор).
Регистрационный номер и дата принятия решения о регистрации СМИ: серия ФС 77 - 68199 от 27.12.2016.

Данный сайт использует cookie-файлы

Продолжая использовать наш сайт, вы даете согласие на обработку файлов cookie, которые обеспечивают правильную работу сайта.

О куки-файлах