Аналитические модели систем массового обслуживания

В.В.РОМАНЦЕВ

АНАЛИТИЧЕСКИЕ МОДЕЛИ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

Учебное пособие

Санкт-Петербург 1998

 

Романцев В.В. Аналитические модели систем массового обслуживания: Учеб.пособие/СПбГЭТУ (ЛЭТИ). СПб., 1998. 67с.

 

Рассматриваются аналитические модели систем массового обслу­живания, приводятся рекомендации по построению и анализу моделей.

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

 

Рецензенты: кафедра статистического моделирования СПбГУ; канд. техн.наук ст.науч.сотр. В.С.Мельканович (ЦНИИ "Морфизприбор").

 

Утверждено редакционно-издательским советом университета в качестве учебного пособия

СПбГЭТУ (ЛЭТИ), 1998

МАТЕМАТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ

Простейший поток событий

Цепи Маркова с непрерывным временем являются математическими моделями СМО. Для анализа СМО необходимо также иметь математичес­кие модели входных потоков заявок на обслуживание. Эти математи­ческие модели представляют собой потоки события, являющиеся от­дельным классом случайных процессов. Потоком событий называется последовательность однородных событий, следующих одно за другим в случайные моменты времени [1]. Этот поток количественно может быть охарактеризован числом событий x(t), имевших место в течение определенного промежутка времени (0,t). Тогда случайный поток со­бытий можно определить как случайный процесс x(t) (t³0), в кото­ром функция x(t) является неубывающей функцией времени, способной принимать лишь целые неотрицательные значения. Иными словами, график функции x(t) является ступенчатой кривой с постоянной вы­сотой ступеньки, равной единице, причем ширина ступеньки - слу­чайная величина (см.рис.1.5,а). Примерами таких потоков могут служить: поток вызовов на АТС, поток запросов в вычислительный центр коллективного пользования и т.п. Моменты появления событий можно отобразить точками на временной оси, поэтому поток событий часто представляется и как последовательность таких точек (см.рис.1.5,б). Поток событий называется регулярным, если события следуют одно за другим через одинаковые, строго фиксированные промежутки времени.

 

Рис.1.5

 

В ТМО такие потоки практи­чески, не используются, однако они представляют интерес как предельный случай. Значительно чаще имеют дело с потоками, в которых времена поступления со­бытий и, следовательно, проме­жутки времени между ними являются случайными (иррегулярными). При этом наиболее простые рас­четные соотношения получаются при использовании простейших потоков событий, которые широко применяются при исследовании CMC.

Простейшими называются потоки, обладающие следующими тремя свойствами: стационарностью, ординарностью и отсутствием последействия. Рассмотрим эти свойства подробнее.

1. Поток событий называется стационарным, если вероятность p_k(l) того, что за отрезок времени t произойдет k событий, зави­сит только от его длины t и не зависит от его расположения на временной оси (см.рис.1.5), т.е. p_k(t’,t’+t)=p_k(t). Из определения однородной марковской цепи следует, что стационар­ность - это однородность потока по времени.

2. Поток называется ординарным, если вероятность попадания на любой элементарный участок временной оси двух или более собы­тий является бесконечно малой величиной, т.е.

 

3. Поток событий называется потоком без последействия, если вероятность попадания событий на некоторый участок временной оси не зависит от того, сколько событий попало на другие участки. Иными словами, условная вероятность наступления k событий за про­межуток времени (t’,t’+t), вычисленная при любом условии чередо­вания событий до момента t', равна безусловной вероятности p_k(t) того же события, т.е.

p[(t’,t’+t),k/(t",t"+t),m]=p_k(t),tÇt_k=Æ, t"<t’.

На практике редко встречаются потоки, удовлетворяющие всем трем допущениям одновременно. Например, поток вызовов в АТС в дневные часы более интенсивен, чем в ночные. Тем не менее, рассматривая работу АТС в периоды с 12 до 13 ч дня и с 2 до 3 ч ночи, поток вызовов на этих более коротких промежутках можно с высокой степенью точности считать стационарным. Этот пример говорит о том, что в большом числе случаев можно ввести определенные упрощения, вытекающие из принципов работы конкретных реальных систем и позволяющие проводить исследование реальных СМО путем замены их входных потоков простейшими. Это дает возможность существенно упростить математический аппарат исследования СМО.

