RESEARCH AND COMPARISON OF DUAL SYSTEMS E2/M/1 AND M/E2/1

Full Text

В настоящее время не существует аналитических методов для точного определения характеристик системы массового обслуживания (СМО) общего вида G/M/1 или G/M/m, в отличие от СМО общего вида M/G/1, для которой известна формула Полячека - Хинчина. Статья посвящена исследованию и сравнению двойственных СМО вида E2/M/1 и M/E2/1 с эрланговским и экспоненциальным входными распределениями. Первая система относятся к типу G/M/1, а вторая - M/G/1. По определению системы называются двойственными, когда закон распределения интервалов входного потока одной системы (первая позиция в трехпозиционной системе Кендалла) становится законом распределения времени обслуживания для другой системы (вторая позиция в указанной системе). Так, в системах E2/M/1 и M/E2/1 закон распределения входного потока E2 первой системы становится законом обслуживания второй системы. В теории СМО исследования G/M/1 особо акG/M/1 особо ак/M/1 особо акM/1 особо ак/1 особо актуальны в связи с тем, что до сих пор не существует решения в конечном виде для общего случая распределения интервалов входного потока. Метод спектрального разложения решения интегрального уравнения Линдли (ИУЛ) составляет важную часть теории систем G/G/1. Для записи интегрального ИУЛ введем следующие обозначения: ( ) Wy - функция распределения вероятностей времени ожидания требования в очереди; ( ) () C u P u u = <  - аналогичная функция для случайной величины uxt = -  ; x  - случайное время обслуживания требования; t  - случайный интервал времени между поступлениями требований. Форма ИУЛ выглядит как ( ) ( ) ( ), 0; 0, 0. y W y u dC u y Wy y -∞  -≥=   <  ∫ (1) При кратком изложении метода спектрального разложения решения ИУЛ будем придерживаться подхода и символики автора теории СМО [2]. Для этого как () As ∗ и () Bs ∗ обозначим преобразования Лапласа функций плотности распределения интервалов между поступлениями и времени обслуживания соответственно. Суть решения ИУЛ методом спектрального разложения состоит в нахождении для выражения ( ) ( ) * * 1 A s B s - ⋅ - представления в виде произведения двух множителей, которое давало бы рациональную функцию от s. Следовательно, для нахождения закона распределения времени ожидания необходимо следующее спектральное разложение: ( ) ( ) ( ) ( ) * * 1 / , A s B s s s +- - ⋅ - =ψ ψ где ψ и ( ) s-ψ - некоторые дробно-рациональные функции от s. Функции ( ) s+ψ и ( ) s-ψ должны удовлетворять следующим условиям согласно [2]: - для ( ) Re 0 s > функция ( ) s+ψ является аналитической без нулей в этой полуплоскости; - для ( ) Re sD < функция ( ) s-ψ является аналитической без нулей в этой полуплоскости, где D - некоторая положительная константа, определяемая из условия: ( ) lim / Dt t a t e - →∞ <∞. Кроме того, функции ( ) s+ψ и ( ) s-ψ должны обладать следующими свойствами: ( ) ( ) ,Re 0 lim 1; ss s s + →∞ > ψ = ( ) ( ) ,Re lim 1 s s D s s - →∞ < ψ = - . (2) Теперь остается применить метод спектрального разложения к рассматриваемым системам. Постановка и решение задачи для системы E2/М/1 В статье ставится задача качественного и количественного сравнения результатов для двойственных систем E2/M/1 и M/E2/1 по среднему времени ожидания в очереди. Для проведения сравнительного анализа приведем решения для обеих систем, полученные методом спектрального разложения ИУЛ. В системе E2/М/1 время поступления требований задано функцией плотности ( ) 22 4 t a t te-λ = λ , (3) преобразование Лапласа которой имеет вид ( ) 2 * 2 2 A s s λ =  λ+  . (4) Время обслуживания распределено с функцией плотности ( ) t b t e -µ=µ , (5) а ее преобразование Лапласа имеет вид ( ) * Bs s µ = µ+ . (6) Для применения метода спектрального разложения воспользуемся результатами [2] для систем общего вида G/М/1, к которым принадлежит система E2/M/1. Выражение для спектрального разложения решения ИУЛ для системы G/М/1 заG/М/1 за/М/1 задается в виде [2]: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ** * 1 1 * 1 , s A s B s s A s s s s s s s s s + - ψ - - = = ψ  µ - - -µ + =  + +µ   (7) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ** * 1 1 * 1 , s A s B s s A s s s s s s s s s + - ψ - - = = ψ  µ - - -µ + =  + +µ   где 1 ss = - - единственный отрицательный корень уравнения ( ) * 0. s A s +µ-µ - = Выражение в первых скобках (5) не имеет ни плюсов, ни нулей в области Re( , ) 0 ≤s кроме 0 s = и 1 ss = - [2]. Поэтому за функцию () s+ψ исходя из условий (1)-(2) примем выражение во вторых скобках, так как его нули 0 s = , 1 ss = - и полюс s =-µ лежат в области Re( 0 )s ≤ , а за функцию ( ) s-ψ - выражение в первых скобках ( ) ( ) 1ss ss s+ + ψ= +µ ; ( ) ( ) ( ) 1 * s s s s s A s- -+ ψ= +µ-µ - . Для окончательного построения функции ( ) s-ψ подставим в ее выражение ( ) * As -= 22 2 s λ =  λ+  Тогда функция ( ) s-ψ примет вид ( ) ( ) ( ) ( )( ) ( )( ) ( )( ) ( ) 1 22 2 1 2 22 1 1 2 2 [4 2 2 ( 4 ) 4 ( ) 22 /] , s s s s ss s s s ss s s s s s s s s s s - -+ ψ= = +µ-µ λ λ- - + λ- = = + µ- λ + λ λ-µ - + λ- λ- = = - + - - так как квадратное уравнение, полученное из знаменателя 2 ( 4 ) 4 ( ) 0 ss + - λ + λ λ-µ = µ , имеет один отрицательный корень 2 1 ( 4 )/2 [( 4 )/2] 4 ( )s - = - µ- λ - µ- λ + λ µ-λ и один положительный корень ) ( ( ) 2 2 (4 )/2 [ 4 /2] 4s = λ-µ + µ- λ + λ µ-λ . В случае стабильной системы при λ<µ выполнено условие 4 ( ) 0 λ µ-λ > . Теперь выполнение условий (1) и (2) метода спектрального разложения для построенных функций ( ) s+ψ и ( ) s-ψ очевидно. Это подтверждает и рисунок 1, где отображены нули и полюсы отношения ( ) ( ) / ss +- ψψ на комплексной s-плоскости для исключения ошибок построения спектрального разложения. На рисунке 1 полюсы отмечены крестиками, а нули - кружками. Рисунок 1. Нули и полюсы функции ( ) ( ) / ss +- ψψ для системы E2/M/1 Далее по методике спектрального разложения найдем константу K: ( ) 11 00 lim lim ss s s s sK ss + →→ ψ + = = = +µ µ . Построим функцию ( ) s+Φ , через которую найдем преобразование Лапласа функции плотности времени ожидания: ( ) ( ) ( ) * 1 1 * () ss W s s s ss+ +µ = Φ = µ+ . Производная от функции ( ) * Ws со знаком минус в точке 0 s = : ( ) * 0s dW s ds = -= ( ) ( ) 1 1 1 22 1 0 () s s s s s s ss =  µ + - +µ µ = - µ+   = 22 11 22 11 11 .ss ss µ - µ = = - µµ Тогда среднее время ожидания для системы E2/M/1: 11/ 1/ Ws = - µ , (8) где 2 1 ( 4 )/2 [( 4 )/2] 4 ( ),s = µ- λ + µ- λ + λ µ-λ абсолютное значение корня 1 s- выражается через параметры распределений (3) и (4). Для практического применения формулы (8) в качестве входных параметров для системы E2/М/1 будем использовать числовые характеристики распределений (3) и (4), а именно средние значения интервалов между поступлениями требований и времени обслуживания и коэффициенты вариаций этих интервалов: 1/ λ τ = λ , 1/ , µ τ = µ 1/ 2c λ = , 1 cµ = . Задав эти числовые характеристики, методом моментов определяем параметры распределений (3)-(4) , λ . µ Решение для системы М/E2/1 и его сравнение с формулой Полячека - Хинчина В этом случае функция плотности распределения для интервалов поступления имеет вид ( ) t a t e -λ=λ , (9) а для времени обслуживания ( ) 22 4 t b t te-µ = µ . (10) Преобразование Лапласа (9) и (10) есть ( ) * As s λ = λ+ , ( ) 2 * 2 2 Bs s  µ = µ+  . Тогда спектральное разложение решения ИУЛ для системы М/E2/1 имеет вид ( ) ( ) ( ) ( ) ( )( ) 2 ** 2 2 2 11 2 44 . 2 A s B s ss s s s ss  λµ - × - = × - = λ- µ+   + µ-λ + µ µ-λ = λ- µ+ Квадратный трехчлен в числителе разложения ( ) ( ) 22 44 ss + µ-λ + µ -λµ , где ( )40 µ µ-λ > и ( ) 40 µ-λ > при µ>λ в случае стабильной системы, имеет два действительных отрицательных корня 1 s- , 2 s- : ( ) ( ) ( ) 2 1 4 /2 [ 4 /2] 4s - = - µ-λ + µ-λ - µ µ-λ , ( ) ( ) ( ) 2 2 4 /2 [ 4 /2] 4s - = - µ-λ - µ-λ - µ µ-λ . Тогда окончательно спектральное разложение будет иметь вид: ( ) ( ) ( )( ) ( )( ) 12 22 s s s s s s s ss + - ψ + + = ψ λ- µ+ . (11) Нули и полюсы этого разложения показаны на рисунке 2: полюсы отмечены крестиками, а нули - кружками. Рисунок 2. Нули и полюсы функции ( ) ( ) / ss +- ψψ для системы М/E2/1 Исходя из правил построения функций ( ) s+ψ и ( ) s-ψ (1)-(2) выбираем ( ) ( )( ) ( ) 12 2 , 2 s s s s s s s+ ++ ψ= µ+ ( ) . ss- ψ =λ- Необходимая для получения решения константа ( ) ( ) 12 220 4 lim 1 . 44s s ssK s + → ψ µ µ-λ = = = = -ρ µµ Далее строим функцию ( ) ( ) ( )( ) ( )( ) 2 12 12 sKs s s s s s s+ + -ρ µ+ Φ = = ψ + + , откуда следует, что преобразование Лапласа функции плотности времени ожидания в системе М/E2/1 ( )( ) 2 * 12 12 * s W s s s ssss+ -ρ µ+ = Φ = ++ . (11) В связи с тем, что система М/E2/1 относится к классу М/G/1, воспользуемся результатом для систем данного класса. Уравнение Полячека - Хинчина для преобразования Лапласа функции плотности времени ожидания для системы М/G/1 имеет вид ( ) ( )( ) * * 1 . s Ws s B s -ρ = -λ+λ (12) С учетом равенства преобразования Лапласа ( ) 2 * 2 2 Bs s  µ = µ+  после его подстановки в (12) получим, что ( ) ( )( ) ( )( ) 2 * 12 12 s Ws ssss -ρ µ+ = ++ . Тем самым подтверждено, что преобразование Лапласа функции плотности времени ожидания для системы М/G/1 в случае СМО М/E2/1 совпадает с выражением (11). Среднее время ожидания в системе М/G/1 даG/1 да/1 дается формулой Полячека - Хинчина [2]: ( ) 2 21 W µ λτ = -ρ , (13) где λ - интенсивность входного потока, ρ - коэффициент загрузки системы, 2 µτ - второй начальный момент времени обслуживания. Для распределения E2 второй начальный момент времени обслуживания 22 3/ 2 ) (µ τ = µ , тогда среднее время ожидания в системе М/E2/1: ( ) 3 41 W ρ = µ -ρ . (14) Сравнительные расчеты среднего времени ожидания для систем E2/M/1 и M/E2/1 Для того чтобы лучше оценить количественную разницу между рассматриваемыми двойственными системами, проведем вычислительные эксперименты для среднего времени ожидания по формулам (1), (7) и (11) соответственно. Выше было отмечено, что формулы (1) и (7) дают идентичные результаты. В таблице 1 приведены результаты расчетов для рассмотренных систем для случаев малой загрузки системы ρ = 0,1; средней загрузки ρ = 0,5 и высокой загрузки ρ = 0,9. Здесь ρ - коэффициент загрузки, определяемый отношением среднего времени обслуживания к среднему интервалу поступлений /µλ ρ= τ τ . Для удобства вычислений принято нормированное время обслуживания в обеих системах 1 1 - µ τ =µ =. Таблица 1. Расчет среднего времени ожидания для систем Н2/M/1 и M/H2/1 Входные параметры Среднее время ожидания ρ для системы E2/M/1 для системы M/E2/1 0,1 0.030 0,083 0,5 0,618 0,750 0,9 6,588 6,750 Данные таблицы 1 свидетельствуют о незначительном различии рассмотренных двойственных систем в связи с сравнительно небольшими коэффициентами вариаций используемых законов распределений. В случае других законов распределений двойственные системы G/M/1 и M/G/1 будут давать достаточно отличающиеся результаты. Результаты расчетов хорошо согласуются с данными [9]. Заключение Основная характеристика для СМО - это среднее время ожидания в очереди, так как все остальные характеристики: время задержки, средняя длина очереди, количество требований в системе и другие являются производными от нее. Результаты по среднему времени ожидания в очереди для систем E2/M/1 и M/E2/1 получены одним и тем же методом спектрального разложения решения ИУЛ [1]. Полученные результаты показывают, насколько отличаются эти две двойственные системы, и свидетельствуют о незначительном различии рассмотренных двойственных систем в связи со сравнительно небольшими коэффициентами вариаций используемых законов распределений.

About the authors

V. N Tarasov

Povolzhskiy State University of Telecommunications and Informatics

Samara, Russian Federation

References

Supplementary files