Файл: Л. В. Горчаков в в в в е е д д е е н н и и е е в в к к о о м м п п ь ь ю ю т т е е р р н н о о е е м м о о д д е е л л и и р р о о в в а а н н и и е е учебное пособие.pdf

70 плина очереди, e – максимальное число допускаемых в систему требований (число требований в очереди + число требований, при- нятых на обслуживание), f – емкость источника, генерирующего заявки на обслуживание. Для a и b приняты следующие обозначе- ния:
М – пуассоновское распределение моментов поступлений заявок на обслуживание или выбытий из системы обслуженных клиентов
(или экспоненциальное распределение интервалов времени между моментами последовательных поступлений или продолжительно- стей обслуживания клиентов),
D – фиксированный (детерминированный) интервал времени между моментами последовательных поступлений в систему за- явок на обслуживание или детерминированная (фиксированная) продолжительность обслуживания,
E
k
– распределение Эрланга или гамма-распределение интерва- лов времени между моментами последовательных поступлений требований в обслуживающую систему или продолжительностей обслуживания (при этом k –параметр распределения),
GI – распределение произвольного вида моментов поступления в систему заявок на обслуживание (или интервалов времени между последовательными поступлениями требований),
G – распределение произвольного вида моментов выбытия из системы обслуженных клиентов (или продолжительностей обслу- живания).
Например,

 

/
/10 :
/
/
M D
GD N

означает систему массо- вого обслуживания с пуассоновским входным потоком, фиксиро- ванным временем обслуживания и 10 параллельными узлами, дис- циплина очереди не регламентирована, независимо от числа посту- пающих требований данная система (очередь + обслуживаемые клиенты) не может вместить более N требований, т.е. остальные не принимаются, источник

емкости.
При решении такого сорта задач возможны две ситуации:
1) число заказов слишком велико, что приводит к большому времени ожидания в очереди и говорит о недостаточном количе- стве станций обслуживания;
2) недостаточное число заказов, что приводит к большому вре- мени простоя оборудования и говорит об избытке оборудования.

71
Поскольку оба требования являются взаимоисключающими, то целью решения задачи являются установление оптимального соот- ношения между потерями, вызванными простоем оборудования и потерями из-за ожидания в очереди.
Примером, который часто приводится в литературе, служит мо- делирование системы массового обслуживания с одной станцией обслуживания, обслуживание в порядке поступления, время об- служивания и время между поступлениями распределены по экс- поненциальному закону. Если мы возьмем некоторый интервал времени между поступлениями i-го и (I + 1) требований и обозна- чим его ATi, а время обслуживания i-го требования –STi, то время ожидания (WTi) и простой станции (IT) можно изобразить графиче- ски, как это сделано на рис. 20. время
ST1
ST2
ST3
WT2
IT
WT4
AT1 AT2
AT3 AT4
Рис. 20. Одноканальная система массового обслуживания
Рассмотрим самый простой вид потока заявок – стационарный пуассоновский поток, который имеет свойства стационарности, ординарности и отсутствия последействия. Поток является стацио- нарным, если его вероятностные характеристики не зависят от сдвига во времени, т.е. вероятность, что на интервале t происходит некоторое количество событий, зависит от длины интервала и не зависит от его положения на оси t. Поток является ординарным, если в каждый момент времени может поступать только одна заяв- ка. Отсутствие последействия означает независимость событий друг от друга, т.е. длина интервала времени до момента поступле- ния следующей заявки не зависит от того, поступила ли в начале этого интервала заявка или нет.
Рассмотрим процесс образования очереди на единственной станции – найдем среднюю длину очереди и вероятность появле- ния очереди заданной длины при случайных потоках заказов.
Пусть скорость обслуживания не зависит от числа заказов в очере-

72 ди и заказы обслуживаются по очереди. Используем следующие обозначения:
 
n
P t
– вероятность образования очереди из n заказов к момен- ту t;

t – вероятность появления в очереди нового заказа в проме- жутке времени от t до t+

t, где

– средняя скорость появления заказов;

t – вероятность того, что в интервале времени от t до t+

t за- вершается исполнение заказа, находящегося на обслуживании, где

– средняя скорость обслуживания;
s
L
– среднее число находящихся в системе клиентов (заявок);
L
q
– среднее число клиентов в очереди на обслуживание;
W
s
– средняя продолжительность пребывания клиента в системе;
W
q
– средняя продолжительность пребывания клиентов в очере- ди.
По определению [11]


0
,
s
q
n
n
n c
L
np L
n c p









, где с – число узлов обслуживания.
Между
L
s
и W
s
(L
q
и W
q
) существует строгая взаимосвязь. В частности, если частота поступлений в систему заявок равна

, то
L
s
=

W
s
, L
q
=

W
q
Если не все заявки могут попасть в блок ожидания, то вводят

эфф
, учитывающее действительно допускаемые в систему требова- ния, т.е. эффективная частота поступлений. Тогда
L
s
=