Указанные свойства простейших потоков позволяют просто опре­делить их распределение вероятностей p_k(t), т.е. вероятность того, что за отрезок времени длиной t произойдет k событий. Прежде всего следует оговорить, что мы будем рассматривать только те по­токи, в которых за конечный промежуток времени t с вероятностью 1 будет происходить лишь конечное число событий, т.е.

                                                   (1.17)

Тогда простейший поток можно представить цепью Маркова, изобра­женной на рис.1.6,а, где состояние S₀ означает отсутствие собы­тий в интервале t, S₁ - появление одного события за время t, S₂ - появление двух событий за время t,…, S_k - появление k событий за время t. Применив правила составления уравнений Колмогорова для такого размеченного графа состояний, получим:

dp₀(t)/dt = - lp₀(t),

dp₁(t)/dt = - lp₁(t)+lp₀(t)                                     (1.18)

…

dp_k(t)/dt = - lp_k(t)+lp_k-1

_…

с начальными условиями: р₀(0)=1, р₁(0)=0,…, р_k=0,…

Плотность вероятности перехода l, которая участвует в уравнениях (1.18), является в данном случае интенсивностью потока собы­тий. Под интенсивностью потока понимается среднее по ансамблю реализаций число событий в единицу времени. Вероятность перехода р_i,i+1(t,t+Dt) равна веро­ятности появления одного события в интервале от t до t+Dt, поскольку ординар­ность потока исключает появление большего числа событий в этом интервале. Очевидно, что эта вероятность равна среднему числу по­явлений одного события за время Dt. Тогда с учетом определения (1.2) можно сделать вывод, что плотность вероятности перехода для марковской цепи (рис.1.6) равна интенсивности простейшего потока. В стационарном простейшем потоке l = const, тогда как в не­стационарном потоке интенсивность зависит от времени: l = l(t).

 

             а                      б

                       Рис.1.6

 

Решить систему (1.18) можно различными методами. Одним из наиболее простых является метод производящих функций. Производя­щей функцией распределения вероятностей состояний p_k(t) называет­ся ряд

                    ,                 (1.19)

где |z|£l.

С учетом (1.17) ряд (1.19) сходится абсолютно. Умножая на z^k все уравнения (1.18) и суммируя по k от 0 до ¥, получим:

         

откуда следует

        dln Ф/dt = l(z-1)                                (1.20)

Интегрируя (1.20), получим

        ln Ф(t,z) – ln Ф(0,z) = l(z-1)t

С учетом начальных условий системы (1.18) можно написать

        Ф(0,z) = p₀(0) = 1, ln Ф(0,z) = 0.

Следовательно,

Подставив вместо Ф(t,z) выражение (1.19), получим окончательно

                                           (1.21)

 

Распределение (1.21) является известным распределением Пуассона, поэтому простейшие потоки называются пуассоновскими.

Важнейшей характеристикой любого потока является закон рас­пределения интервала времени Т между двумя соседними событиями в потоке (см.рис.1.6,б). Определим этот закон для пуассоновских потоков. Вначале рассмотрим интегральный закон распределения F(t)=p(t>T), т.е. вероятность того, что случайная величина Т при­мет значение, меньшее чем t. Для этого необходимо определить ве­роятность того, что в интервал времени t, отсчитываемый от момента t₀ появления некоторого события, попадет еще хотя бы одно событие (см.рис.1.6,б). Эту вероятность можно определить, зная вероятность отсутствия событий в интервале t, равную вероятности p₀(t) состояния S₀ на графе рис.1.6, а. В соответствии с (1.21)

                     p₀(t)=e^-lt

откуда следует

                F(t)=p(t>T)=1-e^-lt, t>0     .         (1.22)

Дифференцируя (1.22) по времени, получим искомый закон распреде­ления

                                          (1.23)

