Минимальное время завершения для взвешенной системы: различия между версиями

Задача нахождения минимального времени завершения для взвешенной системы представляет собой (1) набор J из n заданий, каждому из которых присвоены положительный вес (<math>w_j \;</math> для <math>j \in J \;</math>) и дата запуска <math>r_j \;</math>, ранее которой это задание не может быть спланировано; (2) набор из m вычислительных машин, каждая из которых может обрабатывать не более одного задания в одно и то же время; (3) произвольный набор положительных значений <math>\{ p_{i, j} \} \;</math>, где <math>p_{i, j} \;</math> обозначает время обработки задания j на машине i. План представляет собой назначение заданий машинам и выбор порядка их обработки. Обозначим за <math>C_j \;</math> время завершения задания j в рамках выполнения конкретного плана. Определим время завершения для взвешенной системы как <math>\sum_{j \in J} w_j C_j \;</math>. Задача заключается в вычислении плана, имеющего минимальное время завершения.

В нотации планирования, введенной Грэмом и др. [7], задача планирования задается триплетом <math>\alpha | \beta | \gamma \;</math>, где <math>\alpha \;</math> обозначает машинную среду, <math>\beta \;</math> – дополнительные ограничения для заданий, а <math>\gamma \;</math> – целевую функцию. В данном случае нас главным образом будут интересовать значения параметра <math>\alpha \;</math>, равные 1, P, R или Rm, которые означают, соответственно, одну машину, идентичные параллельные машины (то есть для фиксированного задания j и для каждой машины i <math>p_{i,j} \;</math> равно значению <math>p_j \;</math>, независимому от i), несвязанные машины (значения <math>p_{i,j} \;</math> зависят и от задания i, и от машины j) и фиксированное количество m (не являющееся компонентом входных данных) несвязанных машин. Поле <math>\beta \;</math> принимает следующие значения: <math>r_j \;</math> обозначает, что у заданий имеются даты запуска; pmtn – что разрешено вытеснение заданий; prec – что задача может включать отношения предшествования между заданиями, что также налагает ограничения на составление плана. Поле <math>\gamma \;</math> содержит значения <math>\sum w_j C_j \;</math> либо <math>\sum C_j \;</math>, которые соответствуют полному времени завершения для взвешенной системы и для невзвешенной системы, соответственно.

Некоторые из более простых классов задач поиска минимального времени завершения для взвешенной системы допускают использование оптимальных решений с полиномиальным временем выполнения. Среди них можно упомянуть задачу <math>P || \sum C_j \;</math>, для которой оптимальной является стратегия «самое короткое задание планировать первым»; <math>1 || \sum w_j C_j \;</math>, для которой оптимальным является следование правилу Смита [13] (планирование заданий в порядке неубывания значений <math>p_j / w_j \;</math>); <math>R || \sum C_j \;</math>, которая может быть решена при помощи техник сопоставления [2, 9]. При введении дат запуска даже простейшие классы задач минимизации времени завершения для взвешенной системы становятся строго недетерминированными с полиномиальным временем выполнения (NP-полными). Подход Афрати и др. [1] заключается в разработке аппроксимационных схем с полиномиальным временем выполнения (PTAS) для нескольких классов задач планирования, способствующих минимизации времени завершения для взвешенной системы с указанием дат запуска. До публикации упомянутой работы лучшие решения для минимизации времени завершения для взвешенной системы с указанием дат запуска представляли собой алгоритмы O(1)-аппроксимации (см., например, [4, 5, 11]); единственный известный PTAS-алгоритм для сильной NP-полной задачи, рассматривающей время завершения для взвешенной системы, предложили Скутелла и Вёгингер [12], разработавшие PTAS для задачи <math>P || \sum w_j C_j \;</math>. Исчерпывающий обзор задач поиска минимального времени завершения для взвешенной системы составили Чекури и Ханна [3].

Афрати и др. [1] первыми разработали PTAS-алгоритмы для задач поиска минимального времени завершения для взвешенной системы с указанием дат запуска. В таблице 1 приведено время выполнения этих PTAS-алгоритмов.

[[Файл:MWCT_table.png]]

Первым этапом преобразования на входе является ''геометрическое округление'', при помощи которого длительность обработки и дата запуска преобразуются в степени значения <math>1 + \epsilon \;</math>, в результате чего общая эффективность снижается не более чем на <math>1 + \epsilon \;</math>. Что еще более важно, этот этап: (1) гарантирует небольшое количество различных значений длительности обработки и даты запуска; (2) позволяет разбивать время на геометрически возрастающие интервалы; и (3) выравнивает даты запуска относительно временных границ начала и конца интервалов. Все эти полезные свойства могут использоваться алгоритмом динамического программирования.

Вторым этапом преобразования на входе является ''растягивание по времени'', во время которого к плану на всем его протяжении добавляются небольшие объемы времени простоя. Этот этап также увеличивает время завершения не более чем на <math>1 + O (\epsilon) \;</math>, однако он полезен для лучшей организации процесса планирования. В частности, если задание слишком велико (т. е. занимает большую часть интервала, в котором оно выполняется), его можно переместить во время простоя более позднего интервала, в котором оно будет занимать небольшую часть времени. Это гарантирует, что большинство заданий будут иметь небольшой размер по сравнению с продолжительностью интервала, в котором они выполняются, что значительно упрощает составление плана. Следующим этапом будет ''перемещение заданий''. Рассмотрим разбиение временного интервала <math>[ 0, \infty ) \;</math> на интервалы формы <math>I_x = [(1 + \epsilon)^x,(l + \epsilon)^{x + 1}) \;</math> для целочисленных значений x. Этап перемещения заданий гарантирует, что существует почти субоптимальный план, в котором каждое задание j выполняется в пределах <math>O(log_{1 + \epsilon} (1 + \frac{1}{\epsilon})) \;</math> интервалов после <math>r_j \;</math>. Он имеет следующее интересное свойство: если мы рассмотрим блоки интервалов <math>B_0, B_1, ..., \;</math> где каждый блок <math>B_i \;</math> содержит <math>O(log_{1 + \epsilon} (1 + \frac{1}{\epsilon})) \;</math> последовательных интервалов, то задание j, начинающееся в блоке <math>B_i \;</math>, завершается в пределах следующего блока. Последующие этапы на фазе перемещения заданий гарантируют, что останется не слишком много больших заданий, распространяющихся на следующий блок; это обеспечивает эффективное осуществление динамического программирования.

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

Одна из основных нерешенных задач в этой области заключается в улучшении коэффициентов аппроксимации для планирования заданий с отношениями предшествования на несвязанных или связанных машинах. Следующие задачи заслуживают отдельного упоминания. Наилучшим известным решением задачи <math>1 | prec | \sum w_j C_j \;</math> является алгоритм 2-аппроксимации Холла и др. [8]; улучшение этого коэффициента остается главным открытым вопросом теории планирования. Задача <math>R | prec | \sum_j w_j C_j \;</math>, в которой отношения предшествования формируют произвольный ациклический граф, также представляет высокую важность: единственные известные результаты были получены для случая, когда отношения предшествования образуют цепи [6] или деревья [10].