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

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