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

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