close

Вход

Забыли?

вход по аккаунту

?

Распределения времени ожидания в системе с FCFS орбитой и пороговым управлением.

код для вставкиСкачать
Теория вероятностей и случайные
процессы
УДК 519.21
Распределения времени ожидания в системе с FCFS
орбитой и пороговым управлением
Д. В. Ефросинин
Кафедра теории вероятностей и математической статистики
Российский университет дружбы народов
ул. Миклухо-Маклая, 6, Москва, 117198, Россия
Проводится анализ времени ожидания в марковской системе с повторными заявками,
несколькими неоднородными приборами и пороговой политикой управления. Блокированные заявки ожидают своей очереди на орбите бесконечной ёмкости с FCFS дисциплиной обслуживания. Система исследуется в стационарном режиме. Выводятся выражения для преобразований Лапласа времени ожидания, производящих функций числа
повторных попыток до момента поступления на прибор, а также для моментов рассматриваемых величин. Приводятся численные примеры с иллюстрациями и их обсуждение.
Ключевые слова: СМО с неоднородными приборами, пороговая политика, распределение времени ожидания, FCFS орбита.
1.
Введение
Многие системы массового обслуживания обладают такой особенностью, что
новая заявка, не получившая обслуживание, повторяет попытку занять прибор
через некоторое случайное время. Между попытками заявка пребывает на так
называемой орбите. В данной работе предполагается, что повторную попытку
занять прибор осуществляет только заявка, стоящая во главе орбиты, то есть
имеет место FCFS дисциплина обслуживания или дисциплина постоянных повторов. Обслуживание в рассматриваемой системе происходит в соответствии с
пороговой дисциплиной управления, задаваемой набором пороговых уровней для
каждого прибора. Включение более медленного прибора при поступлении заявки происходит при достижении числа заявок на орбите соответствующего порогового уровня. Ссылки на соответствующую литературу, а также мотивировка
использования подобного типа систем приведены в предыдущей работе автора,
см. [1].
В настоящей работе рассматривается задача вычисления стационарных распределений времён ожидания и пребывания заявки в системе. Время ожидания
является одной из наиболее важных характеристик с точки зрения пользователя системой обслуживания. Для неуправляемых СМО с повторными заявками
распределение времени ожидания может быть получено путём вычисления распределений условных времён ожидания маркированной заявки после её поступления в некоторое состояние, см., например, [2]. Для систем с повторными заявками предложены рекуррентные методы вычисления распределения времени
ожидания в терминах преобразования Лапласа, см., например в [3–5]. Как показано в [6], в случае управляемых систем без повторных заявок, для вычисления
распределения времени ожидания необходимо ввести дополнительный случайный
процесс, определяющий положение маркированной заявки в очереди. Аналогичный случайный процесс необходим также и для системы, рассматриваемой в данной работе, так как, во-первых, пороговая политика оказывает влияние на время
обслуживания и, как следствие, на время ожидания маркированной заявки, а
Статья поступила в редакцию 10 мая 2010 г.
Ефросинин Д. В. Распределения времени ожидания в системе с FCFS . . .
55
во-вторых, предполагается, что новая заявка может иметь прямой доступ к прибору в соответствии с политикой управления, что может привести к увеличению
времени ожидания заявки на орбите.
Основной сложностью анализа системы с неоднородными приборами является
многомерность соответствующего марковского процесса, что значительно усложняет процесс получения аналитических результатов. Одним из наиболее часто и
успешно используемых аппаратов исследования многомерных марковских моделей является матрично-аналитический подход [7], применение которого позволяет
получить результаты также и для управляемых многомерных систем. Проведённый анализ СМО с дисциплиной постоянных повторов, неоднородными приборами и пороговой политикой управления включает следующие результаты:
а) вычисляются преобразования Лапласа времени ожидания заявки и производится соответствующее обратное преобразование. Исследуется также дискретный аналог времени ожидания в виде распределения числа повторных попыток занять прибор до момента успешного поступления;
б) приводятся рекуррентные алгоритмы вычисления произвольных моментов
времени ожидания, а также факториальных моментов числа повторных попыток, сделанных заявкой до момента поступления на прибор с орбиты.
Статья организована следующим образом. В разделе 2 описывается математическая модель системы и кратко представляется стационарное распределение
состояний системы. В разделах 3 и 4 проводится вычислительный анализ времени
ожидания и пребывания заявок в системе. Формулы вычисления распределения
числа повторных попыток и их факториальных моментов выводятся в разделе 5.
Раздел 6 содержит численные эксперименты и их краткое обсуждение.
Далее в работе использованы обозначения (),  () и  соответственно для
единичного вектор-столбца размера , нулевого вектор-столбца размера  с 1 на
j-м месте (начиная с 0), единичной матрицы размера . Если указание размера не
имеет большого значения, будем опускать аргумент в скобках, тогда  обозначает
единичный вектор соответствующего размера. Далее, diag (1 , . . . ,  ) обозначает диагональную матрицу с блочными элементами 1 , . . . ,  , diag + (1 , . . . ,  )
и diag − (1 , . . . ,  ) — соответственно, нулевые матрицы с над- и поддиагональными блочными элементами 1 , . . . , −1 . Будем использовать также обозначение
(a) = diag (1 , . . . ,  ), где вектор a = (1 , . . . ,  ), а также стандартное обозначение 1{} для индексной функции, принимающей значение 1 при выполнении
события  и 0 — в противном случае. Символ ⊗ используется для обозначения
Кронекерова произведения матриц и векторов и верхний символ  — для транспонированных векторов.
2.
Математическая модель и стационарное распределение
состояний
Рассмотрим систему, подробно описанную в работе [1]. Напомним, что данная
система состоит из  неоднородных приборов с интенсивностями обслуживания
1 > . . . >  > 0, в которую поступает простейший поток заявок интенсивности
. Заявка во главе орбиты повторяет попытку занять прибор через экспоненциально распределённое время с параметром . Самый быстрый прибор с индексом
1 включается всякий раз, когда поступает новая или повторная заявка. Более медленные приборы включаются в соответствии с пороговой политикой управления
(2 , . . . ,  ), представленной в [1].
Динамическое поведение системы описывается  + 1-мерной цепью Маркова
{()}>0 = {(), ()}>0
с пространством состояний  = { = (, 1 , . . . ,  );  > 0,  ∈ {0, 1},  = 1, }.
Здесь () обозначает число заявок на орбите, а () = (1 (), . . . ,  ()) — вектор состояний приборов в момент времени . Элементы  () принимают значения
56
Вестник РУДН. Серия Математика. Информатика. Физика. № 1. 2011. С. 54–74
0 или 1, соответственно, если прибор свободен или занят. Как и прежде, перенумеруем состояния цепи Маркова в лексикографическом порядке и далее считаем
i состоянием цепи Маркова, учитывая, что это макросостояние, состоящее из 2
состояний i = {(, );  ∈ },  > 0. Порядковый номер состояния приборов  для
некоторого фиксированного  обозначим через # = 0, 2 − 1.
Как было показано в [1], цепь Маркова {()}>0 является обобщённым процессом рождения и гибели (ПРГ) на пространстве состояний  с инфинитезимальной матрицей Λ, имеющей трёхдиагональную блочную структуру с большим
числом пограничных состояний,
Λ=
= diag (1,0 , 1,1 , . . . , 1,1 , 1,2 , . . . , 1,2−1 , . . . , 1,2−1 , 1,2 , . . . , 1,2−1 , . . .)+
⏟
⏞
⏟
⏞
2 −2
+1 − −1
+
+ diag (0,1 , . . . , 0,1 , . . . , 0, , . . . , 0, , . . . , 0, , . . .)+
⏟
⏞
⏟
⏞
+1 −
2 −1
−
+ diag (2,1 , . . . , 2,1 , . . . , 2, , . . . , 2, , . . . , 2, , . . .),
⏞
⏞
⏟
⏟
 = 1,  − 1,
