Оптимизация назначения приоритетов

Задача: когда с потоком заявок связывается некоторая неотрицательная функция, значение которой для каждой заявки может интерпретироваться как стоимость обслуживания.

Система функционирует следующим образом: новое требование, поступившее в систему «предлагает» неотрицательную плату Y «организатору очереди». После этого требованию предоставляется место в очереди такое, что все требования внесшие меньшую плату оказываются позади , большую впереди данного требования. В каждый момент времени сервер, завершив обслуживание очередного требования, принимает на обслуживание требование, оказавшееся впереди всей очереди. До полного завершения обслуживания требование не покидает сервер. Требования, внесшие одинаковую плату, обслуживаются в порядке поступления.

В пределе, когда размер платы стремится к бесконечности, среднее время ожидания стремится к W₀. Нетрудно убедиться, что когда размер платы для всех требований одинаков

Очевидно, что общие затраты клиента при обслуживании будут состоять из платы за место в очереди и потерь от времени ожидания. Для требования с фиксированным коэффициентом нетерпения эти затраты равны

Пусть для всей совокупности клиентов можно определить функцию распределения вероятностей коэффициентов нетерпения

Из закона сохранения в непрерывной форме

следует, что решение задачи минимизации стоимости сводится к нахождению такой функции, при которой минимальна площадь под кривой произведения :

.

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

.

Применяя ограничение средней платы

получим, что, если считать средний коэффициент нетерпения равный A

Это и есть функция оптимальной платы.

В качестве примера рассмотрим систему с показательным распределением платы

Время ожидания можно непосредственно вычислить:

Используя рассмотренное правило оптимальной платы можно найти распределение коэффициента нетерпения

Следовательно, средняя стоимость получается:

Описанная оптимизация является глобальной и позволяет найти функцию платы, которые минимизируют общую среднюю стоимость.