Full Text

Введение Становление микроэлектронно-информационного технологического уклада дает мощный толчок развитию общества услуг. Развитие сетей передачи данных на порядки расширяет количество обращающихся в существующие системы массового обслуживания (СМО) и создает предпосылки для образования новых. Но по-прежнему во многих случаях «узким местом» обслуживания является физическое исполнение заявок, связанное со взаимодействием людей, преобразованием или перемещением материальных ценностей и т.д. Поэтому образуется задержка, очередь. Обоснованное, успешное управление очередностью обслуживания осложняется рядом обстоятельств: 1) разнообразием услуг, к чему стремятся многие их поставщики; 2) разной значимостью заявок для СМО с точки зрения выживания в условиях рынка; 3) плохой предсказуемостью и глубоким непостоянством количества обращений, временами вынуждающими СМО работать в условиях перегрузки и отказывать заявкам. Множественность обращений требует глубокой автоматизации управления очередью, т.е. чтобы очередность обслуживания подавляющего числа части заявок определялась без участия человека. При этом хорошо, чтобы у представителя СМО сохранялась возможность вмешиваться в ход продвижения в очереди для отдельных заявок. Причем желательно, чтобы это вмешательство осуществлялось не грубо (по положению в очереди), а мягко (по скорости продвижения в очереди), т.е. без нарушения автоматизма работы очереди и с сохранением ее правил. Приведем некоторые черты облика отвлеченной СМО, для которой далее будет рассматриваться управление очередью. Предмет обращения таков, что постоянные пользователи повторно обращаются через приблизительно равные отрезки времени, но эта повторяемость может меняться по их собственному усмотрению. После двух-трех подряд отказов со стороны СМО (вследствие ее перегрузки) пользователь, вероятнее всего, прекращает обращаться к ней. Заявки большинства пользователей выполняются СМО за один и тот же небольшой отрезок времени, однако могут случаться разовые, весьма важные обращения с очень большой длительностью обслуживания, в том числе с временным перекрытием. Важность очередной поступившей заявки назначается внутри самой СМО. Учитываются: вид услуги (прибыльность), разряд обратившегося пользователя (разовый проездом, повторный, постоянный, недобросовестный), внеэкономические установки (обязанность по предоставлению льгот, задача привлечения определенных разрядов пользователей) и различные другие влияющие на выживание СМО в условиях рынка обстоятельства, данные для которых могут быть выяснены у пользователя при подаче заявки (подходы к назначению важностей заявкам находятся за рамками настоящего рассмотрения). Ключевым является рассмотрение работы СМО в условиях перегрузки, потому что при низкой нагрузке преимущества и недостатки различных видов управления очередью менее выражены, поэтому пригодны многие из них. В условиях нарастающей перегрузки, т.е. когда СМО начинает все чаще отказывать заявкам в исполнении, лучшим будет то управление очередью, при котором постепенная потеря пользователей услуг будет производиться с наименьшим ущербом для самой СМО. Причем это управление должно быть автоматическим и основываться на вычислительной обработке данных возросшего количества заявок с учетом всех выясненных различий. Перечисленные выше особенности работы сложной СМО в условиях перегрузки указывают, что для создания пространства поиска наилучшего управления очередью в распоряжении должно быть описание заявки, позволяющее учитывать, по возможности, больше сущностных показателей. Цель данного исследования - представить опыт разработки такого многостороннего и гибкого описания, а также пример управления очередью при его использовании. Мощный толчок к развитию теории массового обслуживания, достигшей к середине XX в. высокой степени математической зрелости [1], дали вычислительные системы, в которых обнаружились новые потребности и одновременно открылись широкие возможности по управлению различными видами очередей. Чаще всего предпочтение отдается простейшим видам устройства очередей [2-5]: - «первый вошел - первый обслужился» (FCFS - First Come First Served) - в порядке поступления; - по приоритету - преимущество задается изначально; - по кругу (RR - Round Robin) - средство обслуживания предоставляет свои мощности короткими отрезками времени всем заявкам поочередно, и др. При приемлемой в целом работе таких очередей обнаруживаются случаи, в которых заявки обслуживаются не так, как хотелось бы. Это является следствием односторонности и узости подхода в каждом случае. Начинаются добавления к исходному простому решению или производится коренной пересмотр всего порядка обработки потока заявок. Находят применение следующие усложненные устройства очередей: - «кратчайшая работа следующая» (SJN - Shortest Job Next) - учитывается оставшееся время выполнения заявок; - «c ближайшим крайним сроком первая» (EDF - Earliest Deadline First); - многоуровневые очереди с обратными связями (MLFB - Multiplylevel Feed Back) - циклическое обслуживание (RR) с расщеплением исходной очереди на две или более подочередей, отличающихся по длительности обслуживания заявок, и присвоение им соответствующих приоритетов во избежание задержки коротких заявок; - с изменяемыми приоритетами при циклическом обслуживании (RR) - по оставшемуся времени выполнения (SRT - Shortest Remaining Time) или по наибольшему времени ожидания; - «с наибольшим штрафным отношением следующая» (HPRN - Highes Penalty Ratio Next) - учитывается отношение общего времени пребывания заявки в системе массового обслуживания (СМО) ко времени обслуживания, и др. Перечисленные усложненные устройства очередей также имеют определенные особенности и предпочтительные случаи применения. Одним из путей предупреждения нежелательной последовательности обслуживания заявок при отдельных сочетаниях исходных данных является составление более развернутого описания заявки. Например, весьма редко учитывается действительное время поступления заявки, гораздо чаще - лишь взаимный порядок поступления заявок в очередь. Ниже будет рассмотрена (без привязки к какому-либо воплощению) возможность объединения в одной математической записи сразу нескольких очевидных сторон заявки: времени постановки в очередь, срочности, преимущества, а также продолжительности обслуживания. При этом будет получено правило извлечения заявок из очереди, действующее гибко: то как FCFS, то как RR, то как SJN, и не требующее создания вспомогательных подочередей. 1. Разработка прообраза Будем рассматривать одно средство обслуживания общей очереди (первичная очередь в травматологическом пункте; очередь данных грубого целеуказания, поступающего из внешних источников в радиолокационную станцию для уточнения местоположения целей; очередь вычислительных задач в процессоре данных и т.п.). При этом ничто не мешает рассматривать обращение к этой очереди нескольких средств обслуживания по мере их высвобождения. В качестве количественной меры описания заявки будут взяты потери. 1.1. Время постановки в очередь Вначале будем рассматривать заявки равной важности, отличающиеся только временем постановки заявки в очередь . Учет потерь можно вести с помощью величины, соразмерной времени пребывания заявки в очереди: где T - текущее время, ед. врем.; Ci - потери i-й заявки из-за ожидания, условные единицы в единицу времени (усл. ед./ед. врем.). 1.2. Срочность Важность в обиходном толковании - довольно многозначное понятие. Одно из его осязаемых воплощений - срочность. Срочность заявки можно задавать тем, насколько быстро потери из-за ожидания растут с течением времени, т.е. значением Ci. СМО может назначить повышенную срочность заявкам, привлекательным с точки зрения прибыльности (прибыли в единицу времени обслуживания) или предписанным для обслуживания в ускоренном порядке (льготном). 1.3. Изменение важности во времени В потерях можно учитывать и изменение важности выполнения заявки во времени (рис. 1). Рис. 1. Изменение важности заявок разной природы во времени На рис. 1 показаны следующие временные разновидности заявок: 1) постоянной важности (потери нарастают только за счет увеличения длительности ожидания); 2) важность выполнения которых важна только некоторое время в начале ожидания, а потом убывает медленно или быстро (долгострой; стремительное устаревание данных внешнего грубого целеуказания для радиолокационной станции); 3) уходящие из очереди, если потери из-за ожидания достигают неприемлемого для заявок уровня, или неприемлемым становится время ожидания; 4) имеющие безотлагательный срок начала обслуживания в будущем. При необходимости можно составить подходящие по сложности математические описания потерь этих видов заявок, а также обосновать более замысловатые временные зависимости 1.4. Преимущество (приоритет) Потери, накопившиеся за время ожидания и учитываемые при извлечении заявки на обслуживание, могут толковаться как мера преимущества. Преимущество заявки с течением времени тем больше, чем раньше она встала в очередь. Рассмотрим возможность учета преимущества заявок, назначаемого извне. Отличное от нуля преимущество заявки можно задать, начав отсчет ее потерь при постановке в очередь на обслуживание не с нуля, а с некоторого положительного значения где - временная зависимость потерь сдвинутая по временной оси с учетом времени поступления i-й заявки Ti. Выше важность задавалась через срочность. Преимущество - второе выражение важности. Новая заявка, имеющая большое преимущество, может сразу поступить на обслуживание. Таким образом, с помощью преимущества можно задавать внеочередные заявки, а с помощью повышенной срочности - первоочередные. 2. Время обслуживания 2.1. Обслуживание как длящееся благо До сих пор в прообразе заявки продолжительность ее обслуживания во внимание никак не принималась. Учитывались только время ожидания, срочность и преимущество. Между тем известно, что очередь в кассу при доброжелательном настрое нередко соглашается пропустить вперед того, у кого всего одна единица товара, если у остальных таковых по полной корзине. Каким самоочевидным правилом здесь руководствуется очередь? Думается, таким: оплата выбранного товара - это благо, состоящее в его обретении; чем больше единиц покупок, тем это благо больше; но покупка сопряжена с потерями времени на пребывание в очереди; по справедливости будет, если на получение большего количества блага будет затрачиваться больше времени, и наоборот. Обслуживание, бесспорно, является длящимся благом, если это оздоровительное, восстановительное, развлекательное или образовательное мероприятие или какой-то вид времяпрепровождения (включая творчески-созидательное под руководством воспитателя-наставника). Вместе с тем в большинстве способов управления очередью время обслуживания толкуется как потеря или одно из слагаемых общих потерь времени на пребывание в СМО (например, в дисциплине HPRN). 2.2. Мерило сравнения заявок - относительные потери Рассмотрим следующий пример. Очередь (рис. 2) образуется тремя заявками, поступающими в T1, T2, и T3 и имеющими продолжительности обслуживания: Рис. 2. Очередь заявок с различными (уменьшающимися) продолжительностями требуемого обслуживания Дугообразные стрелки на рис. 2 показывают длительности обслуживания заявок, как если бы каждая из них не вставала в очередь, а сразу поступала на обслуживание. Высвобождение средства обслуживания для этих трех заявок происходит во время Ts. Вопрос: в каком порядке извлекать заявки из очереди? Количественно выразить соразмерность получаемого блага в ходе обслуживания и потерь времени на ожидание получения этого блага для каждой заявки предлагается, рассмотрев не сами потери из-за ожидания, а их отношение к продолжительности обслуживания, т.е. относительные потери: На рис. 3 изображены такие относительные потери для рассматриваемых трех заявок. Рис. 3. Изменение во времени относительных потерь для трех заявок На рис. 3 также нанесены временные вехи обращения средства обслуживания к очереди при правиле: извлекается заявка с наибольшим текущим отношением потерь к продолжительности обслуживания . Если рассмотреть более раннее высвобождение средства обслуживания (см. рис. 2) и начать изменять с то видно, что предпочтительность заявок для средства обслуживания, согласно рис. 3, будет меняться как: 2-1-3, 2-3-1 и 3-2-1, т.е. в конце концов порядок извлечения таких заявок станет противоположным порядку их постановки в очередь, что соответствует дисциплине SJN. Важно отметить, что, в отличие от большинства рассмотрений очередей [2-5], здесь порядок извлечения заявок из очереди заранее никак не задается, а самопроизвольно складывается на основе обработки всей совокупности их исходных данных. Справедливости ради следует также отметить, что дисциплина HPRN для рассмотренного простого примера дает ту же последовательность изменения порядка предпочтительности заявок при сдвиге начиная с Однако понятно, что математическое описание положения заявки в очереди, согласно HPRN, не включает в себя предпочтение и срочность, а уж тем более в нем нет места данным изменения срочности во времени (см. рис. 1), т.е. она уступает по полноте учета различных сторон заявки рассматриваемому прообразу. Таким образом, можно считать, что предлагаемый прообраз заявки, выражаемый относительными потерями, является развитием или обобщением дисциплины HPRN. 3. Дробное обслуживание 3.1. Прерывание обслуживания До сих пор мы по умолчанию считали, что поступившая внеочередная заявка добавляется в начало существующей очереди, т.е. не затрагивая заявку, находящуюся на обслуживании. Но как управлять очередностью, если при появлении внеочередной заявки средству обслуживания необходимо прерываться, недообслужив очередную заявку? Самое простое - это установить, что после высвобождения от обслуживания внеочередной заявки средство обслуживания возвращается к недообслуженной заявке. Иное дело, если попытаться учесть, что за время отвлечения на внеочередную заявку надобность в продолжении прерванного обслуживания недообслуженной заявки может оказаться ниже, чем у какой-либо другой заявки в очереди, обслуживание которой еще не начиналось. Рассмотрим, какие возможности для подобного сравнения предоставляет предлагаемый прообраз заявки, описываемый относительными потерями. Рис. 4. Двукратное прерывание обслуживания заявки с возвращением в очередь Предположим, в очередь на обслуживание встает заявка с требуемой продолжительностью обслуживания (рис. 4). Некогда до нее доходит очередь. Однако спустя время после начала обслуживания заявки средство обслуживания оказывается вынужденным переключиться на внезапно поступившую внеочередную заявку, вследствие чего первая заявка остается обслуженной лишь частично и должна возвратиться ожидать продолжения в ту же очередь. Чтобы понять положение недообслуженной заявки в очереди, надо рассмотреть, каковы теперь у нее срочность и преимущество, влияющие на предпочтение при извлечении из очереди и скорость продвижения в ней. Пусть срочность прежняя, постоянная (см. рис. 1). Преимущество предлагается определять по остатку потерь, которые постепенно погашались в ходе обслуживания. (Погашение до нуля показано на рис. 4 спадающей прерывистой линией.) Выражение для погашения исходных относительных потерь в ходе обслуживания (на отрезке времени от до следующее: Кроме этого следует учесть, что требуемая продолжительность времени обслуживания этой недообслуженной заявки при возврате в очередь уменьшилась до величины поэтому для нее возрастает отношение потерь к продолжительности обслуживания, что на рис. 4 отражено возросшим углом наклона прямой Далее на рис. 4 изображено, как недообслуженная заявка, побыв некоторое время в очереди и поступив на дообслуживание, обслуживается лишь в течение т.е. снова не до конца, и вынужденно возвращается в очередь, поскольку средство обслуживания опять отвлекается на внезапно поступившую внеочередную. Состояние повторно недообслуженной заявки в очереди нужно определять по непогашенным относительным потерям и остаточной продолжительности дообслуживания Повторное дооблуживание этой заявки, согласно рис. 4, исчерпывает остаток положенной продолжительности обслуживания. 3.2. Дробно-избирательное обслуживание Рассмотрение случаев внезапного появления внеочередных заявок показывает возможность применения данного прообраза заявки и для дробного обслуживания, подобного применяемому в вычислительных устройствах: циклическому (RR) и циклическому с обратными связями (MLFB) [3-5] - когда вычислитель поочередно на короткое время предоставляет свои мощности каждому из стоящих в очереди (или в очередях) вычислительных заданий для того, чтобы длительные задания не останавливали продвижение коротких. Рассмотрим средство обслуживания, выполняющее работу с разделением по отрезкам времени, небольшой постоянной продолжительности, с промежуточными проверками после каждого: не достигли ли относительные потери у какой-либо заявки в очереди большего, чем у обслуживавшейся только что заявки, значения - и принятием на обслуживание на следующем временном отрезке заявки с наибольшими относительными потерями. Такое управление очередью вполне возможно назвать дробно-избирательным. В случае использования относительных потерь в качестве меры для выбора, для краткости будем его называть дробно-избирательным по относительным потерям (ДИОП). Будет показано, что при ДИОП нет необходимости в создании вспомогательных очередей и управлении ими, как в случае MLFB, поскольку недообслуженная заявка возвращается в ту же единую общую очередь. 3.3. Первый пример ДИОП Рассмотрим пример ДИОП обслуживания очереди пяти заявок со следующими исходными данными (табл. 1). Таблица 1 Исходные данные заявок Наименование показателя заявки № заявки 1 2 3 4 5 Преимущество, усл. ед. 150 140 0 0 0 Срочность, усл. ед./ед. врем. 1 1 1 1 0,05 Продолжительность, ед. врем. 11 11 1 4 1 Время постановки в очередь, ед. врем. 0 0 0 0 0 Согласно данным табл. 1, преимущество имеют только заявки 1 и 2, но у них наибольшие длительности. Заявки 3 и 5 - обычные и отличаются тем, что они самые короткие, причем у заявки 5 срочность пониженная. Заявка 4 - тоже обычная и имеет промежуточное значение продолжительности. Все заявки встают в очередь одновременно. Налицо непростое и противоречивое сочетание исходных данных. Средство обслуживания обрабатывает заявки шагами длительностью в одну единицу времени, начиная с третьего шага - пусть, до этого оно было занято. На каждом шаге из очереди на обслуживание извлекается та заявка, у которой относительные потери достигли наибольшей величины. Для каждой из заявок ведется пошаговый пересчет относительных потерь и требуемого времени обслуживания остающегося после очередного шага (это значение влияет на скорость нарастания относительных потерь). Пошаговые вычислительные выражения приведены ниже. Для ожидающей i-й заявки относительные потери возрастают, а оставшаяся длительность обслуживания сохраняется: Для обслуживаемой заявки относительные потерь частично погашаются, а оставшаяся длительность обслуживания уменьшается: Единицы во всех пошаговых выражениях выше имеют смысл единиц времени. Длительности обслуживания здесь - целые неотрицательные числа. Правило определения номера заявки, выбираемой для обслуживания или дообслуживания на следующем шаге, таково: для всех Должно быть предусмотрено прекращение вычислений для полностью обслуженной заявки, чтобы не производилось деление на Кроме этого как-то должно быть разрешено противоречие при определении номера заявки, когда у двух или более заявок относительные потери одновременно достигают одинакового наибольшего значения. Это можно сделать, например, добавлением ко всем малых случайных вещественных значений. Цепные вычисления дают следующий порядок ДИОП управления очередью пяти заявок - рис. 5*. Рис. 5. Изменение относительных потерь и отрезки времени обслуживания при ДИОП управлении очередью пяти заявок (авторские результаты) Согласно рис. 5, первой начинает обслуживаться заявка 1 как имеющая наибольшее преимущество - в течение шага одна одиннадцатая ее потерь погашается, а оставшаяся требуемая продолжительность ее обслуживания снижается с одиннадцати до десяти единиц времени. Затем один шаг обслуживается заявка 2, у которой относительные потери из-за ожидания с учетом ее преимущества оказались наибольшими во всей очереди. Далее, т.е. всю первую половину всего времени обслуживания очереди, средство обслуживания «мечется» между этими заявками 1 и 2. Приблизительно в середине этого времени оно «выдергивает» короткую заявку 3, у которой относительные потери неуклонно росли и наконец стали выше, чем у первых двух, частично обслуженных. Обслужившись за один шаг, заявка 3 уходит из СМО, а попеременное обслуживание первых двух заявок продолжается. С 18-го по 29-й шаг средство обслуживания «кружится» между заявками 1, 2 и 4, имеющими к этому времени сравнимые относительные потери, до полного исчерпания требующихся им продолжительностей обслуживания. После их ухода из СМО средство обслуживания приступает к обработке очень короткой, но при этом крайне несрочной заявки 5. Автоматическая работа средства обслуживания в примере с данной очередью выглядит весьма разумной и справедливой: преимущество первых двух заявок учитывается, причем первая уходит раньше, так как ее преимущество больше; обработка сравнительно короткой заявки 3 обеспечивается, причем без слишком большой задержки. Делается это за счет задержки начала обслуживания заявки 4, не имеющей преимущества, а также откладывания на самый конец малосрочной заявки 5. Заявка 3 поступает на обслуживание раньше, чем заявка 4, поскольку имеет меньшую длительность обслуживания. Заявка 4 - раньше, чем заявка 5, которая имеет наименьшую срочность. Какой при исходных данных таблицы 1 сложилась бы очередность при способах управления очередью, перечисленных вначале? FCFS: применение невозможно из-за одновременности поступления заявок; при различии времен поступления применение спорно из-за наличия существенной разницы в преимуществах заявок, которая не учитывается. По приоритету: применение невозможно из-за равенства преимуществ у заявок 3, 4 и 5. RR: применение спорно, так как самая маловажная, но короткая заявка 5 покинула бы СМО раньше, чем закончилось обслуживание сверхважных, но длительных заявок 1 и 2; а если бы обход средством обслуживания начался с нее, то она вообще обслужилась бы первой; EDR: применение невозможно из-за отсутствия данных о крайних сроках обслуживания. SJN, SRT, MLFB и HPRN: применение невозможно из-за равенства времен обслуживания у заявок 1 и 2, а также 3 и 5 (для времени обязательно нужны целочисленные значения!); у этих пар имеются данные о различиях в преимуществе и срочности, но этими способами управления очередью они не учитываются. Случай равенства используемых значений для всех способов управления очередями преодолим: либо принудительным выбором из равных в пользу заявки, например, с меньшим номером, либо использованием для выбора между равными случайного числа. Однако тогда появляется дополнительное преимущество меньших номеров заявок или возникает непредсказуемость предстоящего выбора. Рассматриваемый в данной статье способ управления очередью при данных заявок, согласно данным табл. 1, благополучно справляется. Однако его применение также может стать невозможным, если в ходе вычислений возникнет полное равенство текущих значений относительных потерь у двух самых важных заявок. Для исключения таких случаев при целочисленности времен обслуживания достаточно добавлять к исходным значениям преимуществ и срочностей малые иррациональные значения. Преимущество рассматриваемого способа перед перечисленными в большинстве остальных, невырожденных случаев заключается в том, что он учитывает большее количество исходных данных о заявках и гибко использует их для управления очередью. 3.4. Второй пример ДИОП Рассмотрим пример ДИОП управления очередью пяти заявок, в котором заявки имеют предельный срок ожидания перед началом обслуживания. Исходные данные приведены в табл. 2. Таблица 2 Исходные данные заявок, включая предельный срок ожидания Наименование показателя заявки № заявки 1 2 3 4 5 Преимущество, усл. ед. 150 120 5 2 0 Срочность, усл. ед./ед. врем. 1 1 1 1 1 Продолжительность, ед. врем. 12 10 3 2 1 Предельный срок ожидания, ед. врем. 1000 20,5 12,5 11,5 5,5 Время постановки в очередь, ед. врем. 0 0 0 0 0 Как и в примере 1, все заявки встают в очередь одновременно, а обслуживание начинается с 3-го шага (отрезок между отметками 2 и 3 на временной оси). Заявка 1 имеет наибольшее преимущество, но и наибольшую длительность. В данные заявок добавлен «предельный срок ожидания» - его значения различны. Для заявки 1 этот срок по сути не задан (1000 - это запредельно много), для заявки 2 обслуживание должно начаться не позднее 22-го шага (поэтому срок выбран 20,5, т.е. непосредственно перед этим, в середине 21-го шага). Заявки 3, 4 и 5 имеют в зависимости от номера убывающие преимущество и продолжительность обслуживания, но при этом они отличаются сокращением предельного срока ожидания. Таким образом, данные довольно противоречивы. В этих данных задано меньше совпадающих значений, по сравнению с табл. 1, для возможности сравнения с известными способами управления очередью. Изменяющаяся во времени срочность с назначением предельного срока ожидания начала обслуживания (кривая 4 на рис. 1) может быть задана математически в виде гладкого или резкого (кусочно-линейного) перехода - ступеньки. При гладком переходе: где - исходная важность (задолго до начала перехода), усл. ед.; H - высота ступеньки (выбирается заведомо многократно большей, чем срочность любых других заявок в очереди), усл. ед.; P - протяженность пологости (чем P больше, тем переход растянутее во времени), ед. врем. При кусочно-линейном задании перехода: где функция ЗНАК соответствует одноименной функции Excel: При оба описания скачка важности сближаются. В вычислениях будем использовать более простое кусочно-линейное описание, так как в нем не требуется дополнительное обоснование выбора значения протяженности пологости P, и при котором проще толковать получающуюся очередность обслуживания. С учетом выбранного способа задания изменения важности во времени потери в течение ожидания для i-й заявки, поступившей в выражаются так: Изменение в выражениях для пошаговых вычислений единственное: пошаговый рост относительных потерь должен рассчитываться теперь как: Цепные вычисления для второго примера приведены на рис. 6*. Рис. 6. Изменение относительных потерь и отрезки времени обслуживания при ДИОП управлении очередью пяти заявок с заданными предельными сроками начала обслуживания (авторские результаты) Согласно рис. 6, первыми попеременно начинают обслуживаться сверхважные заявки 1 и 2. В середине шага 6 (отрезка между отметками 5 и 6 на временной оси) подходит срок начала обслуживания заявки 5, самой маловажной, - «взлетают» вверх ее относительные потери. Она обслуживается за один шаг и покидает СМО. Далее снова попеременно обслуживаются заявки 1 и 2. На шаге 12 (отрезок 11-12 на временной оси) подходит срок заявки 3, а на шаге 13 - заявки 4. Начала их обслуживания почти совпадают, а обслуживание по времени требует больше одного шага для каждой, поэтому они обслуживаются попеременно (но эта попеременность возникает автоматически). В итоге они уходят из СМО с дополнительной задержкой у каждой из-за того, что они мешали друг другу. С середины 21-го шага подходит срок начала обслуживания заявки 2. Она уже частично обслужена, поэтому она дообслуживается и покидает СМО. Следующие четыре шага СМО дообслуживает заявку 1, которая изначально обладала наибольшим преимуществом, но в отличие от остальных не имела близкого предельного срока начала обслуживания. Если бы не было сверхважных заявок 1 и 2, то поступление на обслуживание заявок 3, 4 и 5 происходило бы в порядке их преимуществ: первой - заявка 3 (B03 = 5); второй - заявка 4 (B04 = 2); третьей - заявка 5 (B05 = 0). Но, согласно рис. 6, на обслуживание они были взяты в обратной последовательности. Причина - задержка в обслуживании всех трех из-за сверхважных заявок 1 и 2, отчего их очередность стала определяться не преимуществом, а предельным сроком начала обслуживания. Все кажущиеся неразрешимыми противоречия исходных данных гибко разрешаются, итоги объяснимы. Рассмотрим применимость известных способов управления очередью при данных согласно табл. 2. FCFS: применение невозможно или спорно по указанным в примере 1 причинам. По приоритету: применение невозможно из-за того, что исполнение заявок 1 и 2 сорвет сроки начала обслуживания заявок 3, 4 и 5. RR: применение спорно по причинам, указанным в примере 1. EDR, SJN: применение возможно; последовательность приема на обслуживание та же, что и у предлагаемого способа; отличие - обслуживание без чередования. SRT, MLFB и HPRN: применение невозможно из-за неизбежного совпадения в ходе вычислений целочисленных значений времени; различия в преимуществе и предельных сроках ожидания не учитываются. Таким образом, при данных табл. 2 пригодны для использования дисциплины ДИОП, EDR и SJN. 4. Сравнение способов управления очередью 4.1. Мера сравнения - объем терпения Для сравнения применимых способов управления очередью нужна подходящая количественная мера. Обычно используется среднее время пребывания заявки в СМО, вычисленное при определенном наборе условий. ДИОП управление использует более емкую по числу учитываемых сторон и гибкую меру - относительные потери. Из рис. 1 и рис. 2 видно, что 1) относительные потери изменяются во времени; 2) они различны у разных заявок; 3) длительность пребывания в СМО разная. Как это соединить в одном показателе? Очевидно, что ожидание в очереди требует от посетителя терпения. Количественно терпение можно выразить через произведение двух сомножителей: времени ожидания и силы чувства неудобства при ожидании (час ожидания на первичный прием в травмпункт от людей с разной тяжестью ранений требует различного терпения). Силе чувства, согласно прообразу заявки, можно поставить в соответствие относительные потери. Изменяемость потерь во времени требует суммирования относительных потерь по шагам ожидания. Учитывая эти рассуждения, меру сравнения можно назвать как объем терпения: где - среднее терпение, требующееся источнику i-й заявки при ожидании в течение k-го шага времени. На шагах, когда заявка обслужилась или еще не поступила в СМО, требующееся терпение равно нулю. Поскольку обслуживание - благо, то терпение и на шагах обслуживания также следует считать равным нулю. На шагах ожидания терпение можно вычислять через полусумму значений относительных потерь на временных границах шага: где «1» - это длительность шага (размерность ед. врем.). При этом следует исключить из расчетов значение относительных потерь при достижении предельного срока ожидания, так как оно из-за своей огромности будут искажать счет объема терпения. Обнаружить его можно, проверив условие: При его выполнении надо заменять полусумму относительных потерь - для простоты значением на нижней границе, где условие не выполняется. Например, для заявки 5, согласно рис. 6, пошаговые средние терпения приведены в табл. 3. Таблица 3 Ряды шагов времени, относительных потерь в конце шага и терпения в течение шага k 0 1 2 3 4 5 6 7 0 1 2 3 4 5 1006 0 0 0,5 1,5 2,5 3,5 4,5 5 0 Если неравенство выше выполняется для обеих границ отрезка (чередование обслуживания двух заявок с одновременно закончившимся сроком ожидания - заявки 3 и 4 из примера 2), то для простоты среднее терпение на этом отрезке также можно считать нулевым. При ДИОП управлении очередью последовательность обслуживания заявок по временным шагам для данных примера 2 следующая: - - 1 2 1 2 5 1 2 1 2 1 4 3 4 3 3 2 1 2 1 2 2 2 2 1 1 1 1 1. Для тех же данных при управлении очередью согласно EDR или SJN (решающим для EDR является ближайший предельный срок ожидания обслуживания, а для SJN - малость оставшегося времени обслуживания): - - 5 4 4 3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1. Расчеты объемов терпения по каждой заявке по данным табл. 3 для ДИОП управления очередью, а также в соответствии с EDR или SJN приведены в табл. 4. Таблица 4 Объемы терпения по отдельным заявкам и общие, усл. ед. Способ управления очередью № заявки S 1 2 3 4 5 ДИОП 415,1 160,5 139,7 49,67 47,75 17,5 EDR или SJN 357,5 238,5 99,2 12,5 5,25 2 Из данных табл. 4 следует, что для данных табл. 3 сумма объемов терпения по всем заявкам СМО будет меньше для способов управления очередью EDR и SJN, а не для ДИОП. Вместе с тем при EDR или SJN видна огромная неравномерность в объемах терпения для различных заявок: свыше ста раз для 1 и 5, а также свыше двух раз для близких по данным заявкам 1 и 2. Для ДИОП управления различия объемов терпения в таких же парах - менее десяти раз и менее 15 %. Таким образом, при управлении очередью по правилу EDR или SJN из-за проявленной «несправедливости» высока опасность потери в дальнейшем заказчика самой значимой заявки 1. ДИОП управление в наибольшей степени учитывает высокую значимость заявок 1 и 2, обслуживая их до тех пор, пока не наступит предельный срок по малозначимой заявке 5. Далее возобновляется обслуживание заявок 1 и 2, пока не наступят сроки для заявок 3 и 4. Таким образом, и сроки заявок 3, 4 и 5 соблюдаются, и отдается должное важностям заявок 1 и 2. Представляется, что это самая разумная и справедливая из возможных последовательностей обслуживания, и важно, что обеспечивается она полностью автоматически. 4.2. Подходы к показателю качества Сосредотачиваясь на совершенствовании управления очередью заявок, нельзя рассматривать ее качество в отрыве от устройства СМО (способа назначения важностей заявкам), от обстановки, в которой производится оценка. Конечным показателем качества СМО является ее способность успешно действовать и выживать в сложных меняющихся условиях (рынка). Постоянный пользователь решится на отказ от сотрудничества с данной СМО, если: время ожидания выполнения его заявок будет, с его точки зрения, неприемлемо большим; несколько подряд его заявок вовсе останутся без внимания; его заявка, бесспорно, важна, а СМО несправедливо предпочтет ей другую, менее важную заявку и т.п. Таким образом, в СМО должны учитываться также ожидания постоянных пользователей. Выше был рассчитан простейший возможный показатель качества - суммарной объем терпения всех заявок, но было показано, что некоторым посетителям СМО он может оказаться небесспорным. Пытаясь учесть возможное недовольство отдельных посетителей несопоставимостью объемов терпения в примере выше, можно предложить в качестве показателя сравнения отношение среднеквадратического отклонения к среднему значению объема терпения, вычисленному по всем заявкам. Но и тут к преимуществу показателя может быть отнесена лишь простота, так как в основе этого подхода - представление, что равенство это лучшее. Наилучшим, на наш взгляд, мог бы быть показатель качества, подходящим образом объединяющий в себе отношения обыденных ожиданий и действительных объемов терпения всех посетителей. Обыденное ожидание - это представление о «правильной», «справедливой» работе СМО, опирающееся на чувства и не предполагающее специальных навыков оценки деятельности СМО. Пример расчета действительных объемов терпения представлен выше. С количественной оценкой обыденных ожиданий людей все значительно хуже: участие лимбической системы и уровень развития новой коры сводят количественное выражение обыденного ожидания к сравнительным понятиям «больше - меньше», «наибольший - наименьший». В лучшем случае может использоваться действие сложения из четырех арифметических. Отдельную сложность представляет собой принятие решений в условиях множественных противоречий. Но даже при наличии специальных знаний и навыков в приведенных выше примерах, где намеренно выбраны противоречивые исходные данные, «правильные», «справедливые» действия СМО далеко не очевидны. Представляется, что в целом большее доверие будет вызывать тот способ управления очередью, в котором учитывается большее количество сторон различия заявок - в данном случае, это ДИОП, а не EDR или SJN. Без труда может быть составлен в разы более сложный, запутанный и противоречивый набор исходных данных, который будет непосилен для решения никакому человеку, и тогда ДИОП можно пытаться рассматривать как «умное» управление очередью, как пример воплощения искусственного разума, в котором человеку отводится задача подготовки исходных данных и задание правил их обработки, и затем обобщенная оценка получившегося решения, а само решение принимается машиной. Заключение Представлены рассуждения по разработке обобщенного наглядного прообраза заявки в общей очереди на обслуживание при одном средстве обслуживания. Учитывается время ожидания, срочность, преимущество и длительность требуемого обслуживания. В прообразе воплощено обиходное представление о справедливости как соразмерности потерь из-за ожидания и продолжительности обслуживания, если обслуживание можно толковать как длящееся благо. Может учитываться изменение срочности заявки во время ожидания. Соединение прообраза с правилом извлечения заявок «наибольшие относительные потери из-за ожидания» открывает возможности более гибкого обслуживания очереди, чем это может дать большинство известных дисциплин. В зависимости от сочетания исходных данных могут проявляться черты как бесприоритетных, так и приоритетных дисциплин обслуживания. По математическому описанию из общеизвестных дисциплин обслуживания ближе всего к рассматриваемому прообразу стоит дисциплина HPRN («с наибольшим штрафным отношением следующая»). Предлагаемый прообраз применим в дробно-избирательном обслуживании, подобном циклическому обслуживанию многоуровневой очереди с обратными связями (MLFB). Но рассмотренное в данной статье на примерах ДИОП управление очередью, в отличие от HPRN и MLFB, учитывает не только время. Преимущество HPRN и MLFB, заключающееся в их большей вычислительной простоте, по мере углубления информатизации становится все менее значимым.

About the authors

L. V. Bolshakova

Saint Petersburg University of the Ministry of the Interior of Russia

K. D. Sibarov

Saint Petersburg University of the Ministry of the Interior of Russia

N. A. Yakovleva

Saint Petersburg University of the Ministry of the Interior of Russia

References

Statistics

Views

Abstract - 30

PDF (Russian) - 14

Refbacks

• There are currently no refbacks.