+1 −
2 −1
где (1,0 + 0,1 ) = 0, (2, + 1,2−1 + 0, ) = 0,  = 1, , (2,−1 + 1,2−2 +
0, ) = 0,  = 2, . Блоки 1, , 2, и 0, представляют собой квадратные матрицы размера 2 и содержат следующие интенсивности. Блоки 1, ,  = 0, 2 − 1
включают в себя интенсивности переходов без изменения числа заявок на орбите.
Блоки 0, ,  = 1,  описывают интенсивности поступления новых заявок, так
что число заявок на орбите увеличивается на единицу, а блоки 2, ,  = 1,  —
интенсивности успешных повторных заявок с одновременным уменьшением на
единицу числа заявок на орбите.
Блоки 1, , 2, и 0, представляют собой квадратные матрицы размера 2 .
Блоки 1, ,  = 0, 2 − 1 имеют трёхдиагональную блочную структуру:
⎛
1,
1,0
()
0,1
()
0
0
...
⎜
⎜2,1
⎜
⎜
⎜ 0
=⎜
⎜ .
⎜ ..
⎜
⎜
⎜ 0
⎝
0
1,1
()
0,2
()
0
...
2,2
1,2
()
0,3
()
...
..
.
..
..
..
...
0
2,−1
1,−1
...
0
0
2,
.
.
0
.
()
⎞
⎟
0 ⎟
⎟
⎟
0 ⎟
⎟
⎟,
⎟
⎟
⎟
() ⎟
0, ⎠
()
1,
 = 0, 2 − 1.
(︂ )︂ (︂
)︂


Прямоугольные блоки 2, ,  = 1, , имеют размер
×
и содержат

−1
интенсивности обслуживания в зависимости от набора занятых приборов:
2, = −1, ,
 = 1, ,
где
,
⎛
−1,
⎜ 0
⎜
=⎜ .
⎝ ..
0
−1,+1
..
.
...
..
.
0
..
.
−1,
⎞
, −
,+1 +1− ⎟
⎟
⎟,
⎠
, −
 = 1,  − 1,
Ефросинин Д. В. Распределения времени ожидания в системе с FCFS . . .
0, = ( , +1 , . . . ,  ) ,
(︂
, =
57
)︂
 −+
.

()
Диагональные блоки 1, ,  = 0, , содержат интенсивности пребывания в
соответствующих
(︂ )︂ (︂ )︂состояниях и представляют собой диагональные матрицы раз

мера
×
с элементами, зависящими от числа заявок на орбите:


(︃
)︃
()
1,
=− +

∑︁
 () + 
=1

∑︁
1{∈{2−1,2},  ()=1,=1,−1,  ()=0}
, .
=1
Порядковый номер состояния # определяет номер строки и столбца соответствующего элемента.
(︂ )︂ (︂
)︂


()
Прямоугольные блоки 0, ,  = 1,  размера
×
содержат ин
−1
тенсивности поступления новых требований в зависимости от числа заявок на
орбите:
()
0, = 

∑︁
1{∈{2−2,2−1},  ()= ()=1,=1,−1,  ()= (), =+1,,  ()=1,  ()=0} ×
=1
× , ×, /1, ,
где матрица  состоит из единиц, а порядковые номера состояний # и # определяют соответственно столбец и строку элемента.
Блоки 2, и 0, ,  = 1,  имеют вид:
⎛
()
0 0,1
0
0
⎜
()
⎜0
0
0,2
0
⎜
⎜
()
0
0
0,3
⎜0
2, = ⎜
⎜
..
..
⎜. . . . . .
.
.
⎜
⎜
⎝0
...
0
0
0
...
0
0
(︃
0, =  1 −

∑︁
...
...
...
..
.
0
0
0
⎞
⎟
0 ⎟
⎟
⎟
0 ⎟
⎟ ,  = 1, ,
⎟
⎟
⎟
() ⎟
0, ⎠
0
)︃
1{∈{2−1,2},  ()=1,=1,−1,  ()=0}
2 ,
 = 1, .
=1
Обозначим через  = ( 0 ,  1 ,  2 , . . .) макровектор строку стационарных вероятностей состояний системы, где   обозначает суб-вектор состоящий из вероятностей  с () = , соответствующий макросостоянию i. Вектор  удовлетворяет
соотношениям Λ = 0,  = 1.
Вычисление вероятностей состояний может быть сведено к решению конечной
трёхдиагональной блочной системы, используя матрично-геометрическое представление для вероятностей состояний выше верхнего порога  , когда оптимальным является использование самого быстрого из свободных приборов, см. [1].
Заметим, что в дальнейшем, при анализе времени ожидания и времени пребывания, а также числа повторов, блочные трёхдиагональные матричные выражения
будут встречаться повсеместно, что также приводит к необходимости использования матричных методов, например, блочную обратную подстановку, блочный
итерационный метод Гаусса–Зейделя и т.д.
58
Вестник РУДН. Серия Математика. Информатика. Физика. № 1. 2011. С. 54–74
3.
Распределение времени ожидания
В данном разделе приводится процедура вычисления распределения времени ожидания заявок на орбите в системе с пороговым управлением (2 , . . . ,  ).
В системах массового обслуживания с пороговым управлением время ожидания
маркированной заявки зависит от будущих поступлений новых заявок в течение
её времени ожидания, так как политика управления может изменять набор приборов, доступных для принятия заявок. Также следует принимать во внимание
тот факт, что более поздние заявки могут быть раньше обслужены, так как в соответствии с политикой управления они могут иметь прямой доступ к свободным
приборам. Подобные свойства системы, а также многомерность марковской цепи
значительно усложняют проводимый анализ.
Для вычисления распределения времени ожидания маркированной заявки необходимо исследовать вспомогательную поглощающую цепь Маркова, начальный
момент времени функционирования которой + совпадает с поступлением новой
заявки на орбиту после получения отказа на обслуживание. Моментом поглощения является момент безвозвратного ухода этой заявки с орбиты. Определим
следующую  + 1-мерную поглощающую цепь Маркова
^
{()}
>+ = {(), (), ()}>+
(1)
с пространством состояний
{︀
}︀
^ =  = (, , );  > 0,  = (1 , . . . ,  ),  ∈ {0, 1},  = 1, ,  = 0,  ,

где последняя компонента () обозначает положение маркированной заявки в
списке ожидающих обслуживания заявок в момент времени . Процесс () может принимать значения {0, 1, 2, . . .} и убывает на единицу всякий раз, когда в
момент поступления повторной заявки один из приборов с индексом ,  = 1,  − 1
является свободным и число заявок на орбите вместе с поступающей заявкой
принимает значения  = −1 ,  − 1,  = 2, .
^
Цепь Маркова {()}
достигает поглощающего состояния, когда компонента
() становится равной нулю. Заметим, что () > () в любой момент времени , когда маркированная заявка находится на орбите. В момент поступления
+ маркированной заявки очевидно, что (+ ) = (+ ), если заявка направляется на орбиту и (+ ) = 0, если в момент поступления маркированная заявка
направляется на один из свободных приборов.
Введём следующие обозначения:  — случайная величина времени ожидания,
 — случайная величина остаточного времени ожидания, при условии начального состояния ,  () —∫︁плотность распределения остаточного времени ожида∞
