Продолжаем исследовать законы подлости вместе с теорией вероятностей и прочей другой математикой. В этой серии статей я привожу выдержки из своей книжки Вероятности и неприятности.
* * *
Я размышляю о законах подлости, стоя в аэропорту в очереди на регистрацию пассажиров и оформление багажа. Хвост длинный, люди разные и заметные со всеми своими сумками, детьми или клетками. Сзади слышу ворчание: «Как обычно, наша очередь тормозит. Вон, гляди, тот усатый в кепке наравне с нами стоял, а теперь вон где… Вот ведь закон подлости!» Этот закон зовётся наблюдением Этторе:
Соседняя очередь всегда движется быстрее.
Что же это — психологический эффект или причуды математики?
Ещё раз про пуассоновский процесс
Мы уже достаточно знаем о случайных процессах, чтобы немного проанализировать очередь, в которой стоим. За неимением других данных, разумно предположить, что выход из неё происходит по-пуассоновски: пассажиры подходят к стойке регистрации и проводят там какое-то время, не зависящее от времени обработки данных других пассажиров. Перемещение наблюдателя, стоящего в очереди, будет иметь вид монотонно изменяющейся ступенчатой линии, с одинаковыми шагами через случайные промежутки времени, подчинённые экспоненциальному распределению. Пара реализаций примеров пуассоновских процессов с одинаковой интенсивностью приведена на рисунке.
Обычно пуассоновский процесс накапливает события, и его изображение выглядит как «лесенка», растущая со временем. Но, стоя в очереди, мы заинтересованы в её скорейшем уменьшении, так что шаги нашего процесса ведут вниз.
Разница двух одинаковых пуассоновских процессов — а именно её наблюдает человек, скучающий в хвосте и исследующий соседнюю очередь, — представляет собой своеобразное случайное блуждание. В описанном нами случае величина отставания одной очереди от другой подчиняется распределению Скеллама. Для двух одинаковых очередей, пропускающих μ человек в единицу времени, вероятность отставания одной из них на k шагов равна:
где Iₖ(x) — встречавшаяся нам в предыдущей главе модифицированная функция Бесселя. Она возникла здесь не из-за круговой симметрии, а как результат сложения двух случайных величин, подчиняющихся распределению Пуассона.
Распределение Скеллама имеет симметричный колоколообразный вид, практически не отличимый от биномиального распределения. А раз так, мы уже готовы сделать некоторые качественные выводы, основываясь на опыте, полученном в предыдущей главе.
Во-первых, расстояние между одновременно вставшими в одинаковые очереди людьми будет то увеличиваться, то уменьшаться, при этом станут образовываться характерные волны с постоянно меняющейся длительностью. Во-вторых, из-за самоподобия случайного блуждания длительность меандров — как для коротких очередей, так и для длинных — окажется соизмеримой со временем стояния в очереди, и, значит, они будут заметны. А волны — уже повод для недовольства. В-третьих, заранее неизвестно, какая очередь пройдёт быстрее, ведь случайное блуждание равновероятно уходит как вверх, так и вниз. И наконец, четвёртое заключение: очереди движутся независимо, то и дело опережая и нагоняя друг друга, но в среднем одинаково, и ожидаемая разница между ними стремится к нулю, однако разброс вокруг среднего со временем растёт пропорционально квадратному корню из времени.
Выходит, нет никаких подлых штучек злодейки-судьбы, а есть только честное случайное блуждание. Правда, если нам не повезло и мы оказались во временно отстающей очереди, то мы в ней проведём больше времени и, согласно закону велосипедиста, у нас будет больше возможностей посетовать на судьбу! А теперь, внимание, хорошие новости: в любой выбранный интервал времени тех, кому повезёт попасть в быструю очередь, будет больше, чем невезунчиков, ведь быстрая очередь может пропустить больше людей! Но, увы, это ничуть не утешит того, кто надолго застрял в хвосте.
Теория для заскучавших в коридоре
Тем и хороша математика, что она способна сделать увлекательным даже стояние в очереди. Например, можно прикинуть, сколько ещё ждать своей очереди, но для этого, как ни странно, надо посмотреть не вперёд, а назад, на растущий хвост. Если подождать какое-то время, скажем 10 минут, и посчитать, сколько человек выстроилось за вами, то, разделив количество людей перед вами на полученное число, вы вычислите среднее время ожидания в десятках минут. Например, пусть за десять минут хвост вырос на пять человек; если в момент подсчёта перед вами семь человек, то ожидаемое время ожидания составит 10 × 7/5 = 14 минут. Понятно, что эта оценка будет весьма грубой, но любопытно, что она действительно соответствует среднему времени ожидания. Об этом говорит теорема Литтла — один из самых ранних и самых общих результатов теории очередей, известной в России как теория массового обслуживания.
Теория очередей появилась в самом начале XX века, с первых работ датского математика Агнера Эрланга (1878–1929), который занимался зарождающейся областью телекоммуникаций. За сотню лет результаты исследований Эрланга прочно вошли в нашу жизнь — настолько, что возникает ощущение, будто это мы вошли в мир телекоммуникаций. Несколько позже большой вклад в развитие этой науки внёс советский математик Александр Яковлевич Хинчин (1894–1959), который вместе с Андреем Николаевичем Колмогоровым (1903–1987) заложил основы современной теории вероятностей. Результаты теории массового обслуживания важны для проектирования магазинов и залов ожидания, оптимального управления операционной системой компьютера и операционным залом банка, для грамотной разработки бюрократической машины, управления дорожной сетью и в оценке рисков страховой компании. В очередях могут стоять люди (покупатели, клиенты, пассажиры), автотранспорт и грузы, задачи и документы; а обрабатывать их — кассиры, операторы, регистраторы, серверы и бюрократы. Чтобы не путаться и не утопать в деталях, будем называть стоящих в очереди клиентами, а того, кто их обслуживает, — оператором.
Представьте себе очередь, в которую люди встают согласно некоторому распределению временных интервалов pᵢₙ(t) со средним значением 1/λ. Время, которое оператор тратит на работу с клиентами, подчинено распределению pₒᵤₜ(t) со средним значением 1/μ. На рисунке показана очередь, в которой ожидают два клиента под номерами 1 и 2, один с номером 0 обслуживается, а клиент номер 3 готов в неё встать.
Её можно описать как марковский процесс в котором состояние определяется длиной очереди: состояние 0 — в очереди никого, состояние 1 — один клиент, состояние 2 — два клиента и т. д. В идеальном мире ничто не запрещает очереди стать сколь угодно длинной; значит, мы получаем цепь с бесконечным числом состояний, и для анализа очереди придётся иметь дело с матрицей переходов, содержащей бесконечное число строк и столбцов. В предыдущей главе мы уже имели дело с марковскими процессами, и для анализа стационарного состояния цепи нам понадобилось возводить матрицу переходов в бесконечную степень. Так что же, надо вычислить бесконечную матрицу, возведённую в бесконечную степень?
Математиков эта задача не испугала, и уже в 1930-е были придуманы методы для таких вычислений. Результатом анализа будут свойства стационарного состояния очереди. Оно не меняется со временем, но все параметры очереди, такие как длина или время ожидания в ней, — случайные величины. Они могут постоянно меняться, но при этом всегда остаются в рамках каких-то распределений, от времени не зависящих. И чего только не придумаешь, скучая в зале ожидания!
Свойства очереди сильно зависят от соотношения λ и μ. Если λ > μ, хвост будет расти неограниченно, как пробка на дороге, в которую въезжает больше автомобилей, чем может выехать. Она попросту перекрывает поток клиентов, накапливая их в себе. Для λ < μ очередь устойчива. Она может расти или уменьшаться по мере того, как клиенты добавляются и выходят из неё, но клиенты в ней не накапливаются неограниченно: сколько их вошло в зону ожидания, столько же выйдет. Иными словами, устойчивая очередь может затормозить тех, кто в ней стоит, но неспособна изменить интенсивность потока людей, проходящих сквозь неё. И если на входе мы имеем в среднем λ человек в единицу времени, то и на выходе должны получить такой же поток, независимо от скорости работы оператора. Случай λ ≈ μ рассматривается отдельно. Такая метастабильная очередь ведёт себя неустойчиво и моделируется процессом случайного блуждания — с той только разницей, что длина очереди не может быть отрицательной. У блуждающей таким образом системы есть непроницаемая стенка снизу, которая, однако, не мешает практически неограниченному росту длины очереди. И хотя рано или поздно она сократится и даже исчезнет, отклонения времени ожидания и времени работы оператора от среднего будут столь велики, что счесть такое обслуживание удовлетворительным никак не получится. Далее мы будем рассматривать только устойчивые очереди.
От характера распределений pᵢₙ(t) и pₒᵤₜ(t) зависят динамика очереди и её характеристики, такие как распределение для её длины, времени ожидания клиентом и времени занятости оператора. Для очередей создана система обозначений, называемая нотацией Кендалла. Например, простая очередь, в которую люди входят равномерно и так же уходят, как, например, в аэропорту при посадке на рейс, обозначается D/D/1 (буква D здесь обозначает детерминированный процесс, соответствующий вырожденному распределению, а единица — одного оператора). Въезд и выезд автомашин на территорию аэропорта через три автоматических шлагбаума можно описать очередью M/D/3. Буквой M обозначается пуассоновский (марковский) процесс, то есть случайный процесс без памяти. В очередь на регистрацию билетов и оформление багажа новые люди приходят по-пуассоновски, и багаж у всех разный, так что клиенты будут выходить из очереди тоже по-пуассоновски. Для пяти стоек такая очередь обозначается M/M/5. Собственные обозначения существуют и для других видов распределений. Если же мы вообще ничего не знаем о распределении появления клиентов или методах их обслуживания, то обозначаем такой произвольный процесс буквой G (от слова General — общий).
В этой главе мы будем исследовать неприятности и неожиданности, наблюдаемые в очередях, на примере очереди с λ = 30 чел./ч и μ = 34 чел./ч. В среднем новые клиенты будут поступать в нее с интервалом в 2 минуты, а обрабатываться оператором примерно за 1 минуту 45 секунд. Это похоже на очередь у стойки регистрации в аэропорту. На рисунке показан пример того, как могут «жить» M/D/1- и M/M/1-очереди с такими параметрами.
В стационарном состоянии длина M/M/1-очереди n описывается геометрическим распределением:
Зная это распределение, можно вычислить ожидаемую длину очереди:
Для нашего примера средняя длина очереди составит 7,5 человек. Время обслуживания клиента (сумма времени ожидания своей очереди и собственно времени работы с оператором) в M/M/1-очереди описывается экспоненциальным распределением с параметром μ – λ. Это приводит к значению среднего времени ожидания
Среднее время работы с каждым клиентом не превышает 2 минут, однако среднее время ожидания для нашего примера равно 15 минутам. Как видно, для стационарной M/M/1-очереди выполняется равенство:
Это и есть формула Литтла, которой мы воспользовались, стоя в очереди и от нечего делать занявшись подсчётами. Будучи очень простой, формула на удивление сильна: она выполняется для очень широкого класса очередей и в самых разных задачах. То, что в формулу Литтла входит только λ, а не μ, отражает основное свойство стабильной (устойчивой) очереди: она может задерживать клиентов, но не меняет их поток, который определяется значением λ. И даже если скорость работы оператора μ будет очень велика, среднее время ожидания все равно определяется входным потоком и уже скопившимся числом клиентов. А поскольку для устойчивых очередей λ < μ, мы получаем ещё один закон подлости:
Даже с идеальным кассиром время стояния в очереди в кассу определяет самый бестолковый покупатель.
Важная характеристика очереди — время занятости оператора, или длительность непрерывных периодов времени, в которые он обслуживает клиентов. Обозначим это время B. Периоды занятости перемежаются периодами простоя, когда по какой-то причине клиентов в очереди не оказывается. Клиенты приходят, ждут и уходят, а оператор остается работать, поэтому разумно предположить, что B > W. В действительности ожидаемое, среднее время занятости для M/M/1‑очередей равно среднему времени ожидания, то есть B = W. Уже не вполне интуитивно понятный результат, но и это ещё не всё: при той же интенсивности труда среднее время обслуживания клиента может стать существенно больше среднего времени работы оператора! Вот это уже кажется парадоксом. Получается, оператор в среднем умудряется работать меньше, чем в среднем же обслуживается клиент!
Как мы уже говорили, средние значения надо использовать осторожно. Объяснить этот парадокс и понять, что происходит в очереди, можно, привлекая дисперсию распределения времени обслуживания одного клиента pₒᵤₜ(t). Ещё в 1930-е австрийскому математику Феликсу Поллачеку удалось в общем виде вычислить отношение W/B для произвольной M/G/1-очереди:
Здесь σ — дисперсия распределения pₒᵤₜ(t). В случае M/M/1-очереди σ = 1/μ, и это отношение равно 1. Но может случиться, что при том же значении среднего распределение pₒᵤₜ(t) будет иметь бóльшую дисперсию, и тогда W окажется больше B. На рисунке показан пример, в котором pᵢₙ(t) распределено экспоненциально с λ = 30 чел./ч, а pₒᵤₜ(t) описывается гамма-распределением, соответствующим интенсивности μ = 34 чел./ч с дисперсией σ = 2/μ.
Очередь остаётся стабильной, поскольку λ < μ и клиенты в среднем обслуживаются быстрее, чем приходят новые. Оператор работает хорошо: большинство клиентов обслуживаются очень быстро; но обратите внимание на долю «трудных» клиентов, которые формируют достаточно толстый хвост распределения. Их мало, но каждый отнимает много времени, и все в очереди вынуждены их ждать. Для примера, приведённого на рисунке, среднее время ожидания оказалось равно 35 минутам, хотя среднее время занятости оператора прежнее (15 минут). Получается, что, не переставая работать, оператор в среднем филонит, пока мы страдаем в очереди от безделья!
Динамика такой очереди отличается от динамики M/M/1. Для неё характерен несимметричный пилообразный рисунок с плавной восходящей линией и резким сбросом. Пока оператор занят «трудным» клиентом, постепенно вырастает длинный хвост, а потом, освободившись, оператор очень быстро с ним справляется
* * *
Продолжение темы очередей в следующих статьях.