Системы массового обслуживания

с не-пуассоновскими потоками событий

 

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

 

 

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

 

 

Очевидно, что время Тоб обслуживания заявки вовсе не обязательно распределяется по такому закону; напротив, гораздо более типичным является случай, когда закон распределения времени обслуживания f(t) отличен от показательного, и его наивероятнейшее значение не равно нулю.

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

Приведем (без доказательства) некоторые из полученных в этой области результатов.

 

СМО с отказами

 

Пусть на n-канальную систему массового обслуживания с отказами поступает простейший поток заявок с интенсивностью l, а время обслуживания имеет произвольное распределение с математическим ожиданием

                         (67)

 

В этом случае формулы Эрланга для вероятностей состояний остаются справедливыми, а именно

 

            (68)

 

          

Одноканальная СМО с ожиданием

 

Пусть имеется одноканальная система массового обслуживания с неограниченной очередью (n = 1, m = ∞); на вход ее поступает простейший поток заявок с интенсивностью  λ; закон распределения времени обслуживания f(t) – произвольный, с математическим ожиданием  и средним квадратическим отклонением  

Величина

 

 

называется коэффициентом вариации времени обслуживания (этот коэффициент показывает, насколько велик разброс времени обслуживания относительно его среднего значения).

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

 
 


 

                                 (69)

 

где    – коэффициент вариации времени обслуживания. Что касается среднего времени ожидания в очереди, то оно выражается формулой:

 

 

 

                      (70)

 

 

Формулы (69), (70) обычно называются формулами Полячека-Хинчипа.

Заметим, что для показательного распределения

 

          

 

коэффициент вариации

                 

=1

 

В этом случае формулы (69) и (70) превращаются в ранее выведенные нами формулы (34) и (37):

 

 

                  (71)

 

Рассмотрим крайний случай, когда время обслуживания вообще не случайно и равно своему математическому ожиданию:

 

            

 

Тогда  и формулы (69), (70) дают

 

     =                                       (72)

 

и

                                              (73)

 

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

Пример 1. Поток железнодорожных составов, поступающих на сортировочную станцию для обработки, - простейший поток с интенсивностью  = 2 (состава в час). Среднее время, затрачиваемое на обработку одного состава, равно   20 (мин); его среднее квадратическое отклонение  8 (мин). Определить среднее число составов, ожидающих обработки и среднее время ожидания обработки в очереди, а также среднее число составов, связанных с обслуживанием на сортировочной станции.

Решение. Переходя к одной и той же единице измерения времени (час) имеем:

 

       

 

Коэффициент загрузки станции (приведенная интенсивность потока заявок):

 

 

 

Коэффициент вариации времени обслуживания:

 

 

По формулам (5.69) и (5.70) находим среднее число составов, ожидающих обработки

 

 

и среднее время ожидания обработки:

 

(час)

 

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

 

 

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

В качестве примера рассмотрим одноканальную СМО с очередью (без ограничений). На вход системы поступает простейший поток заявок с интенсивностью λ; время обслуживания То6 распределено по закону Эрланга 2-го порядка с математическим ожиданием  , т. е. представляет собой сумму двух независимых случайных величин с одинаковым показательным распределением. Обозначим параметры этих показательных распределений  и найдем значение . По теореме сложения математических ожиданий имеем:

 

 

 

откуда

 

Таким образом, время обслуживания Тоб, распределенное по закону Эрланга 2-го порядка с математическим ожиданием , может быть представлено, как сумма двух независимых случайных величин Тоб(1) и Тоб(2)  имеющих каждая показательное распределение с параметром . Эти два времени Тоб(1) и Тоб(2) можно представить как две последовательные «фазы» процесса обслуживания.

Рассмотрим различные состояния СМО, нумеруя их по числу заявок в системе и фазе обслуживания:

S0 – заявок в системе нет (обслуживания не происходит);

S1,1 – одна заявка находится в СМО, обслуживание в первой фазе; очереди нет;

S1,2 – одна заявка находится в СМО, обслуживание во второй фазе; очереди нет;

S2,1 – две заявки находятся в СМО, первая  обслуживается (первая фаза), вторая стоит в очереди;

S2,2 – две заявки находятся в СМО; первая обслуживается (вторая фаза), вторая стоит в очереди;

………………..

Sk,1 – k заявок находятся в СМО, одна под обслуживанием (первая фаза), остальные – в очереди;

Sk,2 – k заявок находятся в СМО, одна под обслуживанием (вторая фаза), остальные — в очереди;

  ………………..

Размеченный граф состояний системы приведен. Действительно, из состояния S0 в S1,1 систему переводит поток заявок с интенсивностью λ . Из состояния S1,1 в S1,2 систему переводит поток с интенсивностью    (поток окончаний первой фазы обслуживания). Из состояния S1,2 в S0 – такой же поток. Из состояния S1,1 в S2,1 систему переводит поток заявок и т. д.

 

 

 

Пользуясь размеченным графом состояний, запишем линейные алгебраические уравнения для вероятностей состояний:

 

 

 

 

 

(74)

 

 

 

(75)

 

 Это – система бесконечного числа уравнений с бесконечным числом неизвестных p0, p1,1, p1,2, p2,1, p2,2…. Существуют способы, позволяющие решать также системы буквенно, но они сравнительно сложны, и мы не будем на них останавливаться. Ограничимся указанием на то, как может быть решена система (5.70) при конкретных значениях параметров  и .

Прежде всего, оценивается максимальное практически возможное число заявок в очереди – это можно сделать грубо, приняв закон распределения времени обслуживания показательным. Когда это сделано, удается отбросить некоторые (последние, начиная с какого-то номера) из уравнений, после чего система (5.70) превращается в систему конечного числа уравнений с конечным числом неизвестных, которая решается обычными методами вычислительной алгебры. При большом числе уравнений удобно бывает пользоваться методом итераций (последовательных приближений), причем в качестве первого приближения можно взять значения вероятностей состояний, получаемые при показательном распределении времени обслуживания, разделив вероятности поровну между двумя фазами обслуживания.

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

 

или вводя обозначение

 

 

зываемым методом статистических испытаний (Монте-Карло).