ния, 
˜ () = E[− ] =
0
−  ()d, Re[] > 0 — преобразование Лапласа–
1
˜ () = ()
˜
— безусловное преобразоваСтилтьеса времени ожидания, ()
˜
и

ние Лапласа-Стилтьеса (ПЛС) и преобразование Лапласа (ПЛ).
Пусть w̃() обозначает вектор условных ПЛС, упорядоченных следующим образом
w̃() = (w̃1 (), w̃2 (), . . .) , w̃ () = (w̃, (), w̃+1, (), . . . , w̃+ −1, ()) ,  > 1,
w̃, () = (
˜(,0,0,...,0,) (), 
˜(,1,0,...,0,) (), . . . , 
˜(,1,1,...,1,) ()) ,
 >  > 1.
Для начала рассмотрим ситуацию, когда маркированная заявка находится во
главе орбиты, а число заявок на орбите превышает максимальный пороговый
уровень  . В этом случае повторная попытка заявки во главе орбиты занять
прибор является успешной, если как минимум один прибор свободен, независимо
от его индекса и числа заявок на орбите.
Ефросинин Д. В. Распределения времени ожидания в системе с FCFS . . .
59
Исследуем случайный период времени Θ от некоторого произвольного момента времени до момента успешного повторного поступления заявки, стоящей
во главе орбиты, на какой-либо свободный прибор, при условии некоторого состо˜  ()
яния приборов  ∈ . Обозначим через ˜, () ПЛС времени Θ , а через 
вектор-столбец с компонентами ˜ () упорядоченными в лексикографическом по˜  () = (˜, ();  ∈ ) .
рядке, 
Далее воспользуемся вспомогательной цепью Маркова {()}>0 с непрерывным временем, описывающую состояния приборов в момент времени  с 2 несущественными состояниями  ∈  и 2 − 1 поглощающими состояниями  ∈ ,
куда уходит цепь после успешной повторной попытки поступления. Множество 
состоит из элементов  +  1{= min {: =0}} .
=1,
На рис. 1 изображена диаграмма интенсивностей переходов для некоторого
состояния  = (1 , . . . ,  ) ∈  ∖ {(1, . . . , 1)}. Заметим, что переход из состояния
 в состояние  +  за счёт поступления новой заявки на свободный прибор с
индексом  возможен, если  = 0, где  = min{ :  = 0}.

Рис. 1. Диаграмма переходов для некоторого состояния  ∈  поглощающей
цепи Маркова
Переход из состояния  +  в состояние  происходит за счёт окончания обслуживания на приборе с индексом  ∈ { :  = 0}. Переход из несущественного
состояния  ∈  ∖ {(1, . . . , 1)} в поглощающее состояние  ∈  происходит после
повторной попытки поступления. Наконец, из состояния  = (1, . . . , 1), где все
приборы заняты, возможны переходы только за счёт окончания обслуживания.
˜  () удовлетворяет следующему соотношению
Лемма 1. Вектор ПЛС 

˜  () = −−1

1,2−1 ()2, (2 ),
(2)
где 1,2−1 () = 1,2−1 − 2 + 0, .
Доказательство. Для некоторого состояния  = (1 , . . . ,  ) ∈ , используя
свойства марковости рассматриваемого процесса, получим
(︁
 + ( + )1{︂∑︁
}︂
=1
 6−1
+

∑︁
=1
=  ˜,+ ()1{︃
}︃
= min {: =0}
=1,
)︁
  ˜, () =
+

∑︁
=1
  ˜,− () + 1{︂∑︁
=1
}︂ .
 6−1
Выражая последние равенства для всех возможных состояний  в матричном
виде, получим выражение (2).
60
Вестник РУДН. Серия Математика. Информатика. Физика. № 1. 2011. С. 54–74
Лемма 2. Вектор ПЛС w̃, (),  > + −1,  > 1, вычисляется по формуле


w̃, () = (−−1
1,2−1 ()2, ) (2 ),  > 0.
(3)
Доказательство. Вычислим ПЛС w̃,2 () времени ожидания второй заявки
на орбите. Это время представляется в виде суммы времени ожидания впереди
стоящей заявки до момента попадания на прибор и времени ожидания второй
заявки, занявшей первую позицию на орбите. Очевидно, что вектор ПЛС первой
˜  (),  ≥  . Для ПЛС второй
компоненты удовлетворяет равенству w̃,1 () = 
−1
компоненты имеем w̃,2 () = −1,2−1 ()2, w̃−1,1 (). Учитывая порядок FCFS
обслуживания заявок на орбите, ПЛС времени ожидания -ой заявки на орбите
вычисляется по формуле w̃, () = −−1
1,2−1 ()2, w̃−1,−1 (). Рекуррентная
подстановка влечёт (3).
Теорема 1. Векторы ПЛС w̃ (),  > 1 условного времени ожидания удовлетворяют следующему матричному соотношению
w̃ () = (−1)

∏︁

(Λ̃−1
,−+1 ()Γ̃,−+1 ())( 2 ),  > 1,
(4)
=1
где Λ̃, () = Φ − ^ 2 , ^ 2 = 2 ⊗ (( ) −  −1 ( )), Γ̃, () = Γ +

˜ (), ˜ () = (−−1
1,2−1 ()2, ) ⊗ ( −1 ( )) — квадратные матрицы размера  2 , причём Λ̃, () = Λ̃, () и Γ̃, () = Γ̃, () для  ≥  . Матрицы Φ и Γ состоит из  блочных строк и столбцов с элементами, формирующими матрицу Λ:
Φ = diag (1,2−1 , . . . , 1,2−1 , 1,2 , . . . , 1,2−1 , . . . , 1,2−1 , 1,2 , . . . ,
⏟
⏞
⏞
⏟
+1 − −1
+1 −−1
. . . , 1,2−1 , . . . , 1,2−1 , 2 )+
⏟
⏞
−1
+
+ diag (0, , . . . , 0, , . . . , 0, , . . . , 0, , . . . , 0, , . . . , 0, ),
⏟
⏞
⏟
⏞
⏟
⏞
+1 −
+1 −−1

 =  , +1 − 1,  =  + 1,  − 1,  = 1,  − 2,
Φ = diag (1,2−1 , . . . , 1,2−1 , 2 ) + diag + (0, , . . . , 0, ),
⏟
⏞
⏟
⏞
 −1

Γ1 = diag (2,1 , . . . , 2,1 , . . . , 2, , . . . , 2, , . . . , 2,−1 , . . . , 2,−1 , 0),
⏟
⏟
⏟
⏞
⏞
⏞
2 −1
+1 −
 −−1
 = 1, ,  =  + 1,  − 1,
Γ =
= diag (2, , . . . , 2, , . . . , 2, , . . . , 2, , . . . , 2,−1 , . . . , 2,−1 , 2, , . . . , 2, , 0),
⏟
⏟
⏟
⏞
⏟
⏞
⏞
⏞
+1 −
+1 −
 −−1
−1
 =  , +1 − 1,  =  + 1,  − 1,  = 1,  − 2.
Ефросинин Д. В. Распределения времени ожидания в системе с FCFS . . .
61
Доказательство. Обозначим через  () и  (),  = 1, , следующие
события и их дополнения  () = {() >  ,  () = 1,  = 1,  − 1,  () = 0},
 () = {() 6  − 1,  () = 1,  = 1,  − 1,  () = 0}. Анализируя переходы