Закон распределения (1.4.9) называется показательным (экспоненци­альным). Определим первые два момента показательного распределе­ния:

- математическое ожидание

                                       (1.24)

- дисперсия

                                           (1.25)

Интегрируя (1.24) и (1.25) по частям, получим

 

              .    (1.26)

 

Из (1.26) следует, что для показательного распределения математи­ческое ожидание и среднеквадратичное отклонение равны друг другу. Кроме того из (1.26) следует, что в простейшем потоке среднее время между двумя соседними событиями равно обратной величине ин­тенсивности потока.

Определим теперь вероятность попадания одного события в простейшем потоке на элементарный участок временной оси (см.рис.1.6,б). Так же, как и в предыдущем случае, эта вероятность

P₁(Dt) = 1 – P₀(t) = 1 - e^-lDt. 

Разлагая e^-lDt в ряд по степеням lDt и ограничиваясь только первой степенью (в силу малости Dt), получим

             P₁(Dt) = lDt.                             (1.27)

Выражение в правой части (1.27) называется элементом вероятности появления события в простейшем потоке.

 

Потоки Пальма и Эрланга

Потоки Пальма или потоки с ограниченным последействием явля­ются обобщением потоков элементарных событий.

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

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

Очевидно, что для регулярного потока закон распределения вы­ражается d-функцией.

В теории массового обслуживания широко используются потоки Эрланга. Они образуются из простейших потоков путем применения к ним операции "просеивания". Эта операция заключается в том, что из простейшего потока удаляется некоторое число точек по опреде­ленному правилу.

Если удаляются точки через одну, т.е. остается каждая 2-я точка, то поток Эрланга называется потоком 2-го порядка (Э₂). Ес­ли удаляются две точки подряд и остается каждая 3-я точка, то по­лучается поток Эрланга 3-го порядка (Э₃). Если удаляются (k-l) точек подряд, а остается каждая k-я точка, то поток Эрланга на­зывается потоком k-го порядка (Э_к). Очевидно, что простейший по­ток является потоком Эрланга 1-го порядка.

Определим закон распределения f_k(t) интервалов Т₁ для пото­ка Э_k. Для этого необходимо найти вероятность появления события в потоке Э_k на элементарном участке (t,t+Dt), что будет иметь место в том случае, когда конец интервала Т = ST_i окажется в пределах элементарного участка: t £ ST_i £ t+dt. Вероятность этого события равна f_k(t)dt. С другой стороны, эта вероятность равна произведению вероятностей двух событий:

- на участок длиной t должна попасть k-l точка простейшего потока;

- последняя (k-я) точка должна попасть на участок (t,t+Dt).

Вероятность первого события можно определить в соответствии с пуассоновским законом (1.21)

.

Вероятность второго события равна, по определению, элементу веро­ятности появления события в простейшем потоке (1.27), т.е. ldt. Перемножая эти вероятности, получим

 

откуда следует

                  .           (1.28)

 

Закон распределения (1.28) называется законом Эрланга. При k=1 закон Эрланга вырождается в показательное распределение.

Каждый интервал в потоке Э_k равен: Т = ST_i, где T_i - неза­висимые случайные величины, распределенные по показательному за­кону с первыми двумя моментами, определяемыми выражениями (1.26). Применяя теоремы о сложении математических ожиданий и дисперсий для суммы независимых случайных величин, получим

                              (1.29)

 

Целесообразно выразить параметры непосредственно через интенсив­ность потока Эрланга Э_k. Очевидно, что L_k = l/k, l = kL_k. Пред­ставив таким образом интенсивность исходного пуассоновского пото­ка, получим в соответствии с (1.29):

 

                           (1.30)

 

Сделав соответствующую подстановку в (1.28), определим закон Эр­ланга в виде

 

 

Из (1.30) следует, что, устремляя порядок k потока Эрланга к бесконечности, получим m_t = 1/L_k; D_t ® 0. Это означает, что случай­ная величина Т приближается к постоянной величине, равной матема­тическому ожиданию. При этом поток Эрланга вырождается в регуляр­ный поток.

