Теория массового обслуживания в действии, плюс лягушки

Ну, это был прекрасный отпуск. Начался он плохо, но затем значительно улучшился.

Предположим, у вас есть «вход», который поставляет некоторое большое количество «потребителей» по некоторому расписанию. У вас есть несколько «служащих», которые обрабатывают запросы потребителей. Как только запрос потребителя выполнен, потребитель выходит через «выход». Что происходит, когда подряд приходят больше потребителей, чем у вас есть служащих, готовых их обслужить? Это область аналитической теории массового обслуживания; эта теория лежит в основе огромного количества человеческих и технических задач, от получения двойного чизбургера с луковыми кольцами и большим… оранжевым… напитком… до маршрутизации телефонных звонков в спутниковых сетях.

(Некоторым из вас, возможно, любопытно, какое отношение первые два абзаца имеют друг к другу. Скоро всё сойдётся, обещаю.)

Интересный пример двух разных алгоритмов обслуживания очередей предоставлен двумя популярными сетями ресторанов быстрого питания. В ресторане «M», если, там, к примеру, четыре кассира, то будет четыре очереди. Посетитель приходит, выбирает очередь и ждёт. В ресторане «W» есть одна длинная змеистая очередь; когда освобождается кассир, человек в голове этой очереди идёт к этому кассиру.

Принципиальный недостаток системы W – в том, что та единственная очередь выглядит так, что стоять в ней намного дольше, чем в четырёх коротких очередях в системе M, что может отпугивать. Но практически по любой уместной объективной метрике, практически по любому уместному социальному фактору, и практически в каждом типичном бизнес-сценарии реального мира система W является предпочтительной:

• Система W не требует от потребителя принимать решение на основе неполной информации; система M в своей основе предлагает потребителю играть в рулетку. Какая очередь быстрее всех? Это зависит не только от компетентности кассира, но и от того, просты или сложны транзакции, ожидающие в данной очереди.
• Предположим, вы в системе M и две очереди – ваша, и та, что рядом – обслуживаются примерно с одинаковой средней скоростью. Вполне возможно, и быть может, даже естественно, что, несмотря на одинаковую скорость движения , что в связи с внезапными движениями и остановками в обеих очередях вам будет казаться, что люди рядом с вами «обгоняют» вас чаще, чем вы «обгоняете» их. Весьма возможно, что люди в обеих очередях будут иметь это ощущение одновременно! Каждый чувствует, что выбрал неправильную очередь, даже если в среднем нет «неправильной очереди». В системе W есть только одна очередь, так что она правильная автоматически.
• Система W – честная; потребитель, ждавший дольше всех, всегда обслуживается следующим. Система M – нечестная; потребитель, попавший в «быструю» очередь может обслужиться до того, как потребители в «медленной» очереди, где они ждут окончания сложной продолжительной транзакции (или, хуже, ждут потребителя, который достиг головы очереди до того, как решил, что заказать).
• Система W в теории имеет более высокую пропускную способность; единственный случай, когда потребитель с быстрой транзакцией вынужден долго ждать в голове очереди – это та маловероятная ситуация,что все кассиры оказались заняты сложными транзакциями. Если любой кассир сейчас обслуживает быстрые транзакции, то он быстро опустошает голову очереди. В системе M, много быстрых транзакций могут быть задержаны единственноймедленной. Это сильно снижает среднюю пропускную способность.
• Система W намного гибче. Новых кассиров можно динамически добавлять, когда очередь становится слишком длинной, и отправлять заниматься менее тяжёлой работой, когда она укорачивается. В системе M, когда новый кассир включается в работу, может случиться неорганизованная спешка для формирования новой очереди; потребителей заставляют снова принять решение – попробовать ли новую очередь или остаться в старой, и это предоставляет новые возможности для кажущейся нечестности. Но, хуже, когда кассир в системе M уходит, то что происходит с его очередью?

Именно важность последнего вопроса была подчёркнута для меня в первый день моего отпуска. Назовём мою авиакомпанию «D». Оформление багажа пассажиров авиакомпании D в Международном Аэропорту Сиэтл-Такома работает по модели массового обслуживания “M”. Вы регистрируетесь в одном из киосков, печатаете посадочные талоны, платите ваши пятнадцать долларов за оформление чемодана, и выбираете одну из примерно десяти очередей.

Ну, как минимум в теории D устранила одну из проблем модели M; последнее, что говорит вам система регистрации – это в какую очередь вставать. Я не знаю, как именно эта система решает, какая из очередей лучше, или читает ли хоть кто-то эти сообщения. Это малозаметная штука; лично я не ожидал, что система выдаст мне эту информацию, так что мне легко представить, что кто-то может полностью её пропустить и по-старинке выбрать любую очередь.

