Модели систем с непуассоновскими потоками заявок

В предыдущем разделе были рассмотрены СМО с пуассоновскими потоками обслуживании и заявок, когда время обслуживания и интер­вал между поступлениями двух следующих друг за другом заявок распределены по показательному закону. Это, однако, не всегда соблюдается на практике. Рассмотрим несколько частных случаев, где получены аналитические результаты в явном виде, и укажем один общий подход, существенно расширяющий класс исследуемых СМО [6]-[8].

СМО с отказами. Б.А.Севастьяновым рассмотрена система Эрланга с пуассоновским потоком заявок интенсивностью lи с потоком обслуживания, в котором закон распределения времени обслуживания одной заявки является произвольным. Обозначим этот закон через f(t_Об). Тогда среднее время обслуживания определится как

       

Б.А.Севастьяновым доказано, что формулы Эрланга (2.8) справедливы и в этом случае. Следовательно, на данный случай распространяются все выражения для характеристик СМО Эрланга, полученные ранее.

СМО с очередью. Аналогичный случай (с пуассоновским потоком заявок и произвольным законом распределения времени обслуживания) был рассмотрен применительно к одноканальной СМО с неограниченной очередью (n=1, m=¥). Определим дисперсию времени обслужива­ния:

              

Назовем отношение s_t/t_Об = d коэффициентом вариации времени обслуживания. Очевидно, что для пуассоновского потока d = 1. Полячеком, Хинчиным и Кендаллом независимо друг от друга показано, что среднее число заявок в очереди и среднее время ожидания в очереди равны соответственно

                  (3.1)

 

Формулы (3.1) называются формулами Полячека-Хинчина. Для d = 1 (пуассоновский поток) формулы (3.1) превращаются в полученные ра­нее выражения для простейшей одноканальной СМО с очередью (2.27) и (2.29). Для d = 0 (время обслуживания не случайно и равно своему математическому ожиданию) из (3.1) и (2.27), (2.29) сле­дует, что при строго постоянном времени обслуживания и средняя длина очереди, и среднее время ожидания вдвое меньше, чем при случайном (показательном) времени обслуживания. Приведенные фор­мулы являются наиболее известными в теории непуассоновских СМО. Большое количество других результатов, относящихся к таким СМО, приведено в [7], [8].

Многие реальные потоки можно аппроксимировать потоками Эр­ланга. В потоках Эрланга k-го порядка имеет место следующее соот­ношение между математическим ожиданием и дисперсией:

                   (m_t^(k))²/D_t^(k) = k ³ 1                    (3.2)

Следовательно, аппроксимация реального потока потоком Эрлан­га возможна, если для первых двух моментов распределения интерва­лов времени между двумя соседними событиями в реальном потоке справедливо соотношение (3.2). В случаях, когда это соотношение не выполняется, возможна аппроксимация реального потока обобщен­ным потоком Эрланга [7], однако этого вопроса мы здесь касаться не будем. Если для реального потока измерены величины m_t и D_t, то выбор порядка k аппроксимирующего потока Эрланга определяется со­отношением (3.2).

Пусть реальный поток аппроксимируется потоком Эрланга k-ro порядка. Это означает, что переход из одного состояния в другое под действием потока Эрланга можно представить состоящим из ста­дий или псевдосостояний. Переход из каждого такого искусственно вводимого псевдосостояния в другое происходит через промежутки времени t’, t" и т.д., которые распределены по показательному за­кону. Это значит, что процесс в системе будет марковским. Если же такие псевдосостояния не вводить, то переход из одного состояния в другое будет зависеть от времени нахождения системы в данном состоянии. Это время (последействие) тем больше, чем больше поря­док потока Эрланга. Поэтому СМО с эрланговскими потоками называ­ется системой с ограниченным последействием. Множество псевдосос­тояний, заменяющее одно из реальных состояний в системе с ограни­ченным последействием, называется транзитивным подмножеством [7]. В связи с тем, что при замене реального состояния транзитивным подмножеством в это одно состояние "вкладывается" целая марковская цепочка, такой метод исследования систем с ограниченным последействием называется методом вложенных цепей Маркова. Иногда применяют иное название - метод псевдосостояний [1].

