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

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

Также неисследованным остается направление неаппроксимируемости – имеется немало серьезных пробелов между известными гарантиями аппроксимации и коэффициентами сложности для различных классов задач. Например, известно, что задачи <math>R || \sum w_j C_j \;</math> и <math>R | r_j | \sum w_j C_j \;</math> являются сложно-аппроксимируемыми, однако лучшие известные алгоритмы, предложенные Скутеллой [11], имеют коэффициента аппроксимации 3/2 и 2, соответственно. Устранение этих пробелов представляет собой важную задачу.