Но так или иначе, мы стоим в нашей назначенной очереди и она потихоньку движется. Нам не слишком важно, сколько времени это занимает, потому что наш рейс задержали, предположительно, на один час, в связи с «непредвиденной технической проблемой». Так что у нас полно времени. (Как выяснилось, в действительности у нас было более трёх часов дополнительного времени. Я не против. Авиамеханики, которые это читают: пожалуйста, тратьте столько времени, сколько вам нужно, чтобы гарантировать, что крылья не отвалятся.) И, пока мы ждём, я указываю на кое-что своей жене: лента конвеера, которая должна увозить багаж, не движется. Или, скорее, движется – примерно на один чемодан в минуту – резко стартуя и останавливаясь через секунду. Багаж, конечно же, поставляется из очередей намного, намного быстрее этого, так что формируется целая куча из него. Большинству «служащих» не нужно ходить туда-сюда, но несколько человек ходят позади стоек регистрации, и довольно забавно наблюдать за тем, как им приходится маневрировать вокруг всё более высоких штабелей багажа, сложенных возле уже забитого конвеера.

Ли сообщает мне, что её друг C раньше был грузчиком в авиакомпании D, но недавно его уволили. «О, должно быть, рецессия и сокращение авиаперевозок привели к уменьшению человекочасов?» - спрашиваю я. Нет, оказывается, C заявляет, что у них было полно работы, но шаткое финансовое положение авиакомпании заставило их увольнять персонал и перегружать работой оставшихся грузчиков.

Так или иначе, мы достигаем головы очереди и я смотрю вперёд, пытаясь вступить в визуальный контакт с представителем Авиакомпании D, стоящей прямо передо мной. Она упорно смотрит на пол и громко говорит приблизительно в направлении представителя, обслуживающего соседнюю очередь «мне нужно уйти». Что она и делает, продолжая смотреть в пол. Другие представители, все занятые обслуживанием других пассажиров, не реагируют на эту новость. Возможно, они её не услышали. Или, они могли проинтерпретировать это просто как информацию – как это и было сформулировано – а не как просьбу кому-нибудь заняться покинутой очередью.

У меня масса времени на ожидание. Этим я и занимаюсь. Я продолжаю пытаться посмотреть в глаза одному из представителей, обслуживающих очереди с обеих сторон от меня, но они либо смотрят на человека, которого обслуживают, либо с отчаяньем смотрят на растущие башни багажа, теперь уже полностью окружающие неподвижную ленту конвеера. Мне интересно, трудно ли не замечать человека менее чем в двух метрах от себя, который безотрывно смотрит на вас с выжидательной улыбкой несколько минут подряд. Похоже, авиакомпания D хорошо обучает этому свой персонал, думаю я.

Минуты продолжают идти. Очередь позади меня продолжает расти. Я раздумываю над тем, что это не просто ошибка персонала, но и ошибка применения основных результатов теории массового обслуживания, в которой вы ожидаете от любой авиакомпании хороших знаний. Я понимаю, что у меня где-то здесь есть статья в блоге, что меня радует. Я понимаю, что теперь я думаю о работе, будучи в отпуске, что меня раздражает. Так что, в целом, это ничья.

Примерно через пять минут всего этого, путешественница позади меня вежливо трогает меня за плечо и спрашивает «Вы тоже летите в Мичиган, так ведь? Я стою в той очереди?»

Я поворачиваюсь вполоборота к ней, вполоборота к тому сотруднику авиакомпании D, который так успешно игнорирует меня и пару дюжин людей позади меня. «Мадам,» говорю я, «посмотрите на картину в целом. Вы стоите в очереди, в конце которой некому поставить ваши чемоданы на конвеер, который не движется. Большинство грузчиков, которые должны снимать ваши чемоданы с конвеера, были уволены, и даже если бы там были грузчики, самолёт не может лететь, и вероятно его ещё даже нет в этом аэропорту. Мы с вами явно ошиблись не очередью, мы ошиблись авиакомпанией. »

Что удивительно, вышеупомянутый представитель мгновенно начинает обслуживать нашу очередь.

Хотя никак не признав того, что тут была хоть какая-то проблема, к его чести он был вежлив, выглядел достаточно компетентным в приёме моего чемодана, и добавил чемодан к башне. Когда мы уходили, я оглянулся и увидел парня обслуживающим обе очереди; эти очереди теперь продвигались с половинной скоростью, что, по моему мнению, лучше, чем ничего, хотя могу себе представить, что люди, выбравшие любую их них были менее чем в восторге. Самолёт наконец долетел, и мы в итоге получили чемодан, так что в конце концов всё сработало.

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

После того всё значительно улучшилось. Примеры того, что я видел в отпуске:

• Юпитер в противостояни
• Ганимед
• метеоритный дождь из Персеид
• форель
• лягушек
• жаб
• головастиков
• черепах
• грифов-индеек
• ласточек
• колибри
• крохалей
• гагар
• больших голубых цапель
• какую-то хищную птицу, которую я видел на фоне солнца, так что не смог точно разглядеть, но подозреваю, что это была скопа
• бурундуков
• кроликов
• плакучую берёзу
• львиный зев
• ярко-зелёных стрекоз
• овцу
• петухов
• фоссилизированные ракушки
• подозрительно повреждённые деревянные байдарочные вёсла: это свидетельство активности бобровых акул. Но как они проникли зимой в мой склад с байдаркой? Неужели бобровые акулы – амфибии?
• мою семью
• старых друзей

Полёт домой – где оформление багажа было устроено по модели W – прошёл без происшествий.

Так что, вернёмся к дальнейшим невероятным приключениям в коде. Надеюсь, вам понравились мои законсервированные статьи, которые я заготовил перед отпуском.

В следующем выпуске: еще одно дополнение про блоки итераторов.