Рассмотрим применение метода вложенных цепей Маркова к ана­лизу СМО. Пусть на вход одноканальной СМО с очередью поступает простейший поток заявок с интенсивностью l. Время обслуживания распределено по закону Эрланга 2-го порядка (k=2) с математичес­ким ожиданием 1/m. Очевидно, что время обслуживания представляет собой сумму двух независимых случайных величин, распределенных по одному и тому же экспоненциальному закону с математическим ожида­нием 1/m’. Очевидно, что l/m=2/m’, откуда m’=2m. Следовательно, переход из одного псевдосостояния в другое происходит под дейс­твием потока обслуживаний с интенсивностью 2m. Интервал обслужи­вания содержит два этапа обслуживания, например отыскание неисп­равности и ее устранение, если обслуживание сводится к ремонту ТУ. Тогда размеченный граф состояний будет иметь вид, представ­ленный на рис.3.1, где состояния системы следующие: S₀ – канал свободен, заявок нет; S_1,1 - канал занят обслуживанием заявки, очереди нет; S_1,2 - обслуживание одной заявки на втором этапе, очереди нет; S_2,1 - в СМО две заявки - первая обслуживается на первом этапе, вторая стоит в очереди, S_2,2 - в СМО две заявки, первая обслуживается на втором этапе, вторая - стоит в очере­ди; …; S_k,1 - в СМО находятся k заявок, одна - на первом этапе обслуживания, остальные - в очереди; S_k,2 - в СМО k заявок: одна – на втором этапе обслуживания, остальные - в очереди; …; S_m+1 - в СМО находятся m заявок, вновь приходящие заявки получают отказ.

 

Рис.3.1

 

Этот граф легко продлить и до бесконечности (m®¥). Вправо систему переводят потоки заявок с интенсивностью l, причем пере­ход вправо возможен как из состояний S_k,1, так и S_k,2 в зависимости от того, какой этап обслуживания застанет вновь приходящая в СМО заявка. Влево переводят систему потоки обслуживаний с ин­тенсивностью 2m.

Полученный граф существенно сложнее графа процесса размноже­ния и гибели. Записав для каждой вершины графа соотношения для вероятностей состояний в соответствия с правилом, приведенным в 1.2. получим:

rp₀ = 2p_1,2

(r+2)p_1,1 = rp₀ + 2p_2,2

(r+2)p_1,2 = 2p_1,1

(r+2)p_2,1 = rp_k-1 + 2p_3,2

…

(r+2)p_k,1 = rp_k-1,1 + 2p_k+1,2

(r+2)p_k,2 = rp_k-1,2 + 2p_k,1

rp_m,1 = 2p_m+1

 

 

Итак, система с потоками Эрланга сведена с помощью метода вложен­ных цепей Маркова к марковской цепи. Вычисляя соответствующие ве­роятности, можно определить все интересующие нас характеристики. При повышении порядка потока Эрланга увеличивается число псевдо­состояний и решение соответствующих систем уравнений становится затруднительным.

Модели многофазных систем

Многофазными называются СМО, которые состоят из нескольких последовательно соединенных отдельных подсистем массового обслу­живания, причем входящий поток каждой последующей подсистемы яв­ляется выходящим потоком предыдущей.

Многофазные СМО предназначены для выполнения некоторого пол­ного цикла обслуживания одной заявки, когда по различным причинам этот цикл целесообразней разделить на несколько фаз (например, обслуживание в магазине, где покупатели сначала стоят в очереди в кассы, а затем обслуживаются у продавцов). В качестве подсистем СМО на каждой фазе обслуживания будем рассматривать одно- и мно­гоканальные системы с очередями, в которых число мест не ограни­чено (m=¥). При этом будем считать, что выполняются условия стабилизации очереди, т.е. r < 1 и æ = l/mр < 1.

Для исследования многофазных СМО ключевым вопросом является нахождение характеристик выходящего потока каждой из подсистем. Покажем, что при сделанных выше предположениях и при пуассоновских потоках заявок и обслуживания выходящий поток СМО будет также пуассоновским.