Отмеченное свойство потоков Эрланга и является причиной, по которой они широко используются для аппроксимации реальных пото­ков, изменяя k от 1 (полное отсутствие последействий, пуассоновский поток) до ¥ (жесткая связь между моментами появления событий, регулярный поток), можно получить широкий спектр различных случа­ев, располагающихся по своим свойствам между этими двумя крайними полюсами.

Рассмотрим (без доказательств) два типичных преобразования, выполняемых над случайными потоками: суммирование потоков и раз­режение потоков,

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

1) Для суммарного потока существует предельная теорема: сум­ма независимых, ординарных и стационарных случайных потоков схо­дится к пуассоновскому потоку при неограниченном увеличении числа слагаемых [3]. Интенсивности суммируемых потоков должны при этом быть соизмеримы. Эта теорема аналогична центральной предельной теореме для случайных величин.

2) При сложении n как стационарных, так и нестационарных по­токов интенсивность суммарного потока равна сумме интенсивностей потоков-слагаемых и выражается соотношением

                                            (1.31)

 

Разреженным (редеющим) потоком называется поток, получающий­ся из исходного потока путем случайного удаления из него событий с постоянной вероятностью q. Иными словами, событие исходного по­тока остается в разреженном с вероятностью р = 1-q.

Следует различать операцию детерминированного "просеивания", с помощью которой получаются потоки Эрланга, и операцию случайно­го разрежения.

В качестве примера редеющего потока можно привести поток не­обслуженных заявок на выходе СМО с отказами (например, поток са­молетов, прорвавшихся через систему ПВО, которая сбивает случай­ное число этих самолетов). Отметим основные свойства редеющих по­токов [3].

1) Для редеющих потоков существует предельная теорема: если последовательно разрежать исходный стационарный ординарный поток Пальма с вероятностями р₁,р₂,…,р_n, то многократно разреженный поток стремится к пуассоновскому при n®¥.

2) Интенсивность разреженного потока l_p равна интенсивности исходного потока, умноженной на вероятность сохранения события в потоке, т.е. l_p = рl.

В заключение отметим, что марковские цепи являются математи­ческими моделями некоторых реальных систем, а потоки событий яв­ляются моделями внешних воздействий на эти системы. В дальнейшем будем считать, что переход системы из одного состояния i в другое j в соответствии с размеченным графом состояний происходит под действием потока событий с интенсивностью l_ij, равной соответс­твующей плотности вероятности перехода. Эта интенсивность определяется как среднее число переходов из состояния i в состояние j за единицу времени.

Если все потоки событий являются пуассоновскими, то процесс в системе будет марковским.

Модели систем с очередями

Рассмотрим вначале простейшую одноканальную СМО с очередью, число мест в которой ограничено числом m (рис. 2.4). В системе возможны такие состояния: S₀- прибор свободен, очереди нет; S₁ -прибор занят, очереди нет; S₂ - прибор занят, в очереди стоит од­на заявка; S₃ - прибор занят, в очереди стоят две заявки; …; S_m+1 - прибор занят, в очереди стоят m заявок.

 

Рис.2.4

 

Если заявка приходит в момент времени, когда система нахо­дится в состоянии S_m+1, то она получает отказ и покидает систему. Поскольку работает только один прибор, то интенсивность потока обслуживаний m одинакова для всех состояний. Используя правила вычислений вероятностей состояний для данного процесса размноже­ния и гибели, получим

p₁ = p₀l/m = rp₀, …, p_k = r^kp₀, …,p_m+1 = r^m+1p₀

 

            .           (2.18)

 

 

В формуле (2.18) использован тот факт, что знаменатель является суммой членов геометрической прогрессии со знаменателем r. С по­мощью (2.18) можно рассчитать основные характеристики системы.

1. Вероятность отказа в соответствии с правилами работы сис­темы равна вероятности последнего состояния p_m+1:

.

2. Относительная пропускная способность

                                     (2.19)

 

3. Абсолютная пропускная способность

4. Среднее число заявок, находящихся в очереди (математи­ческое ожидание количества заявок), определяется путем суммирова­ния всех возможных длин очередей от 1 до m с их вероятностями в качестве весовых коэффициентов:

                           (2.20)

 