эфф
W
s
,
L
q
=

эфф
W
q
В общем случае эфф
, 0 1

    
. В любом случае можно установить зависимость от
L
s
и Lq для эфф

. По определению средняя продолжительность пребывания в системе равна средней продолжительности пребывания требований в очереди плюс сред- нее время обслуживания. Если средняя скорость обслуживания –

и средняя продолжительность обслуживания 1/

, то W
s
= W
q
+ 1/

Умножая на

, получаем
L
s
= L
q
+

. Это справедливо и для эфф
  
. При этом


эфф
s
q
L
L

 

. Далее основное внимание

73 будет направлено на формулы для
n
P
, так как из них можно полу- чить все остальные в следующей очередности
0 1
n
s
n
s
s
q
s
q
q
n
P
L
np
W L
W
W
L
W


 
 
 

    

Рассмотрим пример, пусть с = 1 и среднее количество поступлений
– 3 в час, а скорость обслуживания – 8 в час. Вероятность того, что в системе окажется n требований –
n
P
определяется на основе наблюдений и данные помещены в табл. 11.
Таблица 11
n
0 1
2 3
4 5
6 7

8
n
P
0,615 0,234 0,088 0,033 0,012 0,005 0,002 0,001 0
Вычислим
L
s
, W
s
, W
q
, L
q
0 0 0, 625 1 0, 234 2 0, 088 3 0, 033 4 0, 012 5 0, 005 6 0, 002 7 0, 001 0, 6.
s
n
n
L
np



 
 
 
 

 
 
 
 


Так как

= 3, то
0, 6 3 0, 2
s
s
W
L

 

часа.
Учитывая, что

= 8, имеем
1 0, 2 1 8 0, 075
q
s
W
W
   


часа, т.е. среднее количество находящихся в очереди клиентов равно
3 0, 075 0, 225
q
q
L
W
 
 

Вычислите среднее количество находящихся в очереди требова- ний, используя
n
P
– ответ


2 1
0, 225
q
n
n
L
n
p






Вычислите среднее количество клиентов, которое обслуживает- ся системой – ответ
0,375
s
q
L
L

   
В теории массового обслуживания показано, что поведение ве- роятности P
n
(t) будет описываться дифференциальными уравнени- ями
 
 
  
   

1 1
,
0
n
n
n
n
dP t
dt
P
t
P
t
P t
n


 
 
   

,
 
 
 
0 0
1
dP t
dt
P t
P t
 
 
(51)
Они в неявном виде отражают связь между временем ожидания и временем обслуживания и являются исходным пунктом для реше-

74 ния задач теории очередей. В частном случае
 
n
n
P t
P
const


решение имеет простой вид



 

0 1
,
1
n
n
P
P
   
  
  
,
(52) где
n
P
– вероятность появления очереди длины n. Отношение

/

называется интенсивностью нагрузки – средний объем обслужива- ния в единицу времени. Для среднего числа находящихся в системе клиентов получается формула

 

0 1
,
1
s
n
n
L
np



  
     

. (53)
Пусть число поступающих заказов в день равно

= 10, а скорость обслуживания

= 20 заказов в день. Тогда

/

= 1/2. Подставляя это значение в формулы, получим
  

  

1 2 1 1 2 и
1 2 1 1 2 1
n
n
s
P
L





(54)
Тогда вероятность появления очереди из 0,1,2… заказов в любой момент времени будет иметь вид табл. 12
Таблица 12
N
0 1
2 3
Pn
1/2 1/4 1/8 1/16
С увеличением интенсивности нагрузки

/

средняя длина очереди быстро возрастает и при

/

->1 становится бесконечной. Уравне- ние для n перестает быть справедливым при

/

=1. Подставляя не- сколько значений

/

в формулу, можно найти как изменяется средняя длина очереди в зависимости от

/

(табл. 13).
Таблица 13
Интенсивность нагрузки
1/2 3/4 7/8 15/16
Средняя длина очереди
1 3
7 15
Обозначим



, тогда






2 1
1
,
1
,
1
s
q
q
W
L
W

 
 

   








Рассмотрим пример, пусть на мойку автомобили поступают по за- кону Пуассона со средней интенсивностью 5 автомобилей в час.

75
Продолжительность обслуживания подчиняется экспоненциально- му закону со средним значением 10 автомобилей в час. Узел об- служивания один. Таким образом,

= 5,

= 60/10 = 6 автомобилей в час, таким образом,

=

= 5/6<1 и достигается стационарный режим. Вычислим, какое количество стоянок нужно оборудовать на мойке.
 
 


2 5 6 1
5 6 4,14 4
q
L




автомобиля.
Но
L
q
– это математическое ожидание, т.е. может быть больше или меньше этого количества. Допустим, цель обеспечить одновремен- но 80% клиентов стоянкой. Это эквивалентно выполнению условия
0 1
0,8
s
p
p
p

 

