Тел.факс: +7(831)437-66-01
Факторинг  Теория очередей и материальные запасы 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 [ 27 ] 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

есть к-\л факториальный момент распределения числа заявок в очереди. Этот результат получен в статье [115]. В частности, среднее время ожидания в очереди

Wi=q[i]/X = qi/X (3.11.6)

(известная формула Литтла).

Аналогичная связь существует между факториальными моментами распределения числа заявок в системе и моментами распределения времени пребывания заявки в ней для систем M/G/1 и M/D/n . Усиленная формула Литтла

VI = L/X (3.11.7)

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

Сохранение вероятностей состояний. Рассмотрим процесс переходов через разрез АВ в марковской системе (диаграмма переходов рис. 3.6).

/1/2

i->-~ф--

О 1 k-l к

Рис. 3.6. К закону сохранения вероятностей для марковских систем

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

в стационарном реяише средние частоты переходов через разрез в противоположных направлениях равны.

Для диаграммы рис. 3.6 с переходами только между соседними состояниями применение этого закона непосредственно приводит к равенству

Pk-iXk-i =ркРк (3.11.8)

так что необходимые вероятности можно определить рекуррентно:

Рк = -Рк-ъ А:=1,2,..., (3.11.9)



3.12. Расчет марковских систем по законам сохранения 93

отправляясь от начальной вероятности ро .

Частным случаем разреза является кольцевой разрез, выделяющий одно из состояний системы. При этом противоположным направлениям соответствуют входящие и выходящие стрелки.

Сохранение объема работы. Выделим класс так называемых консервативных дисциплин обслуживания, в котором возобновление прерванного обслуживания производится без потери ранее затраченных ресурсов. В указанном классе дисциплин

распреде.тение объема невыполненной работы, находящегося в СМО, постоянно и не зависит от выбора конкретной дисциплины.

Покажем применение этого принципа к расчету среднего времени ожидания заявки в однолинейной системе. Прежде всего, в данном случае средний объем работы совпадает со средним значением w времени ожидания начала обслуживания вновь прибывшей заявкой. Это врегутя будет складываться из времени завершения fi начатого обслуживания и времени обслуживания находящихся в очереди ранее пришедших заявок. Средний остаток начатого обслуживания определяется формулой (3.1.2) и должен учитываться с вероятностью занятости системы, равной р - Xbi :

h=pb2/{2b,) = Xb,/2.

Среднее число заявок в очереди на основании формулы Литтла составит Xw , причем каждая из них в среднем обслуживается 6i единиц времени. Итак, закон сохранения объема работы приводит к равенству

W = Л62/2 -f Au)6i, откуда следует формула (Полячека-Хинчина)

W = Лб2/[2(1 -/>)] (3.11.10)

для среднего времени ожидания в M/G/i .

3.12. Расчет марковских систем по законам сохранения

Применим законы сохранения к расчету основных показателей системы М/М/1 . Прежде всего отметим, что для этой СМО Л(А) = Л и



pfk) = fi независимо от к . Следовательно, для всех к имеет место ppki = Xpk , или pki - {Х/р)рк - рРк и стационарные вероятности

(3.12.1)

образуют геометрическую прогрессию со знаменателем р - X/р . Условием существования стационарного режима является неравенство р < 1 . Вероятность ро - 1-Р . найденная здесь из условия нормировки, совпадает с выражением (3.11.1) при соответствующей замене обозначений, что подтверждает закон сохранения требований.

Для 71-канальной системы распределение числа требований в системе задается вероятностями

-i(W (A i) 1

гГо г!

[п-\)\1-р\

Рг Pi

= Ро-

= РпР

{/рУ

i= 1,п,

(3.12.2)

г = гг + 1,71 + 2,...

ЗЛЗ. Система M/G/1

Выделим смежные моменты {г]п], п = 1,2,..., окончания обслуживания очередного требования в системе M/G/1 и рассмотрим состояния системы в моменты регенерации {т]п -f 0} . В эти моменты система либо свободна, либо только начинает обслуживание, так что фиксировать значение истекшего времени обслуживания не нужно. Такой процесс является вложенным в исходный и, поскольку полностью (в вероятностным смысле) определяется своим текущим состоянием, называется вложенной цепью Маркова.

Обозначим qj вероятность прибытия j новых требований за время обслуживания. Нетрудно видеть, что {qj} определяются согласно (3.6.3) и при аппроксимации распределения времени обслуживания гамма-плотностью проблем с их вычислением не будет. В установившемся режиме застать в системе к требований в очередной момент регенерации можно, если в ней:

а) в предыдущий момент регенерации находилась j -f 1 заявка и ) . одна обслужилась и пришло еще к - j >0 заявок;



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 [ 27 ] 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123