Подставляя в (2.20) значения вероятностей из (2.18), получим

                                     (2.21)

Для вычисления суммы в (2.21) воспользуемся методом дифференциро­вания рядов с учетом формулы суммы геометрической прогрессии со знаменателем r:

                         (2.22)

Следовательно, подставляя (2.22) и (2.18) в (2.21), получим

               (2.23)

 

5. Среднее число заявок, находящихся в системе:

где W - случайная величина, принимающая значения 0 (канал свобо­ден) и 1 (канал занят). Вероятность занятости канала (с учетом (2.19))

                                     (2.24)

 

Следовательно, M[W] = 0×p₀+l(l-p₀)=rq, откуда

6. Среднее время ожидания заявки в очереди  можно определить, усредняя времена ожидания заявок в очереди по всем состояниям S₁ + S_m+1, с учетом вероятностей этих состояний. Поскольку среднее время обслуживания одной заявки равно l/m, то среднее время ожидания заявки в очереди

            

Подставляя сюда выражение для p₁ из (2.18) и принимая во внимание формулу (2.22), имеем:

                       (2.25)

 

Сравнивая (2.25) и (2.21), получим  = /l. Таким образом, среднее время ожидания заявки в очереди равно среднему числу зая­вок в очереди, деленному на интенсивность потока заявок. Среднее время нахождения заявки в системе  определяется аналогичным об­разом:

7. Среднее время простоя канала t_ПК, в соответствии с (2.17) равно:

где среднее время занятости  = 1/m, а p_ЗК определяется из (2.24). Тогда

Рассмотрим теперь предельный случай, когда число мест в очереди не ограничено (m®¥). Этот случай имеет смысл только при r<1. Тогда геометрическая прогрессия в знаменателе (2.18) сходится. Если же r>0, то Srⁱ=¥ и для любого конечного k

Это означает, что для любого k система рано или поздно пройдет состояние s_К и никогда в него не вернется, двигаясь все время вправо по графу процесса "размножения и гибели", т.е. очередь бу­дет разрастаться до бесконечности. Иными словами, если l³m, то система при бесконечной длине очереди не справляется с потоком заявок. Поэтому, когда m=¥ мы будем рассматривать только слу­чай r<1. Тогда в системе наступит стабилизация очереди на ка­ком-то конечном уровне. Для r<1, переходя в (2.18) к пределу при m®¥, будем иметь

                    (2.26)

Поскольку все заявки рано или поздно будут обслужены, то относи­тельная пропускная способность будет равна 1. Абсолютная пропускная способность А=lq=l. Среднее числа заявок в очереди (см.(2.23))

                                              (2.27)

 

Среднее число заявок в системе

                                              (2.28)

Среднее время ожидания в очереди  и среднее время нахождения заявки в системе t_c равны соответственно

                    (2.29)

 

Перейдем к рассмотрению многоканальной СМ0 с очередью. Пусть число каналов обслуживания равно n, а число мест в очереди - m. Если заявка приходит тогда, когда все nканалов заняты, она ста­новится в очередь. Если же заняты и все m мест в очереди, то за­явка получает отказ и покидает систему.

В такой СМО возможны следующие состояния: S₀ - все каналы свободны, очереди нет; S₁ - один канал занят, очереди нет; …; S_n - n каналов заняты, очереди нет; S_n+1 - n каналов заняты, в очереди стоит одна заявка; …; S_n+m - n каналов заняты, в оче­реди стоят m заявок.

Размеченный граф состояний данной СМО представлен на рис 2.5.

 

 

 

Рис. 2.5

 

Интенсивность потоков обслуживания, переводящих систему по цепочке влево, возрастает с подключением новых каналов до тех пор, пока СМО не достигнет состояния S_n. После того как в рабо­ту включатся все n каналов СМО, интенсивности потоков обслужива­ния остаются неизменными и равными nm для состояний S_n + S_n+m.

Введем обозначение

              æ = r/n = l/nm.                              (2. 30)

