.
Весьма интересной задачей является выбор приоритетов для заявок различных классов. Поскольку имеет место закон сохранения, оптимизация имеет смысл только при рассмотрении некоторых дополнительных атрибутов каждого класса требований. Предположим, что можно оценить каждую секунду задержки заявки приоритетного класса p некоторой стоимостью Cp. Тогда средняя стоимость секунды задержки для системы может быть выражена через среднее число требований каждого класса, находящихся в системе
Решим задачу нахождения дисциплины обслуживания с относительными приоритетами для системы M/G/1, которая минимизирует среднюю стоимость задержки C. Пусть имеется P приоритетных классов заявок с заданной интенсивностью поступления и средним временем обслуживания. Перенесем в левую часть постоянную сумму и выразим правую часть через известные параметры
Задача состоит в минимизации суммы в правой части этого равенства путем выбора соответствующей дисциплины обслуживания, т.е. выбора последовательности индексов p.
Обозначим
В этих обозначениях задача выглядит так: нужно минимизировать сумму произведений при условии
Условие независимости суммы функций gp от выбора дисциплины обслуживания определяется законом сохранения. Иначе говоря задача состоит в минимизации площади под кривой произведения двух функций , при условии , что площадь под кривой одной из них постоянна.
Решение состоит в том, что сначала упорядочим последовательность значений fp: .
А затем выберем для каждого fp свое значение gp, так, чтобы минимизировать сумму их произведений. Интуитивно ясно, что оптимальная стратегия выбора состоит в подборе наименьшего значения gp для наибольшего fp , далее для оставшихся значений следует поступать тем же образом. Поскольку gp=Wprp, то минимизация сводится к минимизации значений средней задержки. Таким образом, решение рассматриваемой задачи оптимизации состоит в том, что из всех возможных дисциплин обслуживания с относительным приоритетом минимум средней стоимости обеспечивает дисциплина с упорядоченными приоритетами в соответствие с неравенствами
.
Дисциплины обслуживания с приоритетами, зависящими от времени
На практике часто встречается задача назначения приоритетов в зависимости от времени поступления заявки. Например, для того, чтобы никакие требования не задерживались в системе очень долго, несмотря на общую нагрузку, организуют дисциплину обслуживания, при которой чем дольше заявка находится в системе, тем ее приоритет становится выше.
Рассмотрим приоритетные функции, линейно зависящие от времени с крутизной нарастания, зависящей от номера класса, к которому принадлежит требование.
Предположим, что некоторое меченое требование поступает в момент t и получает в момент t приоритет, определяемый значением приоритетной функции
Всякий раз, когда сервер готов к обслуживанию нового требования он выбирает из очереди требование с наивысшим мгновенным приоритетом- наибольшим значением приоритетной функции. Требования из класса с большим значением p наращивают приоритет с большей скоростью, чем требования из низшего приоритетного класса. На рисунке 3 показан пример того, как поступившее позже требование, но из высшего приоритетного класса, может получить обслуживание раньше, чем поступившее ранее требование из менее приоритетного класса. Это произойдет, если сервер освободится позже момента t0 . При освобождении сервера до этого момента, обслуживание получит первое из поступивших требований.
Рис. 3 Взаимодействие между приоритетными функциями для СМО с приоритетами, зависящими от времени.
Исследуем эту систему при экспоненциальном распределении времени обслуживания.
Найдем среднее число требований , поступивших позже меченого , из классов с p ³ i , которые будут обслужены раньше меченого. Очевидно, что для таких требований скорость нарастания приоритетной функции меньше скорости нарастания приоритетной функции меченого требования и , следовательно число таких требований равно нулю. Теперь определим число таких требований для классов с большей, чем у меченого скоростью нарастания приоритетной функции p< i. Из рассмотрения рисунка 3 можно видеть, что задержка меченого требования в системе для этого случая Wp=t0-t связана с интервалом времени на котором поступают заявки, опережающие меченое требование VI = ti - t соотношением
Отсюда получаем, что этот интервал равен
Следовательно, при интенсивности li входящего потока для требований i-го класса находим среднее число «обгоняющих» требований
Рассмотрим теперь меченое требование из класса p, поступающее в момент t=0 и находящееся в очереди в течение времени tp.
Рис. 4 График приоритета qp(t), используемый для получения .
На рисунке 4 показано, что значение функции приоритета этого требования к моменту поступления на сервер будет равно bptp. При поступлении меченого требования оно застает в очереди ni требований из класса i . Одно из таких требований показанное на рисунке 4 поступило в момент t=-t1. Определим теперь среднее число требований из класса i , которые поступают до нулевого значения момента времени, находятся в нулевой момент еще в очереди и получают обслуживание раньше меченого требования. Из рисунка 4 можно видеть, что этому условию удовлетворяет требование из класса i , которое поступает в момент -t1 и ожидает в очереди в течение времени
Из рассмотрения соотношений на рисунке видно, что
Тогда среднее число требований
При i > p
Подставив вычисленные средние значения для «обгоняющих» требований получим систему линейных уравнений для величин задержки меченого требования
Производя преобразования, можно свести решение этой системы уравнений к рекурсивной форме
Полученная формула представляет собой главный результат анализа дисциплины обслуживания с приоритетами, зависящими от времени. Типичная характеристика СМО с проанализированной дисциплиной обслуживания приведена на рисунке 5 Штриховая линия показывает характеристику для системы без приоритетов. Видно, что действие закона сохранения проявляется здесь в том, что хотя одна часть заявок, получившая высший приоритет будет иметь меньшее время ожидания, чем в системе без приоритетов с обслуживанием в порядке поступления, другая часть заявок при этом обязательно будет задержана на большее, чем в бесприоритетной системе время.
Рис. 5 для СМО с относительными приоритетами, зависящими от времени (Р=5, lр=l/5,).
Оптимизация назначения приоритетов
Рассмотрим систему M/G/1 с интенсивностью поступающего пуассоновского потока l требований в секунду и произвольной функцией плотности вероятности для времени обслуживания с заданным средним временем обслуживания. Пусть плата за требование Y является случайной величиной с произвольной функцией распределения .
Система функционирует следующим образом: новое требование, поступившее в систему «предлагает» неотрицательную плату Y «организатору очереди». После этого требованию предоставляется место в очереди такое, что все требования внесшие меньшую плату оказываются позади, большую впереди данного требования. В каждый момент времени сервер, завершив обслуживание очередного требования, принимает на обслуживание требование, оказавшееся впереди всей очереди. До полного завершения обслуживания требование не покидает сервер. Требования, внесшие одинаковую плату, обслуживаются в порядке поступления.
Найдем среднее время ожидания в очереди для требования, внесшего плату Y=y. Это время складывается из трех составляющих. Во-первых, это время на дообслуживание требования, находящегося в данный момент в сервере. Во-вторых – время обслуживания требований, которые поступили раньше и внесли большую или равную плату. Наконец меченому требованию придется ждать обслуживания всех требований поступивших позже его, но внесли большую плату. Среднее число требований, плата которых лежит в интервале (u,u+du) определяется по формуле Литтла :, где .
Используя обозначения для нижнего и верхнего предела функции b(u) можно записать суммарное выражение для времени ожидания в очереди для меченого требования в виде:
Используя ряд соотношений и обозначений можно найти, что при разрывной функции распределения вероятности это соотношение может быть приведено к виду
При абсолютно непрерывной функции плотности вероятности получим
.
Таким образом, мы получили конечное среднее время ожидания для всех требований, которые вносят плату выше, чем некоторое критическое значение
В пределе, когда размер платы стремится к бесконечности, среднее время ожидания стремится к W0. Нетрудно убедиться, что когда размер платы для всех требований одинаков
Это известный результат для СМО типа M/G/1 при обслуживании в порядке поступления, как и следовало ожидать, поскольку равная плата равносильна ее отсутствию с точки зрения распределения приоритетов.
При распределении приоритетов можно рассмотреть и другие стоимостные задачи. Определим оптимальное распределение платы за приоритеты в следующих предположениях. Пусть имеется зависимость стоимости от времени задержки в очереди для каждого требования, т.е. есть возможность определить, сколько стоит каждая секунда ожидания в очереди. Опишем эту зависимость с помощью случайного коэффициента нетерпения a.
Очевидно, что общие затраты клиента при обслуживании будут состоять из платы за место в очереди и потерь от времени ожидания. Для требования с фиксированным коэффициентом нетерпения эти затраты равны
Пусть для всей совокупности клиентов можно определить функцию распределения вероятностей коэффициентов нетерпения
Сформулируем следующую задачу оптимизации: найти функцию ya , которая минимизирует среднюю стоимость С при условии ограничения всей средней платы некоторой заданной величиной B.
Определим
Преобразуя минимизируемый интеграл, получим
Из закона сохранения в непрерывной форме
следует, что решение задачи минимизации стоимости сводится к нахождению такой функции, при которой минимальна площадь под кривой произведения :
.
В то время как площадь под кривой, определяемой первым сомножителем должна оставаться постоянной.
Путем рассуждений о согласованности возрастания и убывания функций, входящих в произведение, можно сделать вывод, что решением задачи являются все функции, удовлетворяющие условию
Множество S такое, что.
Выберем самую простую строго возрастающую функцию – линейную. Таким образом, будем считать, что плата пропорциональна коэффициенту нетерпения.
.
Применяя ограничение средней платы
получим, что, если считать средний коэффициент нетерпения равный A
Это и есть функция оптимальной платы.
В качестве примера рассмотрим систему с показательным распределением платы
Время ожидания можно непосредственно вычислить:
Используя рассмотренное правило оптимальной платы можно найти распределение коэффициента нетерпения
Следовательно, средняя стоимость получается:
Описанная оптимизация является глобальной и позволяет найти функцию платы, которые минимизируют общую среднюю стоимость.
Страницы: 1, 2