^
цепи Маркова {()}
>0 , с учётом введённых обозначений, получим следующую
^
систему уравнений для для ПЛС 
˜ (),  = (, 1 , . . . ,  , ) ∈ 
(︁

∑︁
++
1{ ()} +
=1
=

∑︁
(︁

∑︁
)︁
  
˜ () =
=1

˜+ ()1{ −1 ()} + 
˜+0 ()1{
=1
+

∑︁
)︁
 −1
()}
+

∑︁
  
˜− ()+
=1

˜−0 −+1 + ()1{ ()} ,
^
 ∈ ,
=1
причём 
˜ () = 1 для состояний  = (, , 0), где  > 0. Заметим также, что
по формуле (3) можно вычислить ПЛС времени ожидания в явном виде для
состояний  = (, , ), где  >  +  − 1,  ∈ ,  > 1. Более того, очевидно, что
w̃, () = −−1
 >  +  − 1,
1,2−1 ()2, w̃−1,−1 (),
˜  (),  >  .
w̃,1 () = 
 > 2,
(5)
Группируя интенсивности переходов в блочные матрицы и используя обозначение w̃ () для векторов условных ПЛС, с учётом последнего замечания получим
следующее рекуррентное матричное соотношения
Λ̃, ()w̃ () = −Γ̃, ()w̃−1 (),  > 1,
w̃0 () = ( 2 ),
(6)
где Λ̃, () = Λ̃, () и Γ̃, () = Γ̃, () для  >  . Дальнейшая рекуррентная подстановка приводит к выражению (4). Таким образом, теорема доказана.
Теорема 2. Векторы ПЛС w̃, (), 1 6  6  6  +  − 2 могут быть
вычислены используя следующие рекуррентные соотношения

−−1
˜ +1
w̃, () = 
,2−1 ()w̃+1 −1, ()+
+1 −−2
+
∑︁

˜ ,2−1 ()w̃−1+,−1 (),
˜ ,2−1
()

 =  , +1 − 2,
 = 1,  − 1,
=0
(7)
˜ ,2 ()w̃ , () + 
˜ ,2 ()w̃ −2,−1 (),
w̃+1 −1, () = 
+1
+1
˜  +−−1 ()w̃ +−1, ()+
w̃, () = 

,2−1
+
 +−−2
∑︁

˜ ,2−1
˜ ,2−1 ()w̃−1+,−1 (),

()
 =  ,  +  − 2,
=0
w̃ +−1, () = −−1
1,2−1 ()2, w̃ +−2,−1 (),
w̃,0 () = (2 ),
˜ ,. () и 
˜ ,. () определяются следующим образом
где матрицы 
62
Вестник РУДН. Серия Математика. Информатика. Физика. № 1. 2011. С. 54–74
˜ ,2−1 () = (1,2−1 − )−1 0, , 
˜ ,2−1 () = (1,2−1 − )−1 2, ,

˜ ,2 () = (1,2 − )−1 2, . (8)
˜ ,2 () = (1,2 − )−1 0,+1 , 

Доказательство. Рассмотрим рекуррентные соотношения (6) для макровекторов w̃ (). Выпишем соответствующие соотношения для подвекторов w̃, (), 1 6
 6  6  +  − 2, учитывая двухдиагональную блочную структуру матриц