. Используя формулу для
n
p
, можно запи- сать

 



1 1
1 0,8
s
        
Учитывая, что

 















1 1
1 1
1 1
1 1
1 1
1
,
s
s
s
s


             
     


  
 
    


получаем
1 0, 2
s



. Логарифмируя при

= 5/6, имеем

  
1 log 5 6
log 0,8
s


Так как log(5/6)<0, то деление на log(5/6) меняет знак неравенства, т.е. для
s
получаем
 
log 0, 2 log 5 6 1 7,8 8
s

 

площадок.
Можно вычислить долю времени бездействия мойки – вероятность того, что на мойке не окажется ни одного автомобиля
0 1
0,17
p
  
, т.е. 17% времени простаивает. Для оценки каче- ства обслуживания полезно знать среднее время пребывания авто- мобиля на станции (от момента прибытия до момента завершения мойки).




1 1
1 6 1 5 6 1 час
s
W

  










Вычислите вероятность то, что прибывший автомобиль будет ждать обслуживания – ответ 0.8333.

76
Вычислите вероятность того, что при наличии 6 мест для стоянки для прибывающего автомобиля не найдется места – ответ
7 7
0, 279
n
p

  
Для системы массового обслуживания вида (M/M/1):(GD/N/

) для вероятностей были получены следующие формулы




1 1
1
, для
1 и
0,1,...
N
n
n
P
n
N







 



,


1 1 для
1
n
P
N


 








1 1
1 1
1 1
для
1
N
N
N
s
L
N
N



 

  
   




 

,
2
s
L
N

для

= 1.
Рассмотрим пример, пусть мойка имеет 5 площадок для стоян- ки. Службу интересует количество клиентов, которое она теряет из-за ограниченности числа площадок. Это эквивалентно нахожде- нию разности между

и

эфф


эфф
1
N
p

  
, откуда эфф
N
p
  
 
. Здесь
5 1 9,
5 6
N
    
и
 


 


 
7 6
1 5 6 1
5 6 5 6 0, 07774,
6
N
p
N











, т.е. частота возникновения ситуаций, когда все пять стоянок заня- ты, равна 5

0,07774 = 0,387 автомобилей в час, при 8-часовом рабо- чем дне – это означает потерю трех клиентов в среднем. Опреде- лим среднее время пребывания на мойке, вычислив L
s
и W
s
 
 
 




 


6 7
7 5 6 1 7 5 6 6 5 6 1 5 6 1 5 6 2, 29
s
L














Так как вероятность того, что требования не имеют возможности присоединиться к очереди равна
N
p (т.е. вероятности, что в систе- ме уже N требований) доля требований, которым разрешено войти в блок ожидания равно


1
N
P n
N
p

 
Отсюда


эфф
1
N
p

  
,


эфф
1
q
q
q
N
W
L
L
p



 
,


эфф
1
s
q
q
N
L
L
L
p

 
 
  

,


1 1
s
q
s
N
W
W
L
p

  
 

77
Таким образом,




эфф
1
s
q
N
L
L
p

 

  
С учетом

 

эфф
6 1
5 1 0, 07774 4, 613
p

  



, получаем эфф
2, 29 4, 613 0, 496
s
s
W
L




часа.
Таким образом, при введении ограничения на количество мест для стоянки (N = 6) среднее время ожидания сократилось на полча- са по сравнению с

очередью. Это достигнуто за счет «потери» в среднем трех автомобилей в день из-за недостаточности мест для стоянки.
1>

78 ожидания на одной станции при экспоненциальном распределении с отрицательным показателем определяется выражением


1 1
t

    
, а среднее время обслуживания
t
s
= 1/

Иллюстрацию появления и движения заявок в очереди можно представить в виде рис. 21.
Рис. 21. Времена ожидания
Цифры на графике соответствуют порядку поступления заявок в систему, а время ожидания определяется по отношению к общей продолжительности рассматриваемого интервала. Легко видеть, что площадь под ступенчатой кривой равна произведению nT, где n среднее число заявок в системе. Общая площадь квадратов, поме- ченных цифрой 3, равна 6. Это означает, что общее время ожида- ния третьего требования на интервале Т составило 6 единиц. То же касается и требований 4,5,6. Площадь под кривой включает время ожидания требований, поступивших на интервале Т и обслуженных на нем, плюс время ожидания требований, поступивших до начала этого интервала, плюс время ожидания требований, попавших за интервал Т в систему, но не обслуженных за это время. Тогда

W = n, где W – среднее время ожидания, n – длина очереди,

– средняя интенсивность поступления требований на интервале.
7.3. Имитация задач теории массового обслуживания [3]
Раccмотрим одноканальную однофазовую модель. В ней систе- ма состоит из одной станции, на которую поступают заявки, обра- зующие очередь. Если станция свободна, то она приступает к об-