Величину æ назовем приведенной интенсивностью потока заявок многоканальной СМО. Тогда в соответствии с правилом вычисления веро­ятностей состояний для процесса размножения и гибели получим:

p₁ = rp₀, p_n+1 = rⁿæp₀/n!

p₂ = r²p₀/2!, p_n+2 = rⁿæ²p₀/n!

…

p_n = rⁿp₀/n!, p_n+m = rⁿæ^mp₀/n!

 

                                      (2.31)

 

Просуммируем геометрическую прогрессию со знаменателем æ в выражении для р₀. Получим

               .               (2.32)

 

Выражения (2.31) и (2.32) дают возможность по аналогии с одноканальной СМО определить все основные характеристики многоканальной СМО:

1. Вероятность отказа

      p_ОТК = p_n+m = rⁿæ^mp₀/n!

2. Относительная пропускная способность

      q = 1 - p_ОТК = 1 - rⁿæ^mp₀/n!

3. Абсолютная пропускная способность

      А = lq = l[1 - rⁿæ^mp₀/n!]

4. Среднее число заявок в очереди

5. Среднее число занятых каналов . Если каждый канал об­служивает в среднем m заявок в единицу времени, а вся СМО обслу­живает А заявок за то же время, то среднее число занятых каналов

                                       (2.33)

Отсюда можно определить вероятность занятости канала p_ЗК = /n.

6. Среднее число заявок, находящихся в системе, .

7. Среднее время ожидания заявки в очереди .

8. Среднее время ожидания заявки в системе .

Перейдем к предельному случаю при m®¥. Легко заметить, что этот переход возможен, как и в предыдущей СМО, только при æ < 1 (l < nm), так как в данном случае в выражении для р₀ суммиру­ется геометрическая прогрессия со знаменателем æ. Опуская проме­жуточные выкладки, которые рекомендуется проделать читателю, выпишем основные соотношения для предельного случая.

1. Предельные вероятности состояний

                                       (2.34)

p₁ = p₀r¹/1!      (i=1,…,n)

…

p_n+j = æ^jp₀rⁿ/n!   (j=n+1,…,¥)

2.Вероятность отказа Р_ОТК = 0, q = 1, A = l.

3. Среднее число заявок в очереди

                                 (2.35)

4. Среднее число занятых каналов z и среднее число заявок k, находящихся в системе:

                         (2.36)

 

Остальные характеристики находятся аналогичным образом.

В заключение рассмотрим СМО с ограниченным временем пребывания заявки в очереди. Будем считать, что число мест в очереди не ограничено (m=¥), а число каналов обслуживания равно n. Раз­меченный граф состояний такой системы представлен на рис.2.6, где состояния S₀ + S_n+rимеют тот же смысл, что и в предыдущем случае. Различие заключается в том, что заявки могут находиться в очереди ограниченное время, после чего они покидают систему, если за время ожидания их не успеют обслужить. Для того чтобы рассмот­реть такую СМО с "нетерпеливыми" заявками в рамках теории марковских процессов, будем считать, что на заявки, стоящие в очере­ди, действует пуассоновский "поток уходов" с интенсивностью v. Если среднее время ожидания заявки в очереди равно , то

 

 

Рис.2.6

Тогда интенсивности потоков, переводящих состояние системы влево, равны сумме интенсивности потока обслуживании nm и соответствую­щих интенсивностей потоков уходов rv = r/ , где r - число зая­вок, находящихся в очереди. Кроме приведенной интенсивности пото­ка заявок æ = l/nm введем также приведенную интенсивность потока уходов многоканальной СМО b = v/nm.

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

                       (2.37)

 

 

Бесконечный ряд в выражении для р₀ сходится при любых æ и b. В этом можно убедиться, применяя любой известный признак сходимости рядов. Это означает, что поток уходов стабилизирует очередь и не позволяет ей разрастись до бесконечности. Среднее число заявок, находящихся в очереди такой СМО, можно определить обычным обра­зом:

