Минимизация продолжительности потока: различия между версиями

Рассмотрим любое задание j данного экземпляра и время t в плане A и обозначим за <math>w_j(t) \;</math> количество времени, проведенного A над выполнением задания j до наступления момента t. Обозначим за <math>x_j(t) = p_j - w_j(t) \;</math> его ''оставшееся время обработки'' в момент t.

Наилучшей известной эвристикой для минимизации средней продолжительности потока при разрешенном вытеснении является эвристика ''«наименьшее оставшееся время обработки»'' (shortest remaining processing time, SRPT). В любое время t эвристика SRPT выполняет «повисшее» задание j, для которого <math>x_j(t) \;</math> минимально. Если вытеснение не разрешено, эта эвристика превращается в эвристику ''«сначала самое короткое задание»'' (shortest job first, SJF): в начале выполнения плана или при завершении задания алгоритм выбирает «повисшее» задание с наименьшим временем обработки и выполняет его до завершения.

Рассматриваемая задача является полиномиально разрешимой на единичном компьютере с допустимым вытеснением [9, 10]. Если вытеснение допускается, то оптимальным для одного компьютера является подход SRPT. На параллельных компьютерах наилучшая известная верхняя граница для случая с разрешенным вытеснением достигается алгоритмом SRPT, который является O(logmin n/m; P)-аппроксимируемым [6], где P – отношение между самым большим и самым малым временем обработки для данного экземпляра. Заметим, что алгоритм SRPT является онлайновым, так что предыдущий результат выполняется также и для онлайнового случая. Кроме того, в [6] было доказано, что в онлайновом случае эта нижняя граница является строгой. Для оффлайнового случая с разрешенным вытеснением не найдено неконстантной нижней границы.