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

Стационарный бардак

А теперь немного изменим политику очередности. Пусть внеочередники будут сверхнаглыми, и если так случится, что один такой клиент придет вслед за другим, то вместо формирования нормальной очереди второй вклинится перед первым. Эта задача уже отличается от классического подхода к очередям с приоритетом. Давайте сразу рассмотрим предельный случай, когда доля наглых клиентов равна единице. Тогда наша очередь (рис. 7.10) превращается в то, что программисты называют стеком, — последовательность элементов, подчиняющуюся правилу «первым вошел, последним вышел» (FILO — first in, last out) — в противовес очереди, для которой выполняется правило «первым вошел, первым вышел» (FIFO — first in, first out).

Рис. 7.10. Очередь как стек

Такая «очередь наоборот» выглядит неестественно, но если вместо людей мы рассмотрим пачку документов, то можем увидеть знакомую картину на рабочем столе, когда входящие документы не сортируются по времени, складываются в стопку по мере поступления, а потом обрабатываются начиная сверху. Удивительно, но в стационарном состоянии все средние значения основных параметров — и длины очереди, и времени ожидания, и времени занятости оператора — будут точно такими же, как и в FIFO-очереди. Что же поменяется? Посмотрим на пример работы такой очереди, он показан на рис. 7.11. Мы видим, что вместо целенаправленного движения к оператору клиенты могут то приближаться к нему, то отдаляться. Время ожидания для самого последнего клиента существенно удлиняется, однако, пока он ждет, через оператора проходит много вновь поступающих клиентов, которые обрабатываются почти мгновенно. В среднем же мы получаем примерно такое же время ожидания, как для «нормальной» очереди. Но мы уже много раз убеждались в том, что среднее значение не может характеризовать случайную величину в полной мере.

Рис. 7.11. Динамика FILO-очереди или стопки документов, которые при поступлении кладутся наверх и обрабатываются начиная сверху. Как и прежде, темные точки соответствуют каждому седьмому клиенту

Глядя на динамику FILO-очереди, легко понять, что время ожидания клиента должно быть близким к времени занятости оператора. Действительно, время занятости определяется как период от момента прихода первого клиента до момента выхода последнего, но в стеке первый клиент и оказывается последним. Нужно еще учесть, что очередной клиент не прерывает оператора, поэтому ко времени его ожидания добавится время обслуживания клиента, с которым уже работает сотрудник. Если оно распределено экспоненциально, то, как уже обсуждалось в связи со временем ожидания автобуса, добавочное время будет распределено точно так же. В итоге время ожидания окажется распределено как сумма времени занятости оператора и периода работы с одним клиентом. На рисунке 7.12 показаны распределения времени ожидания для M/M/1-очередей: обыкновенной, с политикой FIFO, придерживающейся правила FILO. В обоих случаях λ = 30 и μ = 34 человека в час.

Рис. 7.12. Распределения времени ожидания для M/M/1-очередей с различной политикой

Распределения сильно различаются, но средние значения у них практически одинаковые. Хотя распределение времени ожидания для FILO-очереди кажется сконцентрированным около моды (близкой к 1/μ, времени работы с одним клиентом), у него длинный тяжелый хвост, который сильно увеличивает дисперсию и повышает среднее значение. Медиана этого распределения равна 3 минутам. Это значит, что в половине случаев клиент будет ждать немного, но если уж застрянет, так застрянет: 5 % клиентов потратят больше часа, а самые невезучие 2 % вместо 2 минут вынуждены будут ждать своей очереди больше 2 часов! Для FIFO-очереди с такими же параметрами вероятность застрять на 2 часа составляет не более 0,04 %.

При этом оператор, то есть бюрократ, обрабатывающий бумаги, не заметит разницы между очередью и стеком: распределение его времени занятости не изменится. Руководитель бюрократа тоже увидит, что из кабинета подчиненного бумаги выходят с нормальной интенсивностью в силу устойчивости очереди. И большинство документов даже окажутся обработаны очень оперативно. Но то и дело какая-то их часть внезапно «проваливается» на дно стопки и задерживается там очень надолго. Такие дела приходится «двигать вручную» тем, кто в них заинтересован.

Подобная картина наблюдается и в шкафу, куда мы складываем вещи с мыслью разобрать потом. Но мы задвигаем то, что уже лежит там, поглубже и добавляем новые вещи. Так что даже если мы и станем их постепенно разбирать, до «ископаемых» у самой стенки руки дойдут очень и очень нескоро.

Для демонстрации несправедливости распределения времени между различными делами в ведомстве бюрократа (или вещами в шкафу) изобразим кривые Лоренца для FIFO- и FILO-очередей, описываемых формулой M/M/1. Если для всех FIFO-очередей кривая Лоренца одинакова, несправедливость FILO-очередей зависит от соотношения λ и μ. Чем ближе их отношение к единице, тем ближе к ней и индекс Джини. На рисунке 7.13 показаны кривые Лоренца для этих двух типов очередей с теми же параметрами, что и для предыдущего рисунка.

Рис. 7.13. Кривые Лоренца для времени ожидания в двух типах очередей. Коэффициент Джини для FIFO-очереди равен 0,5, а для FILO-очереди — 0,78

Закон сохранения клиентов, или равенство входного и выходного потоков, может сыграть еще одну злую шутку. Представьте себе контору, через которую проходит за рабочий день, скажем, 15 человек; при этом на каждого клиента в среднем уходит полчаса. В конторе два клерка, один трудится с интенсивностью 16 человек в день, а второй — 14. Вместе они могли бы обслужить человек тридцать, но, кажется, столько и не нужно. Люди в такой конторе почти не ждут своей очереди, среднее время ожидания составляет 18 минут, средняя длина очереди всего 1,2 человека[30]. Очень часто бывает так, что, пока с клиентом работает кто-то из клерков, второй в это время отдыхает. На рисунке 7.14 показан пример динамики очереди в конторе. При этом надо иметь в виду, что этот незначительный поток распределен между двумя операторами: каждый из них наблюдает поток, еще в два раза менее интенсивный. Про такую работу говорят: «не бей лежачего».

Рис. 7.14. Две недели в конторе с двумя клерками

Руководство, проведя все эти замеры и наблюдения, решает, что клерки живут уж больно вольготно, трудясь только половину рабочего времени, и в стремлении оптимизировать работу учреждения увольняет нерасторопного клерка. И вот все стало совсем иначе! Система приблизилась к опасному состоянию, когда μ≈λ. При таких условиях очередь становится метастабильной: она может какое-то время вести себя «хорошо», а потом внезапно наступит коллапс (рис. 7.15).

Рис. 7.15. В течение недели один клерк вполне справлялся с объемом работ, но потом все превратилось в кошмар

При λ = 15 и μ = 16 средняя длина очереди будет как раз равна 15 клиентам, а среднее время занятости оператора составит 1 день. Руководство может быть довольно своей оптимизацией. Но мы-то знаем, что средние показатели не показывают толком почти ничего. Посмотрите, с какой вероятностью время занятости клерка превысит указанное количество дней (рис. 7.16).

Рис. 7.16. Вероятность для одного клерка не уложиться с текущими делами в указанный период времени

Что еще хуже, среднее время ожидания одного клиента вырастает тоже до одного дня! Вместо 18 минут он застрянет со своим делом на час с вероятностью 88 %, вероятность проторчать в конторе полдня составит 60 %, а ухлопать на это весь день — 37 %. Таким образом, вроде бы разумное решение может иметь неожиданно неприятные последствия.