Однако такой способ весьма затруднителен, так как требует вначале подсчета суммы членов бесконечного ряда в формуле (2.37), а затем необходимо снова определять сумму членов уже другого бесконечного ряда для нахождения среднего значения r. Это затруднение можно обойти следующим образом.

Определим вначале абсолютную пропускную способность. Если в очереди содержатся в среднем r заявок, то в единицу времени будет уходить vr заявок, а приходить - l заявок. Оставшиеся после ухо­дов заявки будут обслужены, следовательно.

             А = l - v  .                                   (2.38)

Относительная пропускная способность

                                         (2.39)

Среднее число занятых каналов определяется аналогично предыдущему случаю:

                                    (2.40)

 

Из (2.40) можно найти r:

                                               (2.41)

Таким образом, среднее число заявок в очереди мы выразили через среднее число занятых каналов. Эта величина, очевидно, получается в результате суммирования конечного ряда

Однако сумму этого ряда определить достаточно сложно из-за необходимости суммирования бесконечного ряда для нахождения р_n. Чтобы обойти это затруднение, сумму членов бесконечного ряда заменя­ют суммой (r-1) членов конечного ряда, отбрасывая все остальные члены, начиная с r-го. Легко показать, что погрешность вычисления суммы в результате такой замены

.

Заметим, что из (2.37) - (2.41) при v®0 (или b®0) в пределе получаем выражения для обычной многоканальной СМО с очередью ("нетерпеливые" заявки становятся "терпеливыми"). Вероятность от­каза в такой СМО с "нетерпеливыми" заявками не имеет смысла.

Все прочие характеристики СМО находятся способом, аналогичным ранее описанному.

 

Модель замкнутой системы

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

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

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

Однако в ряде случаев количество источников заявок ограниче­но сравнительно небольшим числом. Так, например, если рассматри­вать как СМО бригаду слесарей-ремонтников, обслуживающих станки в некотором цехе, то такая СМО является замкнутой. Действительно если станок испортился и в данный момент либо ремонтируется, либо ожидает в очереди на ремонт, то он перестает быть источником зая­вок. Поскольку количество станков в цехе ограничено, то выход из строя одного или нескольких станков существенно сказывается на интенсивности потока заявок на обслуживание. То же самое можно сказать об авторемонтной мастерской, обслуживающей гараж како­го-либо предприятия, или об авиаремонтных базах, обслуживающих аэропорт. Если обозначить через R(t) случайное число заявок, на­ходящихся в очереди на обслуживание в момент времени t, Z(t) - случайное число обслуживаемых заявок в момент времени t, H(t) - случайное число заявок, не нуждающихся в обслуживании, m - общее число источников заявок, то в любой момент времени должно соблю­даться равенство

m = R(t) + Z(t) + H(t)

как для мгновенных значений, так и для математических ожиданий

                                                  (2.42)

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

Назовем уравнение (2.42) уравнением расхода замкнутой СМО. Источники заявок замкнутой СМО назовем техническими устройствами (ТУ). Это могут быть самолеты, станки, автомобили и т.п. Тогда из уравнения расхода (2.42) следует ряд важных характеристик замкну­тых СМО.

Если общее число каналов обслуживания (например, рабочих-ре­монтников) равно n, то можно определить следующие коэффициенты для оценки эффективности СМО:

1. Коэффициент использования ТУ (вероятность того, что ТУ не будет нуждаться в обслуживании)

                                    (2.43)

2. Коэффициент ожидания c (вероятность того, что ТУ находит­ся в очереди на обслуживание)

                 c = /m.                                (2.44)

3. Коэффициент простоя канала обслуживания (вероятность не­занятости канала)

                   К_ПР= 1- /n.                           (2.45)

4. Коэффициент простоя ТУ (вероятность того, что ТУ находит­ся в очереди или в обслуживании)

            z = 1 - x =( + )/m.                         (2.46)

5. Коэффициент (вероятность) нахождения ТУ в обслуживании

             y = /m.                                   (2.47)

Если обозначить - среднее время ожидания заявки в очереди,  - среднее время обслуживания заявки в очереди, а  - среднее время безотказной работы ТУ, то на основании эргодического свойства будем иметь

y =  (