Рассмотрим для простоты одноканальную СМО. Пусть p_n(t/i) - условная вероятность того, что в промежуток времени (t,t+t) произошло n обслуживании при ус­ловии, что за это же время в системе на­ходилось i заявок (рис.3.2). Поскольку рассматривается установившееся состояние СМО, то вероятность нахождения заявок в одноканальной СМО с бесконечной очередью i в соответствии с (2.26)

            p_i = rⁱ(1 - r)                                 (3.3)

 

 

Рис.3.2

 

Рассмотрим малый промежуток времени (t,t+Dt). Появление события в этом промежутке определяется величиной элемента вероят­ности появления события (1.27). При этом возможны три случая:

- если за время Dt приходит новая заявка с вероятностью p_i=lDt, то число заявок возрастает на единицу, а число обслужива­ний будет тем же. Тогда в оставшийся промежуток времени t-Dt число заявок возрастет на единицу, а число обслуживании не изме­нится, чему будет соответствовать условная вероятность р_n=(t-Dt/i+1);

- если за время Dt с вероятностью р₂=mDt заканчивается обслуживание одной заявки, то в промежутке t-Dt число окончаний обслуживаний будет равно n-1, при этом обслуженная заявка поки­нет систему и число заявок в системе будет равно 1. Соответствующая условная вероятность будет равна р_n-1((t-Dt)/(i-1));

- если за время Dt не поступит ни одной заявки и не закон­чится ни одно обслуживание с вероятностью

Р₃=1-(p₁+p₂)=1-(m+l)Dt,

то этому состоянию по определению будет соответствовать условная вероятность р_n(t-Dt/i). Тогда условные вероятности будут связаны соотношением

р_n(t/i)=p_n(t-Dt/i+1)l×Dt+p_n-1(t-Dt/i-1)mDt+[1-(m+l)Dt]p_n(t-Dt/i)    (3.4)

После элементарных преобразований (3.4) и перехода к пределу при Dt®0 получаем дифференциальное уравнение

dp_n(t/i)/dt=lp_n(t/i+1)+mp_n-1(t/i-1)-(l+m)p_n(t/i)                  (3.5)

В (3.5) можно перейти от условных к безусловным вероятностям, ис­пользуя формулу полной вероятности

где р_n(t) - вероятность того, что за время t в системе произойдет n окончаний обслуживаний. Очевидно, что

                                         (3.6)

Умножим обе части (3.5) на вероятность р_i, определяемую из (3.3), и произведем суммирование обеих частей (3.5) по i от 0 до ¥. Из (3.3) следует, что p_i=rр_i-1 и р_i=rp_i+1. С учетом этого обстоятельства и формулы (3.6) получим

    dp_n(t)/dt=-lp_n(t)+lp_n-1(t)                                   (3.7)

Очевидно также, что

    dp₀(t)/dt=-lр₀(t)                                       (3.8)

и (3.7) и (3.8) следует интегрировать с начальными условиями

    p₀(0)=1, p₁(0)=0, …, р_n(0)=0                           (3.9)

отражающими тот факт, что за нулевой отрезок времени не происхо­дит ни одного события. Система уравнений, состоящая из (3.7) и (3.8) с начальными условиями (3.9), полностью совпадает с систе­мой (1.18), которая определяет вероятности попаданий n событий на интервал t для пуассоновского потока. Следовательно, мы доказали, что выходящий поток СМО с неограниченной стабилизированной оче­редью при пуассоновских потоках обслуживания и заявок также явля­ется пуассоновским.

В связи с этим различные подсистемы в многофазной СМО можно рассматривать независимо друг от друга как системы, находящиеся под воздействием одного и того же потока заявок интенсивности l и потоков обслуживания в общем случае с различными интенсивностями m_i(i=1,…,k).

 Состояние СМО характеризуется вероятностью некоторого расп­ределения заявок по каждой из подсистем

                                     (3.10)

 

с условием нормировки

                                    (3.11)

Принимая во внимание формулу (2.28) для среднего числа заявок в отдельной СМО, получим выражение для математического ожидания числа заявок в многофазной СМО:

                                                 (3.12)

 

Используя формулы (2.34)-(2.36) для многоканальной СМО, можно получить выражения, аналогичные (3.10)-(3.12) для случая приме­нения таких СМО в качестве отдельных подсистем многофазной СМО.