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

В нотации планирования, введенной Грэмом и др. [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].

Первым этапом преобразования на входе является геометрическое округление, при помощи которого длительность обработки и дата запуска преобразуются в степени значения <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> интервалов после rj. Он имеет следующее интересное свойство: если мы рассмотрим блоки интервалов <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>, завершается в пределах следующего блока. Последующие этапы на фазе перемещения заданий гарантируют, что останется не слишком много больших заданий, распространяющихся на следующий блок; это обеспечивает эффективное осуществление динамического программирования.

Одна из основных нерешенных задач в этой области заключается в улучшении коэффициентов аппроксимации для планирования заданий с отношениями предшествования на несвязанных или связанных машинах. Следующие задачи заслуживают отдельного упоминания. Наилучшим известным решением задачи 1 jprecj P wjCj является алгоритм 2-аппроксимации Холла и др. [8]; улучшение этого коэффициента остается главным открытым вопросом теории планирования. Задача _R|prec| ^ wjCj, в которой отношения предшествования формируют произвольный ациклический граф, также представляет высокую важность: единственные результаты были получены для случая, когда отношения предшествования формируют цепи [6] или деревья [10].

Также неисследованным остается направление неаппроксимируемости – имеется немало серьезных пробелов между известными гарантиями аппроксимации и коэффициентами сложности для различных классов задач. Например, известно, что задачи Rj j P wj Cj и R j rj j P wj Cj являются сложно-аппроксимируемыми, однако лучшие известные алгоритмы, предложенные Скутеллой [11], имеют коэффициента аппроксимации 3/2 и 2, соответственно. Устранение этих пробелов представляет собой важную задачу.