RESEARCH OF QUEUING SYSTEM WITH DISPLACED EXPONENTIAL INPUT DISTRIBUTIONS

Full Text

К системам с запаздыванием в науке и технике можно отнести системы автоматического регулирования, системы автоматического и дистанционного управления, телеметрии и др. В литературе по теории систем массового обслуживания (СМО) и в интернет-ресурсах нет упоминаний о таких системах со смещенными во времени входными распределениями. В основе описания любой СМО, в том числе СМО с запаздыванием, лежит понятие рекуррентного потока [1], определяемого совокупностью функций распределения 12 ( ) ( ) ... F t F t = = = ( ) ... ( )n F t F t = = = между поступающими требованиями. Далее мы рассмотрим случай, когда СМО образована двумя потоками, определяемыми функциями ( ) 0() 0 0 1,; 0, 0 , tt e t t Ft tt -γ - -≥ =  ≤< где 0, γ> и потоки имеют одинаковое время запаздывания 0. t В качестве математической модели таких систем предлагается рассматриваемая ниже СМО с запаздыванием. Рассмотрим СМО, на вход которой поступают требования, случайные интервалы между кото рыми распределены с функцией плотности (см. также рисунок 1) вида ( ) ( ) 0 0 0 ,; 0, 0 . tt e t tat tt -λ - λ≥=  ≤<  (1) Аналогично распределено и время обслуживания: ( ) ( ) 0 0 0 ,; 0, 0 . tt e t tbt tt -µ - µ≥=  ≤<  (2) Рисунок 1. График функции плотности с запаздыванием (1) Функции плотности (1) и (2) являются сдвинутыми вправо от нулевой точки на величину 0t экспоненциальными распределениями с двумя параметрами ( ) 0, tλ и ( ) 0 ,, tµ причем µ λ< (см. рисунок 1). Таким образом, мы имеем СМО с запаздыванием во времени на величину 0 0. t > Заметим, что законы распределения (1) и (2) содержит два параметра, следовательно, они могут быть описаны двумя первыми моментами. Новую СМО, в отличие от классической, обозначим M /M /1. -- Постановка и способ решения задачи Методом спектрального разложения решения интегрального уравнения Линдли (ИУЛ) требуется получить результат по среднему времени ожидания в очереди, а также требуется оценить, как операция сдвига во времени скажется на характеристиках новой СМО M /M /1, -- и чем эта внешне схожая с классической СМО М/М/1 система будет от нее отличаться. Для последующего применения метода спектрального разложения к решению данной задачи сначала определим числовые характеристики интервала поступления требований и времени обслуживания. Для этого воспользуемся преобразованием Лапласа функций плотности (1)-(2): ( ) 0 * tseAs s -λ = +λ ; (3) ( ) 0 * tseBs s -µ = +µ . (4) Первая производная функции (3) ( ) ( ) ( ) 00 0 2 * ts ts dA s t e s e ds s -- -λ +λ -λ = +λ , а ее значение со знаком минус в точке 0: s = ( ) 0 2 10 02 * . s dA s ds t t = - -= λ +λ = =λ + λ По свойству преобразования Лапласа правая часть последнего выражения равна среднему значению интервалов между соседними требованиями входного потока 1 0 t-λ τ =λ + . (5) Из равенства (5) следует, что интенсивность поступления требований 1/ λ ′ λ = τ в СМО M /M /1 -- определяется через параметры распределения (1) как 0 /(1 ). t′ λ =λ +λ (6) Поступая аналогично с функцией (4), находим среднее время обслуживания в системе 1 0. t-µ τ =µ + (7) Тогда интенсивность обслуживания требований ′ µ определяется через параметры распределения (2) из равенства (7): 0 /(1 ). t′ µ =µ +µ (8) Таким образом, интенсивности поступления ′λ и обслуживания ′ µ в системе M /M /1 -- напрямую зависят от интенсивностей λ и µ классической системы и параметра сдвига 0. t Загрузка рассматриваемой системы, определяемая отношением интенсивностей поступления (6) и обслуживания (8), возросла в 0 0 1 1 t t +µ +λ раз по сравнению с системой М/М/1: 0 0 (1 ) (1 ) t t ′ λ λ +µ ρ= = ′ µ µ +λ . (9) Из равенств (5) и (7) следует, что в качестве входных параметров системы удобнее использовать средние значения интервалов λ τ и , µτ так как их отношение /µλ ρ= τ τ определяет загрузку СМО. Определим начальный момент второго порядка интервалов поступления. Для этого находим значение второй производной от функции (3) при 0.s = Тогда 22 0 0 2 22 ttλ τ = + + λλ и, с учетом того, что дисперсия интервалов для распределения (1) равна 2, D - λ =λ получим коэффициент вариации интервалов входного потока ( ) 1 0 1. ct - λ = +λ (10) Аналогично определим коэффициент вариации времени обслуживания. Дисперсия этого времени 2, D - µ =µ а коэффициент вариации ( ) 1 0 1. ct - µ = +µ (11) Заметим, что коэффициенты вариации cλ и cµ меньше единицы при 0, t , λ 0. µ> Полученные числовые характеристики позволяют сделать следующие предположения. 1. Операция сдвига во времени приводит к увеличению загрузки системы в 0 0 1 1 t t +µ +λ раз, чем в классической системе М/М/1. 2. В связи с тем, что коэффициенты вариации интервалов поступления cλ и времени обслуживания cµ меньше единицы, мы имеем немарковскую модель массового обслуживания. Среднее время ожидания требования в очереди в такой системе должно быть меньше, чем в системе M/M/1 при одинаковом коэффициенте загрузки, так как cλ и cµ для системы M/M/1 равны единице. 3. Использование функций плотности (1) и (2) позволяет аппроксимировать исходные входные распределения, в отличие от классической СМО, на уровне двух первых моментов. Таким образом, мы выделили основные отличия рассматриваемой системы от классической СМО, но, как оказывается, между ними есть и много общего. Определение среднего времени ожидания в очереди для системы -- M /M /1 на основе метода спектрального разложения ИУЛ Основные характеристики системы G/G/1, как следует из [2], описываются известными из теории случайных процессов интегральными уравнениями типа Винера - Хопфа. Одно из этих уравнений в [2] выведено в форме интегрального уравнения Линдли: ( ) ( ) ( ), 0; 0, 0, y W y u dC u y Wy y -∞  -≥=   <  ∫ (12) где ( ) Wy - функция распределения вероятностей времени ожидания требования в очереди, ( ) Cu - аналогичная функция предельной случайной величины lim n n UU →∞ = = 1; nn xt +- n x - время обслуживания n-го требования ; nC 1 nt + - интервал времени между поступлением требований nC и 1. nC + Важно заметить, что интегральная форма уравнения (12) имеет место только для неотрицательных значений аргумента y, так как для отрицательных значений аргумента функция ( ) 0. Wy≡ Суть решения ИУЛ (12) спектральным методом сводится к тому, чтобы для выражения ( ) ( ) * * 1 A s B s -- (13) найти представление в виде произведения двух множителей, которое давало бы рациональную функцию от s [2]. Таким образом, для нахождения распределения времени ожидания необходимо следующее спектральное разложение: ( ) ( ) ( ) ( )* * 1 s A s B s s + - ψ - - = ψ , (14) где ( ) s+ψ и ( ) s-ψ - некоторые рациональные функции от s, которые можно разложить на множители. Функции ( ) s+ψ и ( ) s-ψ должны удовлетворять определенным условиям [2]. 1. Для ( ) Re 0 s > функция ( ) s+ψ является аналитической без нулей в этой полуплоскости. 2. Для ( ) Re sD < функция ( ) s-ψ является аналитической без нулей в этой полуплоскости, где D - некоторая положительная константа, определяемая из условия ( ) lim . Dtt at e-→∞ <∞ (15) Кроме того, функции ( ) s+ψ и ( ) s-ψ должны обладать следующими свойствами: ( ) ( ) ( ) ( ) Re 0 lim 1; Re 0 lim 1. äëÿ : äëÿ : S S s s s s s s + →∞ - →∞ ψ - > = ψ - < = - (16) Таким же путем получены решения для систем с гиперэкспоненциальными входными распределениями в работах [3; 6-7]. Определим теперь спектральное разложение (14) для распределений (1)-(2) с учетом преобразований Лапласа (3)-(4). Метод спектрального разложения для решения ИУЛ (12) в этом случае дает ( ) ( ) 00 1 t s t ss ee s s s - + - ψ λµ = - ψ λ- µ+ , где ( ) s+ψ и ( ) s-ψ должны быть рациональными функциями. Выполнив несложные вычисления, получим ( ) ( ) ( )( ) ( )( ) ( ) ( )( ) s s s s s s s s s s + - ψ λµ- λ- µ+ +µ-λ = = ψ λ- µ+ λ- µ+ . Таким образом, показатели степени у экспонент в числителе дроби обнуляются, и тем самым операция сдвига нивелируется. Следовательно, спектральные разложения решения ИУЛ для систем M /M /1 -- и M/M/1 совпадают, так как функция ( ) ( ) ( ) ( )( ) s s s s s s + - ψ +µ-λ = ψ λ- µ+ (17) является спектральным разложением для решения системы М/М/1 [1]. Совпадение разложения (17) с результатом для системы М/М/1 является чисто внешним, так как здесь параметры λ и µ не являются для системы M /M /1 -- интенсивностями поступления и обслуживания соответственно. Далее, следуя [2], в качестве функции ( ) s+ψ выбираем ( ) ( ) ( ) ss s s+ +µ-λ ψ= µ+ , которая не имеет нулей и полюсов в области ( ) Re 0, s > а в качестве функции ( ) , ss- ψ =λ- которая не имеет нулей в области ( ) Re . s <λ Постоянная K определяется из условия: ( ) 00 lim lim 1 sS s sK ss + →→ ψ +µ-λ = = = -λ µ +µ , где параметры λ и µ определяются выражениями (5) и (7) и отношение /λµ не определяет коэффициент загрузки как в случае системы М/М/1. Преобразование Лапласа для функции распределения времени ожидания согласно [2] имеет вид ( ) ( ) ( )( ) ( ) 1 sKs ss+ + -λ µ µ+ Φ = = ψ +µ-λ . Следовательно, преобразование Лапласа функции плотности времени ожидания ( ) ( ) ( )( ) ( ) 1 * s W s s s s+ -λ µ µ+ = Φ = +µ-λ . (18) Найдем первую производную от (18): ( ) ( )( ) ( )( ) ( ) ( ) ( ) 2 2 * 11 1 . dW s ds ss s s = -λ µ +µ-λ - -λ µ µ+ = = +µ-λ -λ -λ µ = +µ-λ Тогда значение первой производной со знаком минус при s = 0 будет равно ( ) ( ) ( ) ( ) 2 0 *1 / s dW s ds = λ -λ µ λµ - = = µ-λµ-λ . Отсюда среднее время ожидания W λµ = µ-λ . (19) Результат (19) полностью совпадает с результатом для системы М/М/1, где 1 W ρµ = -ρ (20) при значении . ρ=λµ Таким образом, формулы для среднего времени ожидания для системы с запаздыванием M /M /1 -- и для системы М/М/1 совпадают при одинаковых значениях параметров λ и , µ создавая при этом разные нагрузки на системы. Это интересный факт сходства двух различных систем. Определение неизвестных параметров рассматриваемых распределений Полученные числовые характеристики распределений (1) и (2) в виде равенств (5), (7), (10) и (11) позволяют определить неизвестные параметры , λ µ и 0. t Запишем их в виде системы уравнений 1 0 1 0 1 0 1 0 , (1 ) , , (1 ) , t tc t tc - λ - λ - µ - µ  λ + = τ  +λ =   µ + = τ   +µ =  (21) где числовые характеристики в правых частях системы будут входными параметрами системы для определения неизвестных параметров. Система (21) является переопределенной, и поэтому мы получим ограничение на входные параметры СМО , λτ , cλ µ τ и . cµ Для решения системы из первого уравнения выразим 0: t 1 0 .t - λ = τ -λ Второе уравнение дает 1/(1 1) , c λλ +λτ - = откуда 1/( ) cλλ λ = τ . (22) Третье уравнение дает 11 , -- λµ µ + τ -λ = τ тогда ( ) 1 1 c µ λ λ µ= τ - τ - . (23) Из четвертого уравнения получим следующее ограничение: ( ) ( ) 1 , 1 1 1 c c c µ λλ µ λ λ = τ- + τ - τ - отсюда ( ) ( ) 1 1 1 , c cc µ λ λ µλ µ τ - τ - = = - - ρ τ где /. µλ ρ= τ τ Окончательно коэффициент вариации времени обслуживания есть ( ) 1 1 . cc µλ = -ρ - (24) Таким образом, входные параметры системы M /M /1: -- , λτ , cλ µ τ и cµ строго связаны соотношением (23). Примеры расчета среднего времени ожидания для системы M-/M-/1 В качестве примера рассмотрим случаи разных нагрузок. Примем следующие значения входных параметров СМО: 1, µ τ= 10 λ τ= и 0,5. cµ = Тогда ограничение (24) при загрузке 0,1 ρ= дает c λ = Далее определим неизвестные параметры λ и . µ Из (22) находим значение 1/9,5 λ = =2/19, а из (23) 1/ 1 10 0,5 () µ = - ⋅ =2. Тогда среднее время ожидания из (19) есть 119/36 19 W = = 1/36. Для сравнения среднее время ожидания для системы М/М/1 при такой же нагрузке 0,1 ρ= и интенсивности обслуживания 1 µ= равно 0,11 1 1 0,9 9 W ρµ = = = -ρ , что в четыре раза больше, чем в системе с запаздыванием M /M /1 -- . В качестве второго примера рассмотрим случай высокой нагрузки: 1, µ τ= 10/9 λ τ= и 0,5.c µ = В этом случае получим загрузку 0,9; ρ= ограничение (24) дает 0,55, cλ = а равенства (22)- (23) - значения 18/11 λ= и 2. µ= Тогда среднее время ожидания 1811 2 18 11 9 2 1811 4 22 4 W ⋅ = = = -⋅ . Система М/М/1 при той же нагрузке дает 0,9 1 9 1 0,9 W = = - . Расчетные данные хорошо согласуются с результатами двухмоментной аппроксимации [8]. Заключение Рассмотренная СМО с запаздыванием M /M /1 -- позволяет рассчитать ее характеристики при коэффициентах вариации интервалов между поступлениями требований cλ и времени обслуживания , cµ меньших единицы при некоторых ограничениях на входные параметры системы. Учитывая тот факт, что основные характеристики СМО, такие как средняя длина очереди, среднее количество требований в системе и другие, являются производными от среднего времени ожидания, они в статье не рассмотрены. Полученные результаты приводят к следующим выводам. 1. Операция сдвига во времени приводит к увеличению загрузки системы в 0 0 1 1 t t +µ +λ раз по сравнению с классической системой М/М/1. 2. В связи с тем, что коэффициенты вариации интервалов поступления cλ и времени обслуживания cµ меньше единицы, мы получили немарковскую модель массового обслуживания G/G/1, для которой существует решение в замкнутой форме. Среднее время ожидания требования в очереди в такой системе меньше, чем в системе M/M/1 при одинаковом коэффициенте загрузки. 3. Использование функций плотности (1)-(2) позволяет аппроксимировать исходные входные распределения в СМО на уровне двух первых моментов, в отличие от классической системы.

About the authors

V. N Tarasov

Povolzhskiy State University of Telecommunications and Informatics

Samara, Russian Federation

N. F Bakhareva

Povolzhskiy State University of Telecommunications and Informatics

Samara, Russian Federation

E. G Akhmetshina

Povolzhskiy State University of Telecommunications and Informatics

Samara, Russian Federation

References

Supplementary files