Минимизация простоя ресурсов при ограничении на время их использования

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

Формально эту задачу можно записать в виде

, =1, 2, 3, . (3.3.13)

Считаем, что при . В результате решения задачи (3.3.13) получаем комбинации слотов, каждая из которых является оптимальной и обеспечивает максимум и, следовательно, отсутствие простоя ресурсов: (1, 2, 3), (2, 1, 3), (2, 2, 2) и (3, 1, 2).

Заметим, что лишь для комбинаций (2, 2, 2) и (3, 1, 2) цена составляет 20 единиц и является максимальной.

Задача выбора эффективной комбинации слотов

Постановка задачи

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

Пусть – вектор частных критериев , , например . Вектор формирует бинарное отношение сравнительной эффективности комбинаций слотов множества , такое что

, , . (3.4.1)

Положим, имеет место (3.4.1) и при этом . Тогда - отношение Парето.

Будем применять понятие модели выбора и говорить об -оптимальной стратегии планирования пакета заданий. Стратегия понимается как множество оптимальных по бинарному отношению комбинаций слотов в модели выбора . Если, в частности, - отношение Парето, то речь идет о Парето-оптимальной стратегии. Каждый из критериев формирует частное бинарное отношение

. (3.4.2)

При этом в (3.4.2) , а – подмножество комбинаций слотов, одновременно обладающее свойством внешней устойчивости

(3.4.3)

и внутренней устойчивости

(3.4.4)

в модели выбора .

Подмножество множества комбинаций слотов, определяемое в соответствии с (3.4.2) – (3.4.4), будем называть стратегией, условно оптимальной по частному критерию .

Формальная постановка задачи выбора эффективной комбинации слотов при заданном ограничении (3.2.5) заключается в построении -оптимальной стратегии, где формируется вектором критериев, таким что имеет место (3.4.1), и отборе наилучшего компромиссного решения путем нахождения экстремума (например, минимума) функции полезности вида

, (3.4.5)

где – вес частного критерия , а – его нормированное значение.

В (3.4.5) нормированное значение любого из критериев определяется согласно соотношению

. (3.4.6)

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