4446
правок
Балансировка нагрузки: различия между версиями
Материал из WEGA
→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Планирование временных задач в режиме онлайн == Постановк…») |
Irina (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
В наиболее общей модели m машин – 1, ..., m. Информация о поступающем задании j представляет собой вектор | В наиболее общей модели имеется m машин – 1, ..., m. Информация о поступающем задании j представляет собой вектор <math>p_j</math> длины m, где <math>p^i_j</math> – это нагрузка или размер задания j, если оно назначено машине i. Как было сказано выше, каждое задание должно быть назначено машине до следующего поступления или убытия. Нагрузка на машину i в момент времени t обозначается <math>L^t_i</math> и представляет собой сумму нагрузок (на машину i) заданий, назначенных машине i, которые поступили к моменту времени t и не убыли к этому времени. Цель заключается в сведении к минимуму максимальной нагрузки любой машины при всех значениях t. Эта машинная модель носит название «''несвязанные машины''» (см. в [3] исследование проблемы балансировки нагрузки при выполнении постоянных задач на несвязанных машинах). Было определено немало более специальных моделей. Далее будет описано несколько таких моделей. | ||
Для алгоритма A мы обозначаем его стоимость также как A. Стоимость оптимального оффлайнового алгоритма, который знает всю последовательность событий заранее, обозначается OPT. Балансировка нагрузки изучается в терминах (абсолютного) коэффициента конкурентоспособности. Коэффициентом конкурентоспособности алгоритма A является инфимум R, такой, что для любых входных данных A | Для алгоритма <math>\mathcal{A}</math> мы обозначаем его стоимость также как <math>\mathcal{A}</math>. Стоимость оптимального оффлайнового алгоритма, который знает всю последовательность событий заранее, обозначается OPT. Балансировка нагрузки изучается в терминах (абсолютного) коэффициента конкурентоспособности. Коэффициентом конкурентоспособности алгоритма <math>\mathcal{A}</math> является инфимум <math>\mathcal{R}</math>, такой, что для любых входных данных <math>\mathcal{A} \le \mathcal{R} \cdot OPT</math>. Если коэффициент конкурентоспособности онлайнового алгоритма не превышает С, этот алгоритм также называется С-конкурентным. | ||
Равномерно связанными машинами [3, 12] являются машины, с которыми ассоциированы скорости; таким образом, машина i имеет скорость | ''Равномерно связанными машинами'' [3, 12] являются машины, с которыми ассоциированы скорости; таким образом, машина i имеет скорость <math>s_i</math>, а информацией, которую задание j должно предоставить по прибытии, является только его размер, или нагрузка, которую он налагает на машину с единичной скоростью, что обозначается <math>p_j</math>. Положим <math>p^i_j = p_j / s_i</math>. Если все скорости одинаковы, в результате получаются ''идентичные машины'' [15]. | ||
Ограниченное назначение [ ] представляет собой модель, в которой каждое задание может выполняться только на подмножестве машин. Задание j ассоциируется со временем выполнения, равном времени выполнения на любой из разрешенных ему машин | ''Ограниченное назначение'' [8] представляет собой модель, в которой каждое задание может выполняться только на подмножестве машин. Задание j ассоциируется со временем выполнения, равном времени выполнения на любой из разрешенных ему машин <math>M_j</math>. Таким образом, если <math>i \in M_j</math>, то <math>p^i_j = p_j</math>, в противном случае <math>p^i_j = \infty</math>. | ||
== Основные результаты == | == Основные результаты == | ||