˜ +, () и 
˜ +, () матрицы, имеюΛ, () и выражения (5). Обозначим через 
щие структуру (8). Тогда полученные соотношения примут вид (7).
Заметим, что согласно пороговой политике управления маркированная заявка
должна направляться на орбиту, если она поступает в одно из состояний подмножества  = { = (, );  = −1 − 1,  − 2,  = 1,  = 1,  − 1,  = 2,  + 1}.
Обозначим через   бесконечную вектор-строку, элементами которого являются
вероятности состояний из множества  :
^ 0 ^1 , . . . , 
^ 2 −2 ^1 , . . . , 
^ −1 −1 ^−1 , . . . , 
^  −2 ^−1 , 
^  −1 ^ , . . .),
  = (
1
^  =   ⊗ 0 (  ),  > 0.
где ^ = 0, ⊗ (0 ( )),  = 1, , 

˜ () времени ожидания полуСледствие 1. Безусловные ПЛС ()
˜
и ПЛ 
чаются по формуле полной вероятности
1
˜ () = 1 ()

˜
= (1 −    +   w̃()),

(9)

где слагаемое
[︃
1 −   = 1 −

∑︁
∑︁
 −2
]︃
^
^  ^−1 + (
^  −1 + 
^  ( − )

−1
)^ 
=2 =−1 −1
является вероятностью прямого доступа поступившей заявки к приборам, когда
время ожидания равно 0; слагаемое
  w̃() =
∑︁
 −2

∑︁
^  ^−1 w̃+1 () + 
^  −1 ^ w̃ ()+

=2 =−1 −1
+
∞
∑︁
^  ^ w̃+1 () =

=

∑︁
∑︁
 −2
^  ^−1 w̃+1 ()+

=2 =−1 −1
^ ^ Λ̃−1 ()Γ̃ ())−1 ^ Λ̃−1 ()Γ̃ ())w̃ (),
^  −1 ^ − 
^  ( 2 + 
+ (



,
,
(10)
− +1
^ − 
^ = 
^  ,  >  , w̃+1 () = (−1)− +1 (Λ̃−1
где 
w̃ (),  >
, ()Γ̃ ())
^
 и  = diag (, 0, . . . , 0 ), представляет собой ПЛС времени ожидания для плот⏟ ⏞
( −1)2
∫︁∞
ности распределения  () при условии  > 0, причём
 ()d =   .
0
˜ () и ()
Замечание 1. Использование формулы (10) для вычисления 
˜
представляется довольно проблематичным в силу размерностей, входящих в соотношение матриц. Для численных расчётов используются соотношения (7) и
Ефросинин Д. В. Распределения времени ожидания в системе с FCFS . . .
63
преобразованная формула (9)

(︁
[︁ ∑︁
˜ () = 1 1 − 1



1
+

[︁
∑︁
 −2
]︁
  0,−1 + (  −1 +   (2 − )−1 )0, +
=2 =−1 −1

∑︁
∑︁
 −2
  0,−1 w̃+1,+1 () +   −1 0, w̃ , +
=2 =−1 −1
+  
∞
∑︁
]︁
− 0, w̃+1,+1 () . (11)
=
Бесконечная сумма в последнем слагаемом аппроксимируется конечной суммой

∑︁
− 0, w̃+1,+1 ()
(12)
=
c соответственно подобранным граничным параметром  . Выбор подходящего
значения для  >  зависит от загрузки системы и является отдельной задачей.
Например, последовательно увеличивая значение  , можно вычислять разницу
между точным значением среднего времени ожидания и производной формулы
(11) с конечной суммой (12) в точке  = 0 пока не будет достигнута заданная
точность.
Зная (),
˜
можно получить значение плотности распределения  () в точке
 = 0. Так как lim 
˜ () = 
∑︁
→∞
=1
1{ (),()=1} , то получим, что lim  () =
→0
lim→∞   w̃() = 0. Далее получим выражения для произвольных моментов
¯  () = E[ ] условный момент -го повремени ожидания. Обозначим через 
рядка и через W̄() − макровектор моментов W̄() = (W̄1 (), W̄2 (), . . .) , с
подвекторами W̄ (),  > 0, в которых компоненты упорядочены также, как и у
векторов w̃ ().
Теорема 3. Векторы условных моментов W̄ (),  > 0 времени ожидания
удовлетворяют следующему рекуррентному матричному соотношению
Φ1 W1 () = −^ 2 W1 ( − 1) − ¯ ()( 2 ),
Φ W () = −^ 2 W ( − 1) − Γ W−1 ()−
 (︂ )︂
∑︁
 ¯
−
 ( − )W̄−1 (),

=0
(13)
 > 1,
W0 () = 0( 2 ),
где Φ = Φ и Γ = Γ
( −1 ( ))
 > 1, W (0) = ( 2 ),  > 1,
для  >  , ¯ () = ((−1) ()!(1,2−1 + 0, )− ) ⊗
Доказательство. Последовательным дифференцированием рекуррентных соотношений (6) получим
d
d−1
d
w̃1 () − ^ 2 −1 w̃1 () +  Γ̃,1 ()( 2 ) = 0,

d
d
d
−1

d
d
d
Λ̃, ()  w̃ () − ^ 2 −1 w̃ () +  (Γ̃, ()w̃−1 ()) = 0,  > 2,
d
d
d
Λ̃,1 ()
64
Вестник РУДН. Серия Математика. Информатика. Физика. № 1. 2011. С. 54–74
где
d
d

Γ̃,1 () =  (−−1
1,2−1 ()2, ) ⊗ ( −1 ( )),

d
d
d
(Γ̃ ()w̃−1 ()) =
d ,
(︂ )︂ −
−1
∑︁ 
d
d
(−−1
()2, ) ⊗ ( −1 ( ))  w̃−1 ().
=
1,2−1
−
d
 d
=0
Так как для ПЛС имеем
⃒
⃒
d
w̃ ()⃒ ,
W () = (−1)
d  ⃒=0

d
¯ () = (−1)  ˜ (),
d
то с учётом равенства Λ̃, (0) = Φ получим искомое выражение (13). Для вы¯  () продифференцируем выражение
числения векторов 
Следствие 2. Безусловные моменты времени ожидания определяются как
E[  ] =   W(),  > 0.
(14)
Следствие 3. Вектор первых условных моментов времени ожидания W̄ (1),
 > 1 удовлетворяет соотношению
W̄ (1) = (−1)
−1
∏︁
−1 ^

¯
(Φ−1
−+1 Γ̃,−+1 (0))Φ1 ( 2 +  (1))( 2 )+
=1
+
−1
∑︁
(−1) Φ−1

=1
−1
∏︁

¯
^
(Γ̃,−+1 (0)Φ−1
− )( 2 +  (1))( 2 ),
=1
где Γ̃, (0) = Γ + ((2 )) ⊗ ( −1 ( ))), ¯ (1) = (−(1,2−1 + 0, )−1 ) ⊗
( −1 ( )).
¯ := E[ ]
Следствие 4. Первый безусловный момент времени ожидания 
вычисляется по формуле
¯ =   W̄(1) =


∑︁
∑︁
 −2
^  ^−1 W̄+1 (1) + 
^  −1 ^ W̄ (1)+

=2 =−1 −1
+
∞
∑︁
^  ^ W̄+1 (1) =


∑︁
∑︁
 −2
^  ^−1 W̄+1 (1)+

=2 =−1 −1
=
−1 −1
^ ^ Φ−1
^  −1 ^ − 
^  ( + 
+ (
Φ Γ, )W̄ (1)+
 Γ̃, (0))
−1
−1
−1
−1
^ ^ ) ( + 
^ ^ Φ Γ̃, (0)) Φ (^ 2 + ¯ (1))( 2 ),
^  ( − 
+





где для  > 
− +1
W̄+1 (1) = (−Φ−1
W̄ (1)+
 Γ̃, (0))
+
−
∑︁
=0
 −1 ^

¯
(−1)+1 (Φ−1
 Γ̃, (0)) Φ ( 2 +  (1))( 2 ).
Ефросинин Д. В. Распределения времени ожидания в системе с FCFS . . .
4.
65
Распределение времени пребывания
Время пребывания заявки в системе представляется в виде суммы времени
ожидания и времени обслуживания на приборе. Время обслуживания маркированной заявки на приборе зависит от состояния орбиты на момент повторного
поступления, так как согласно пороговой политике от этого зависит индекс прибора, на который заявка может поступить с орбиты. Таким образом, для вычисления распределения времени пребывания используется тот же самый подход, что
и для времени ожидания с той лишь разницей, что процесс пребывания маркированной заявки в системе переходит в поглощающее состояние в момент, когда
она покидает систему.
Введём следующие обозначения: t̃() = (t̃1 (), t̃2 (), . . .) — макровектор с подвекторами t̃ (),  > 1, содержащими условные ПЛС времени пребывания ˜ (),
упорядоченными также, как и элементы 
˜ (), T() = (T1 (), T2 (), . . .) —
макровектор с подвекторами T (),  > 1 моментов -го порядка с элемента˜  () — вектор ПЛС
ми   () = E[ ], ˜() и ˜() — безусловные ПЛС и ПЛ, 
времени пребывания в системе заявки, стоящей во главе орбиты, при условии,
что при повторном поступлении эта заявка направляется на свободный прибор с
наибольшей интенсивностью обслуживания.
˜  () удовлетворяет следующему соотношению
Лемма 3. Вектор ПЛС 
˜  () = −−1

1,2−1 ()

∑︁
=1

( − 2,−1 )(2 ),
 +  2,
2,0 = 0.
(15)
Доказательство. Для некоторого состояния  = (1 , . . . ,  ) ∈  справедливо соотношение
(︁
 + ( + )1∑︁
+
=1
 6−1

∑︁
)︁
  ˜, () =  ˜,+ ()1{︃
=1
+

∑︁
=1
}︃ +
= min {: =0}
=1,
  ˜,− () + 

1{︃
 + 
=
}︃ .
min {: =0}
=1,
Выражая последние равенства для всех возможных состояний  в матричном
виде, получим соотношение (2).
Лемма 4. Вектор ПЛС t̃, (),  >  + −1,  > 1, вычисляется по формуле
−1
˜  (),
t̃, () = (−1,2−1
()2, )−1 
 > 1.
Теорема 4. Векторы ПЛС t̃ (),  > 1 условного времени пребывания удовлетворяют следующему матричному соотношению
t̃ () = (−1)
−1
∏︁
=1
−1

(Λ−1
,−+1 ()Γ̃,−+1 ())Λ,1 ()Γ̃,1 ()( 2 ),  > 1,
(16)
66
Вестник РУДН. Серия Математика. Информатика. Физика. № 1. 2011. С. 54–74
где
Γ̃,1 () =

∑︁
=1

 + ˜,1 (),
 +  
˜,1 () = ˜,1 () = (−−1
1,2−1 ()

∑︁
=1
Γ̃, () = Γ + ˜,2 (),
 > 2,

( − 2,−1 )) ⊗ ( −1 ( )),
 +  2,

˜,2 () = (−−1
1,2−1 ()2, ) ⊗ ( −1 ( )),

∑︁
 = diag (0, . . . , 0, 2, − 2,−1 , . . . , 2, − 2,−1 , 0),
⏟ ⏞
⏟
⏞
 −1
 = Γ1 .
=1
 −
^ удовлетворяет следуДоказательство. ПЛС ˜ (),  = (, 1 , . . . ,  , ) ∈ 
ющим соотношениям
(︁
++

∑︁
1{ ()} +
=1
=

∑︁

∑︁
)︁
  ˜ () =
=1

˜+ ()1{ −1 ()} + ˜+0 ()1{
=1
+

+
−1 ()}

∑︁
  ˜− ()+
=1
 (︁
)︁
∑︁

1{=1} + ˜−0 −+1 + ()1{>1} 1{ ()} .
 + 
=1
Из предыдущих результатов следует, что
˜
t̃, () = −−1
1,2−1 ()2, t̃−1,−1 (),  > + −1,  > 2, t̃,1 () =   (),  >  .
Группируя интенсивности переходов в блочные матрицы и используя обозначение t̃ () для векторов условных ПЛС, получим следующие рекуррентные матричные соотношения
Λ̃, ()t̃ () = −Γ̃, ()t̃−1 (),
 > 1,
t̃0 () = ( 2 ),
где Λ̃, () = Λ̃, () и Γ̃, () = Γ̃, () для  >  . Дальнейшая рекуррентная подстановка приводит к выражению (16).
Следствие 5. Безусловные ПЛС ˜() и ПЛ ˜() времени ожидания получаются по формуле полной вероятности

(︁ 1 ∑︁
1
1
˜() = ˜() =




=1
 ^
  +   t̃() ,
 +  
)︁
^  = diag (0, . . . , 0, 2, − 2,−1 , 2, − 2,−1 , . . .),
где 
⏟ ⏞
 −1
первое слагаемое


 ∑︁
−1
 −2
∑︁
1 ∑︁  ^
1 ∑︁ 
  =

( − 2,−1 )+

 + 

 +  2,
=1
=2 =−1
=1
(17)
Ефросинин Д. В. Распределения времени ожидания в системе с FCFS . . .
+ ( −1 +   ( − )−1 )
1


∑︁
=1
67

( − 2,−1 )
 +  2,
обозначает ПЛС времени обслуживания при поступлении заявки на прибор, минуя орбиту; второе слагаемое
  t̃() =
∑︁
 −2

∑︁
^  ^−1 t̃+1 ()+

=2 =−1 −1
^ ^ Λ̃−1 ()Γ̃, ())−1 ^ Λ̃−1 ()Γ̃, ())t̃ ().
^  −1 ^ − 
^  ( 2 + 
+ (



,
,
обозначает ПЛС времени пребывания заявки в системе, при условии, если заявка
перед началом обслуживания находится на орбите.
Теорема 5. Векторы условных моментов T̄ (),  > 1 времени ожидания
удовлетворяют следующему рекуррентному матричному соотношению
Φ1 T̄1 () = −^ 2 T̄1 ( − 1) −

(︁ ∑︁
!
)︁
¯

+

()
( 2 ),

,1

=1
Φ T̄ () = −^ 2 T̄ ( − 1) − Γ T̄−1 () −

(18)

∑︁
(︂ )︂
 ¯
,2 ( − )T̄−1 (),  > 2,

=0
T̄ (0) = ( 2 ),
 > 1,
¯
где Φ = Φ и Γ = Γ для  >  , ¯,1 () = (−−1
1,2−1 (0)  ( − 1) −
−1
1,2−1 (0)
∑︁
=1
!
(2, −2,−1 ))⊗( −1 ( )), ¯,2 () = ((−1) ()!(1,2−1 +


0, )− ) ⊗ ( −1 ( )).
Следствие 6. Безусловные моменты времени ожидания определяются как
E[  ] = 

1 ∑︁ ! ^
  +   T̄(),  > 1,



(19)
=1
где

 ∑︁
−1
 −2
∑︁
1 ∑︁ ! ^
1 ∑︁ !

  =

(2, − 2,−1 )+






=1
=2 =−1
=1
+ ( −1 +   ( − )−1 )

1 ∑︁ !
(2, − 2,−1 ).



=1
Следствие 7. Вектор первых условных моментов времени ожидания T̄ (1),
 > 1 удовлетворяет соотношению
T̄ (1) = (−1)

−1
∏︁
−1 ^
(Φ−1
−+1 Γ̃,−+1 (0))Φ1 ( 2
=1
+

∑︁
1
+
 + ¯,1 (1))( 2 )+
 
=1
−1
∑︁
=1
(−1) Φ−1

−1
∏︁

^
¯
(Γ̃,−+1 (0)Φ−1
− )( 2 + ,2 (1))( 2 ),
=1
68
Вестник РУДН. Серия Математика. Информатика. Физика. № 1. 2011. С. 54–74

1
−1
¯
где ¯,1 (1) = (−−1
(2, −2,−1 ))⊗( −1 ( )),
1,2−1 (0)  (0)−1,2−1 (0)
=1 
¯,2 (1) = (−(1,2−1 + 0, )−1 ) ⊗ (
( )), Γ, (0) = Γ, (0).
∑︁
 −1
Следствие 8. Первый безусловный момент времени пребывания ¯ := E[ ]
вычисляется по формуле

−1
 ∑︁
 −2
∑︁
∑︁
1 ^
1 ∑︁ 1
  +   T̄(1) =
( − 2,−1 )(2 )+




 2,
1
¯ = 
=1
=2 =−1
+( −1 +  ( −)−1 )
1


∑︁
=1
=1

∑︁
1
(2, −2,−1 )(2 )+

∑︁
 −2
^  ^−1 T̄+1 (1)+

=2 =−1 −1
^ ^ Φ−1 Γ̃ (0))−1 Φ−1
^  −1 ^ − 
^  ( + 
+ (
 Γ̃ (0))T̄ (1)+


−1 −1 ^
^ ^ )−1 ( + 
^ ^ Φ−1
^  ( − 
+
Φ ( 2 + ¯,2 (1))( 2 ),
 Γ̃ (0))





где для  > 
− +1
T̄+1 (1) = (−Φ−1
T̄ (1)+
 Γ̃, (0))
+
−
∑︁

 −1 ^
¯
(−1)+1 (Φ−1
 Γ̃, (0)) Φ ( 2 + ,2 (1))( 2 ).
=0
5.
Распределение числа повторных попыток
В данном разделе представлена схема вычисления распределения числа повторных попыток Ψ, предпринимаемых заявкой, стоящей во главе орбиты, до
момента её успешного поступления на прибор. По сути, число повторных попыток является дискретным аналогом времени ожидания и существенно дополняет
его анализ.
Введём следующие обозначения: Ψ — число повторных попыток занять прибор, при условии начального состояния ,  () = P[Ψ = ] — вероятность того,
что до момента успешного поступления на прибор
∑︁∞маркированная заявка соверΨ
˜
шит  попыток поступления,  () = E[ ] =
 ()  , || 6 1, — произво=0 
˜
˜ (), 
˜ (), . . . , 
˜ ()) — вектор-столбец ПФ с
дящая функция (ПФ), ()
= (
1
2

˜
подвекторами  (), состоящими из компонентов ˜ (), упорядоченных в соответ
ствие с , Ψ̄() = (Ψ̄1 (), Ψ̄2 (), . . . , Ψ̄ ()) — вектор-столбец факториальных
моментов порядка , где подвекторы Ψ̄ () состоят из аналогично упорядоченных
компонентов Ψ̄ () = E[Ψ (Ψ − 1) . . . (Ψ −  + 1)],  > 1.
Рассмотрим снова маркированную заявку во главе орбиты. Вычислим для
этой заявки ПФ ˜Ψ, () числа повторных попыток, при условии начального со˜ Ψ () = (˜Ψ, ();  ∈ ) вектор-столбец ПФ,
стояния  ∈ . Обозначим через 
упорядоченных в лексикографическом порядке. Выписывая рекуррентные соотношения для ˜Ψ, () и выражая их в матричном виде, получим следующее матричное выражение.
˜ Ψ () удовлетворяет следующему соотношению
Лемма 5. Вектор ПФ 
˜ Ψ () = −1,2−1 ()−1 2, ()(2 ),

(︁
)︁

0, , 2, () = 2, .
где 1,2−1 () = 1,2−1 + 2 − (1 − )

(20)
Ефросинин Д. В. Распределения времени ожидания в системе с FCFS . . .
69
Доказательство. Для некоторого состояния  = (1 , . . . ,  ) ∈ , используя
свойства марковости процесса, получим
(︁
 + 1{︂∑︁
=1
+

∑︁

∑︁
}︂ +  +
 6−1
)︁
  ˜Ψ, () =  ˜Ψ,+ ()1{︃
}︃ +
= min {: =0}
=1
=1,
(︁
  ˜Ψ,− () +  1{︂∑︁
=1
}︂
=1
 6−1
+ ˜Ψ, ()1{︂∑︁
=1
}︂
)︁
.
 =
Выражая, как и прежде, последние равенства для все возможных состояний  в
матричном виде, получим равенство (20).
˜
Лемма 6. Вектор ПФ  (),  >  +  − 1,  > 1, вычисляется по формуле
,
˜ () = (−1,2−1 ()−1 2, ()) (2 ),

,
 > 1.
(21)
Доказательство. См. доказательство леммы 2.
˜
Теорема 6. Векторы ПФ   (),  > 1 числа повторных попыток занять
прибор удовлетворяют следующему матричному соотношению
˜ () = (−1)



∏︁
(Λ̃Ψ,−+1 ()−1 Γ̃Ψ,−+1 ())( 2 ),
 > 1,
(22)
=1
где
Λ̃Ψ, () = Φ + (1 − ) 1{=1} ,
Γ̃Ψ,1 () = Γ1 + ˜Ψ (), Γ̃Ψ, () = Γ + ˜Ψ (),  > 2,
˜Ψ () = (−1,2−1 ()−1 2, ()) ⊗ ( −1 ( )),


 = − diag (0,1 , . . . , 0,1 , . . . , 0,−1 , . . . , 0,−1 , 0).

⏞
⏟
⏞
⏟
 −−1
2 −1
^
Доказательство. Анализируя переходы цепи Маркова {()}
>0 , получим
˜
^
следующую систему уравнений для для ПФ  (),  = (, 1 , . . . ,  , ) ∈ 
(︁
+

∑︁
1{ ()} 1{>1} + 1{=1} +
=1

∑︁
)︁
  ˜ () =
=1
=

∑︁
(︁
˜+ ()1{ −1 ()} + ˜+0 ()1{
=1
+

∑︁
  ˜− () + 
 −1
()}
+
˜−0 −+1 + ()1{ ()} 1{>1} +
=1
=1
+ 

∑︁
)︁

(︁ ∑︁
˜−0 −+1 + ()1{ ()} + ˜ ()1{
=1
)︁

()}
1{=1} ,
^
 ∈ .
Как и прежде, имеют место соотношения
˜ () = −1,2−1 ()−1 2, ()
˜

 >  +  − 1,
,
−1,−1 (),
˜
˜
 () =  Ψ (),  >  .
,1
 > 2,
(23)
70
Вестник РУДН. Серия Математика. Информатика. Физика. № 1. 2011. С. 54–74
Группируя интенсивности переходов в блочные матрицы и используя обозна˜ () для векторов условных ПФ, получим следующее рекуррентное матчение 

ричное соотношение
˜ () = −Γ̃Ψ, ()
˜
Λ̃Ψ, ()

−1 (),
 > 1,
˜ () = ( 2 ).

0
(24)
Здесь Λ̃Ψ, () = Λ̃Ψ, () и Γ̃Ψ, () = Γ̃Ψ, () для  >  . Дальнейшая рекуррентная подстановка приводит к выражению (22).
˜ (), 1 6  6  6  +  − 2 могут быть вычисТеорема 7. Векторы ПФ 
,
лены, используя следующие рекуррентные соотношения
˜ () = 
˜
˜ +1 −−1 ()

,
+1 −1, ()+
Ψ,2−1
+1 −−2
+
∑︁

˜
˜ Ψ,2−1
˜ Ψ,2−1 ()

()
−1+,−1 (),  =  , +1 − 2,  = 1,  − 1, (25)
=0
˜
˜
˜
˜

+1 −1, () = Ψ,2 () +1 , + Ψ,2 () +1 −2,−1 (),
˜ () = 
˜
˜  +−−1 ()

,
 +−1, +
Ψ,2−1
+
 +−−2
∑︁

˜
˜ Ψ,2−1
˜ Ψ,2−1 ()

()
−1+,−1 (),
 =  ,  +  − 2,
=0
−1
˜
˜

2, ()
 +−1, () = −1,2−1 ()
 +−2,−1 (),
˜ () = (2 ),

,0
˜ Ψ,. () и 
˜ Ψ,. () определяются следующим образом
где матрицы 
(︁
)︁−1
˜ Ψ,2−1 () = − 1,2−1 − 1{=1} (1 − ) 0,

0, ,

(︁
)︁
−1
˜ Ψ,2−1 () = − 1,2−1 − 1{=1} (1 − ) 0,

2, ,

)︁−1
(︁
˜ Ψ,2 () = − 1,2 − 1{=1} (1 − ) 0,

0,+1 ,

(︁
)︁
−1
˜ Ψ,2 () = − 1,2 − 1{=1} (1 − ) 0,

2, .

˜
Следствие 9. Безусловная ПФ ()
числа повторных попыток получается
по формуле полной вероятности
˜
˜
()
= 1 −    +   ().
(26)
Теорема 8. Векторы условных факториальных моментов Ψ̄ (),  > 0 числа повторных попыток удовлетворяют следующему рекуррентному матричному соотношению
Φ1 Ψ̄1 () = −(Γ1 1{=1} + ¯Ψ ())( 2 ) +  Ψ̄1 ( − 1),
 (︂ )︂
∑︁
 ¯
Φ Ψ̄ () = −Γ Ψ̄−1 () −
Ψ ( − )Ψ̄−1 (),  > 2,

=0
Ψ̄ (0) = ( 2 ),
 > 1,
(27)
Ефросинин Д. В. Распределения времени ожидания в системе с FCFS . . .
71
(︁  )︁−1
((1,2−1 +
для  >  , ¯Ψ () = ((−1) ()!
где Φ = Φ и Γ = Γ

0, )−1 0, )−1 (1,2−1 + 0, )−1 ) ⊗ ( −1 ( )).
Следствие 10. Из соотношений (13) и (27), принимая во внимание, что
(Γ1 −  )( 2 ) =  ^ 2 ( 2 ) и ¯Ψ (1) =  ¯ (1),
получим очевидное равенство W̄1 (1) =
6.
1
Ψ̄ (1).
 1
Численные эксперименты
В данном разделе вычисляются характеристики системы //3 для оптимальной пороговой политики управления (Optimal Threshold Policy, OTP), задаваемой уровнями (2* , 3* ). Для проведения сравнительного анализа данная система
исследуется также для некоторых других управляемых систем с приближенными
и эвристическими политиками управления, определёнными в работе [1]:
– приближенная пороговая политика (Approximated Threshold Policy, ATP), задаваемая порогами ( = 1, )
∑︁−1
*
⌊︂
(︂

≈
+
∑︁−1
=1
=1
√︂
∑︁−1
 −  + ( =1  − )2 + 4( − 1) 
2

)︂⌋︂
− ( − 1)
,
– политика расписания (Scheduling Threshold Policy, STP) с порогами
*
⌊︂

= ∑︁−1
=1
 + 
(︂ ∑︁−1 
=1

)︂⌋︂

− ( − 1)
,
 = 1, ,
– политика включения самого быстрого свободного прибора (Fastest Free Server,
FFS), политика случайного выбора прибора (Random Server Selection, RSS),
а также система с однородными приборами (Homogeneous Servers).
С помощью программного пакета Mathematica созданы процедуры
˜ () и ˜(), формулы (9) и (17);
– для получения ПЛ 
˜
– для получения ПФ (), формула (26).
˜ () и ˜() используются два типа алгоритмов: стандартДля обращения ПЛ 
ный алгоритм и алгоритм на основе рядов Фурье. Математические пакеты, такие как Mathematica, Mathlab, Mathcad и др., используют стандартный алгоритм,
основанный на представлении функции преобразования в виде суммы элементарных функций меньшего порядка. Преимущество данного алгоритма состоит в
возможности получения явного вида соответствующей функции распределения.
Но такой алгоритм является эффективным лишь для функций с небольшими
степенями. В этом случае граничный параметр  , приведённой в формуле замечания 1, не может быть большим. В свою очередь это приводит к тому, что точное
представление функций распределений  () и  () возможно лишь для малых
значений . Алгоритмы, основанные на рядах Фурье, дают возможность довольно точного численного обращения ПЛ в случае сложных функций. К таким алгоритмам относятся алгоритмы Эйлера и Пост–Виддера [8], которые могут быть
использованы и для больших значений . Упомянутые выше пакеты позволяют
также обращать ПФ для вычисления функции распределения Ψ(). Однако, как и
прежде, возникают проблемы с функциями, имеющими большие степени. В этом
случае для численного обращения используется алгоритм Латтиса–Пуассона [9].
72
Вестник РУДН. Серия Математика. Информатика. Физика. № 1. 2011. С. 54–74
На рис. 2–5 представлены функции распределения времени ожидания заявки
на орбите (см. рис., обозначенные «а») и времени пребывания в системе (см. рис.,
обозначенные «б»). Скачок функции распределения времени ожидания в точке
 = 0 равняется вероятности P[ = 0] и увеличивается при убывании  и .
(а)  ()
(б)  ()
Рис. 2. Функция распределения для  = 0, 5, 1 = 2, 2, 2 = 0, 5, 3 = 0, 2,  = 2, 5
(а)  ()
(б)  ()
Рис. 3. Функция распределения для  = 1, 2, 1 = 2, 2, 2 = 0, 5, 3 = 0, 2,  = 2, 5
(а)  ()
(б)  ()
Рис. 4. Функция распределения для  = 0, 5, 1 = 2, 2, 2 = 0, 5, 3 = 0, 2,  = 18, 5
Ефросинин Д. В. Распределения времени ожидания в системе с FCFS . . .
(а)  ()
73
(б)  ()
Рис. 5. Функция распределения для  = 1, 2, 1 = 2, 2, 2 = 0, 5, 3 = 0, 2,  = 18, 5
Из рис. 2–5 видно, что распределения, соответствующие более высоким значениям , обладают более тяжёлыми хвостами.
Распределения числа повторных заявок для различных значений  и  изображены на рис. 6 и 7. Из рисунков видно, что графики функций повторяют силуэты
функций распределения времени ожидания, так как являются их дискретными
аналогами.
(а)  = 0, 5
(б)  = 1, 2
Рис. 6. Функция распределения Ψ(), 1 = 2, 2, 2 = 0, 5, 3 = 0, 2,  = 2, 5
(а)  = 0, 5
(б)  = 1, 2
Рис. 7. Функция распределения Ψ(), 1 = 2, 2, 2 = 0, 5, 3 = 0, 2,  = 18, 5
74
Вестник РУДН. Серия Математика. Информатика. Физика. № 1. 2011. С. 54–74
Литература
1. Ефросинин Д. В. Стационарные характеристики многоканальной неоднородной системы с FCFS орбитой и пороговым управлением // Вестник РУДН.
Серия «Математика. Информатика. Физика». — 2010. — № 3 (1). — С. 34–
46. [Efrosinin D. V. Stacionarnihe kharakteristiki mnogokanaljnoyj neodnorodnoyj
sistemih s FCFS orbitoyj i porogovihm upravleniem // Vestnik RUDN. Seriya
«Matematika. Informatika. Fizika». — 2010. — No 3 (1). — S. 34–46.]
2. Kleinrock L. Queueing Systems. — New York, 1975.
3. Artalejo J. R., Chakravarthy S. R., Lopez-Herrero M. J. The Busy Period and the
Waiting Time Analysis of MAP/M/c Queue with Finite Retrial Group // Stochastic
Analysis and Applications. — 2007. — Vol. 25. — Pp. 445–469.
4. Falin G. I., Tempelton J. G. C. Retrial Queues. — Chapman and Hall, 1997.
5. Gomez-Corral A., Ramalhoto M. F. On the Waiting Time Distribution and the
Busy Period of a Retrial Queue with Constant Retrial Rate // Stochastic Modeling
and Applications. — 2000. — Vol. 3(2). — Pp. 37–47.
6. Ефросинин Д. В., Рыков В. В. К анализу характеристик производительности СМО с неоднородными приборами // Автоматика и телемеханика. — 2008. — Т. 1. — С. 64–82. [Efrosinin D. V., Rihkov V. V. K analizu
kharakteristik proizvoditeljnosti SMO s neodnorodnihmi priborami // Avtomatika
i telemekhanika. — 2008. — T. 1. — S. 64–82.]
7. Neuts M. F. Matrix-Geometric Solutions in Stochastic Models. — The John Hopkins
University Press, 1981.
8. Abate J., Whitt W. Numerical Inversion of Laplace Transforms of Probability Distributions // ORSA Journal on Computing. — 1995. — Vol. 7. — Pp. 36–43.
9. Abate J., Whitt W. Numerical Inversion of Probability Generating Functions //
Operation Research Letters. — 1992. — Vol. 12. — Pp. 245–251.
UDC 519.21
Waiting Time Distribution of the Queue with FCFS Orbit and
Threshold Policy
D. V. Efrosinin
Department of Probability Theory and Mathematical Statistics
Peoples’ Friendship University of Russia
Miklukho-Maklaya str., 6, Moscow, 117198, Russia
We perform a waiting time analysis of a retrial queue with several heterogeneous servers
and threshold control policy. The blocked customers are dispatched to the infinitely large orbit
with FCFS service discipline. The system is analyzed in steady-state by deriving expressions
for the Laplace transforms of the waiting time, the probability generating functions for the
number of retrials made by a customer and for various moments of corresponding quantities.
Some illustrative numerical examples and their discussion are presented.
Key words and phrases: heterogeneous servers, threshold control policy, waiting time
distribution, FCFS orbit.
Документ
Категория
Без категории
Просмотров
5
Размер файла
1 226 Кб
Теги
времени, ожидание, орбитой, система, пороговых, управления, распределение, fcfs
1/--страниц
Пожаловаться на содержимое документа