Вероятности и неприятности. Математика повседневной жизни

Свойства очереди сильно зависят от соотношения λ и μ. Если λ > μ, хвост будет расти неограниченно, как пробка на дороге, в которую въезжает больше автомобилей, чем может выехать. Она попросту перекрывает поток клиентов, накапливая их в себе. Для λ < μ очередь устойчива. Она может расти или уменьшаться по мере того, как клиенты добавляются и выходят из нее, но клиенты в ней не накапливаются неограниченно: сколько их вошло в зону ожидания, столько же выйдет. Иными словами, устойчивая очередь может затормозить тех, кто в ней стоит, но неспособна изменить интенсивность потока людей, проходящих сквозь нее. И если на входе мы имеем в среднем λ человек в единицу времени, то и на выходе должны получить такой же поток, независимо от скорости работы оператора. Случай λ ≈ μ рассматривается отдельно. Такая метастабильная очередь ведет себя неустойчиво и моделируется процессом случайного блуждания — с той только разницей, что длина очереди не может быть отрицательной. У блуждающей таким образом системы есть непроницаемая стенка снизу, которая, однако, не мешает практически неограниченному росту длины очереди. И хотя рано или поздно она сократится и даже исчезнет, отклонения времени ожидания и времени работы оператора от среднего будут столь велики, что счесть такое обслуживание удовлетворительным никак не получится. Далее мы будем рассматривать только устойчивые очереди. От характера распределений p_in(t) и p_out(t) зависят динамика очереди и ее характеристики, такие как распределение для ее длины, времени ожидания клиентом и времени занятости оператора. Для очередей создана система обозначений, называемая нотацией Кендалла. Например, простая очередь, в которую люди входят равномерно и так же уходят, как, например, в аэропорту при посадке на рейс, обозначается D/D/1 (буква D здесь обозначает детерминированный процесс, соответствующий вырожденному распределению, а единица — одного оператора). Въезд и выезд автомашин на территорию аэропорта через три автоматических шлагбаума можно описать очередью M/D/3. Буквой M обозначается пуассоновский (марковский) процесс, то есть случайный процесс без памяти. В очередь на регистрацию билетов и оформление багажа новые люди приходят по-пуассоновски, и багаж у всех разный, так что клиенты будут выходить из очереди тоже по-пуассоновски. Для пяти стоек такая очередь обозначается M/M/5. Собственные обозначения существуют и для других видов распределений. Если же мы вообще ничего не знаем о распределении появления клиентов или методах их обслуживания, то обозначаем такой произвольный процесс буквой G (от слова General — общий).

В этой главе мы будем исследовать неприятности и неожиданности, наблюдаемые в очередях, на примере очереди с λ = 30 чел./ч и μ = 34 чел./ч. В среднем новые клиенты будут поступать в нее с интервалом в 2 минуты, а обрабатываться оператором примерно за 1 минуту 45 секунд. Это похоже на очередь у стойки регистрации в аэропорту. На рисунке 7.4 показан пример того, как могут «жить» M/D/1- и M/M/1-очереди с такими параметрами.

Рис. 7.4. Динамика M/D/1 и M/M/1 очередей. Более темным цветом выделены траектории каждого седьмого клиента в очереди. Длина очереди склонна к своеобразным колебаниям: она «дышит», то удлиняясь, то сокращаясь, оставаясь при этом в стационарном состоянии

В стационарном состоянии длина M/M/1-очереди n описывается геометрическим распределением:

Мы встречали его в предыдущей главе, рассматривая простейшую несимметричную марковскую цепь. Зная это распределение, можно вычислить ожидаемую длину .

Для нашего примера средняя длина очереди составит 7,5 человек. Время обслуживания клиента (сумма времени ожидания своей очереди и собственно времени работы с оператором) в M/M/1-очереди описывается экспоненциальным распределением с параметром μ − λ. Это приводит к значению среднего времени ожидания .

Среднее время работы с каждым клиентом не превышает 2 минут, однако среднее время ожидания для нашего примера равно 15 минутам. Как видно, для стационарной M/M/1-очереди выполняется равенство:

λW = L.

Это и есть формула Литтла, которой мы воспользовались, стоя в очереди и от нечего делать занявшись подсчетами. Будучи очень простой, формула на удивление сильна: она выполняется для очень широкого класса очередей и в самых разных задачах. То, что в формулу Литтла входит только λ, а не μ, отражает основное свойство стабильной (устойчивой) очереди: она может задерживать клиентов, но не меняет их поток, который определяется значением λ. И даже если скорость работы оператора μ будет очень велика, среднее время ожидания все равно определяется входным потоком и уже скопившимся числом клиентов. А поскольку для устойчивых очередей λ<μ, мы получаем еще один закон подлости: