Дилемма парикмахера и приоритеты

В очереди в магазине стоят пять человек, делаю­щих приблизительно равными покупки. При этом их обслуживание продавцом занимает приблизительно равное время, скажем 6 мин на каждого. Дверь в торговый зал открывается, и входит молодой человек, пришедший купить сигареты. Его обслуживание за­нимает 30 с. Молодой человек, пришедший за сига­ретами, становится в общую очередь. Посмотрим, как развертываются события, начиная с этого момен­та. Продавец начинает обслуживание первого стоя­щего в очереди клиента, и время его ожидания рав­но нулю. Второй клиент ждет 6 мин, третий— 12 мин, четвертый—18 мин, пятый—24 мин, и молодой человек, пришедший за сигаретами,— полчаса. Суммарное время, которое все покупатели провели в очереди, равно полутора часам, В среднем по

121

 

15 мин на человека. Запомним эту цифру. Теперь предположим, что молодой человек купил свои сига­реты без очереди. Тогда он, вместо получасового стояния в очереди, не затратил никакого времени на ожидание. А последовательность времен ожидания людей, стоявших до его прихода в очереди, имеет вид 0,5; 6,5; 12,5; 18,5; 24,5 мин. При этом полное время ожидания равно 62,5 мин, а среднее время ожидания равно 10,4 мин, т. е. уменьшилось почти в полтора раза. Средняя длина очереди за рассмат­риваемый отрезок времени изменилась с 2,4 до 2.

Конечно, приведенное рассуждение лишь прибли­зительно отражает картину, так как в нашем приме­ре поступление клиентов прекратилось с момента прихода молодого человека за сигаретами. Однако наш пример поясняет механизм, который обеспечи­вает снижение средней длины очереди и среднего времени ожидания обслуживания в том случае, когда быстро обслуживаемым клиентам в очереди назначается приоритет. Оказывается, что Остап Бендер был прав, требуя чтобы его пропустили без оче­реди, так как ему «только справку».

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

Если трудно представить себе побудительные мо­тивы, которые могли бы сформировать систему при­оритетов в очереди, то следует подумать, как такую систему могут навязать очереди каналы обслужива­ния. Для этого, однако, необходимо внести в правила взаимодействия клиентов и каналов право каналов назначать приоритеты или, что равнозначно, право выбирать из очереди клиентов га обслуживание.

Теперь из магазина мы перейдем в парик­махерскую, в которой работают несколько равноцен­ных мастеров (система с несколькими равноценными каналами обслуживания). В парикмахерскую прихо­дит несколько категорий клиентов, отличающихся друг от друга временем обслуживания — клиенты, желающие только побриться, клиенты, желающий сделать простую или фасонную стрижку, клиенты,

128

Желающие постричься, побриться и сделать массаж лица и т. п. Как мы уже отметили, для уменьшения средней длины очереди имеет смысл пропустить без очереди тех, кто обслуживается быстро. Если времена обслуживания клиентов известны заранее, то на этом основании в парикмахерской может быть вы­вешен список приоритетов, составленный по принципу «короче обслуживаешься — раньше обслужива­ешься». В этой ситуации опять же заявление Остапа «мне только справку» может служить достаточным основанием для нарушения очереди (дополнитель­ное заявление о не снятых калошах находится вне нашей модели). Список приоритетов может быть достаточно простым. Например, «бреем без очереди!»

Сложнее обстоит дело, когда времена обслужи­вания заранее неизвестны, могут быть случайными величинами и, вообще говоря, могут изменяться во времени. В этом случае мы должны формировать так называемые динамические приоритеты в процес­се функционирования системы. В рамках интересую­щего нас подхода система приоритетов должна по­рождаться коллективным поведением каналов об­служивания.

Для организации коллективного поведения нам необходимо так сформулировать в этой задаче ин­дивидуальные предпочтения, чтобы, добиваясь мак­симального удовлетворения индивидуальных потреб­ностей для совокупности клиентов, достигать и тре­буемый общесистемный эффект. Как мы уже от­мечали, трудно предложить правдоподобные крите­рии, делающие для клиента предпочтительным уве­личение времени пребывания в очереди. А вот для канала обслуживания такие критерии можно пред­ложить сравнительно легко.

Допустим (и это допущение достаточно естествен­но) , что парикмахер стремится к максимизации сво­его заработка. Тогда, если с точки зрения парик­махера клиент, обслуживаемый быстро, будет выгод­нее клиента, обслуживаемого долго, то парикмахер будет изыскивать способы протащить такого клиента без очереди. Ситуация, в которой освободившийся парикмахер берет из очереди своего постоянного клиента, если последний ему достаточно выгоден, знакома многим. В ряде случаев такое дейст­вие вызывает возмущение очереди, но мы уже выше

123

Договорились узаконить право парикмахера иметь

любимчиков». Перед обращением за очередным кли­ентом паракмахер может объявить, например, что сту­дентов он обслуживает вне очереди. Но, как мы уже отметили, клиент, обслуживаемый быстро, должен быть выгоден для парикмахера. Этого можно добить­ся, введя постоянную плату за обслуживание. Вооб­ще говоря, постоянная плата за обслуживание может привести к росту времени обслуживания — «Раз уж я заплатил деньги, то почему бы не обслужиться по полному кругу»: поэтому можно, как в такси, ввести «плату за посадку», не зависящую от времени об­служивания.

Мы начали с того, что в качестве системы обслу­живания могут выступать системы самой различной природы, а не только системы, в которых клиентами и каналами служат люди. В' качестве системы обслу­живания могут выступать самые разнообразные тех­нические системы: системы связи, вычислительные машины, транспортные системы (например, система транспортерных лент, питающих углем бункеры ТЭЦ) и многое другое. Поэтому, изучая поведение каналов и клиентов в таких системах, мы будем стремиться формализовать их поведение. Формализо­вать так, чтобы его можно было реализовать доста­точно простыми техническими средствами. Такой подход, кроме всего прочего, поможет нам строить и изучать модели организации коллективного поведе­ния в системах обслуживания. Если же в реальном мире локальные задачи будут решаться более тон­кими и «разумными» средствами, то тем лучше для системы. Однако для наглядности изложения мы на некоторое время сохраним терминологию парик­махерской.

Разделим всех клиентов на несколько типов. Каждый тип клиентов требует времени обслужива­ния, лежащего в некотором своем интервале. Каждо­му типу клиентов присвоим номер, одинаковый для всех клиентов данного типа, и назовем его номером клиента. Все клиенты, независимо от их номера, вносят до поступления в канал обслуживания одну и ту же плату. Пусть эта плата состоит из К одина­ковых монет, которые парикмахер кладет в копилку. После обслуживания, длившегося Т единиц времени, парикмахер вынимает из копилки Т монет. Если

124

К=<Т, то в копилке ничего не остается и клиент не фиксируется. Если же К > Т, то в копилке остается (К—Т) монет и парикмахер вешает на копилку номер клиента. Клиент, номер которого висит на ко­пилке, в следующий раз имеет право на обслужива­ние без очереди. Если К равно среднему по всей системе времени обслуживания, то приоритет полу­чат клиенты, длительность обслуживания которых меньше, чем среднее в системе. Если имеющий прио­ритет клиент вновь придет на обслуживание, внесен­ная им плата добавится к остатку, находящемуся в обозначенной его номером копилке. Таким образом, за достаточный для этого отрезок времени, все кли­енты, время обслуживания которых меньше среднего, будут упорядочены по значениям содержимого копи­лок, т. е. по средним временам обслуживания, отне­сенным к частотам обслуживания клиентов. Действи­тельно, если клиенты типа А дают доход 1 руб и приходят 10 раз в день, то они безусловно выгод­нее клиентов типа Б, дающих доход 100 руб., но приходящих 1 раз в месяц. Если все типы клиентов упорядочены и имеют свои номера приоритетов, то для оптимизации длины очереди клиенты типа Б все равно должны иметь приоритет ниже, чем у кли­ентов типа А, хотя эффект от такого упорядочивания и невелик.

Приведенный способ формирования приоритетов мало чем отличается от набора в процессе функцио­нирования статистической информации о характери­стиках клиентов и решения на этом основании зада­чи об оптимальной системе приоритетов. Нас такое решение задачи не должно удовлетворять. Во-пер­вых, техническая сложность системы начинает зави­сеть от количества типов клиентов. Чем их больше, тем больше надо иметь копилок. Во-вторых, при та­кой постановке задача организации децентрализован­ного управления теряет содержательный смысл — на каждом канале обслуживания решается полная задача об оптимальной системе приоритетов. Попы­таемся упростить систему и, быть может, тем самым выявить некоторые новые привлекательные черты ее поведения.

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

125

 

В простейшем случае—двух. Теперь парикмахе­ру достаточно иметь всего две копилки. Но тогда двое первых оказавшихся выгодными клиентов захватят приоритет на этом канале и, следовательно, формирование системы приоритетов прекратится. Для того чтобы избежать возможности попадания в такие тупиковые состояния, организуем конкуренцию клиентов на канале. Если на обслуживание по­ступает клиент, не имеющий приоритета по этому каналу, содержимое копилок сравнивается между , собой и копилка, имеющая меньший запас, очищается и начинается работа с новым клиентом. Здесь естественно возникает вопрос о необходимом числе копилок. Их, как видно, должно быть не менее двух, но и не более числа типов клиентов. Исследование поведения таких систем показало, что увеличение числа копилок сверх двух приводит к незначительным изменениям качества функционирования, несоизмеримым с затратами на усложнение системы управления.

При построении такой системы возникает еще один вопрос. Если копилка захвачена клиентом, име­ющим сравнительно небольшое, но явно не минимальное среднее время обслуживания, и этот клиент сумеет накопить достаточно большую сумму в своей копилке, то очень мала вероятность того, что другие клиенты, используя оставшиеся копилки, сумеют превзойти его, хоть и медленно, но постоянно растущий запас. Если же, начиная с некоторого момента, клиент вообще перестал посещать парикмахерскую, то очень велика вероятность того, что на канале бу­дет удерживаться приоритет несуществующего клиента и опять-таки функционирование системы будет блокировано. Конечно, все эти трудности можно устранить повышением «интеллектуального уровня» правил формирования приоритетов. Но это уже назы­вается «пускаться во все тяжкие», а нас интересуют возможности формирования простейших правил взаи­модействия и алгоритмов оптимизации. Отсюда не следует, что если нам встретился умный парикмахер, то он должен зарыть свой талант в землю. Простей­шим выходом из создавшегося положения является ограничение объема копилки. Если копилка перепол­нится, то избыточные деньги сдаются в кассу. Оказывается, что введение такого ограничения улучшает

126

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

Здесь уместно вспомнить о существовании опти­мальной глубины памяти целесообразных автоматов при их поведении в переключающихся случайных средах. Аналогия здесь полная. Действительно, чем меньше емкость копилок, тем выше способность сис­темы к переучиванию, тем она подвижнее, лабильнее. Однако, чем меньше емкость копилок, тем труднее системе различать между собой выгодных клиентов, тем грубее она работает. Оптимальная емкость как раз и соответствует компромиссу между качеством решения и временем, необходимым для его нахож­дения.

Выработка приоритетов для каналов (причем разных для разных каналов) улучшает еще одно ка­чество системы — количество переключении. Пере­ключением мы называем переход от обслуживания клиентов одного типа к обслуживанию клиентов другого типа. Если подряд обслуживаются два кли­ента одного типа, то переключения не происходит. Легко понять, что если данный канал, и только он предоставляет приоритет некоторому типу клиентов, то подавляющее большинство клиентов такого типа поступает на обслуживание именно на этот канал, что уменьшает разнообразие типов клиентов на ка­нале и, как следствие, снижает частоту переключении.

Что дает системе снижение числа переключении? Во-первых, переключение всегда связано с потерями. Это либо расходы на переналадку оборудования, либо, как в случае систем связи, источник дополни­тельных помех, либо дополнительная потеря времени.

Во-вторых, снижение числа переключении приво­дит к специализации канала обслуживания, что, как правило, приводит к снижению времени обслужива­ния приоритетных клиентов.

Здесь мы коснулись вопроса, который несколько расширяет нашу модель. Очевидны случаи, когда один и тот же клиент на разных каналах имеет

127

разное время обслуживания и различные времена обслуживания имеют разные клиенты на одном и том же канале. В этом случае перераспределение клиен­тов по каналам будет изменять не только среднюю длину очереди, но и пропускную способность системы.

⇐ Предыдущая6789101112131415Следующая ⇒

Поделиться: