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

Эвристики «сначала самое короткое задание» возникают в задачах упорядочения, целью которых является минимизация воспринимаемой задержки для пользователей в многопользовательской или многозадачной системе. В этой задаче алгоритм должен спланировать множество заданий для пула из m идентичных компьютеров. Для каждого задания известны дата запуска и продолжительность обработки. Цель заключается в минимизации среднего времени, потраченного на выполнение задания системой. Это обычно считается подходящей метрикой качества услуги, предоставляемой системой интерактивным пользователям. Формальное определение задачи оптимизации выглядит следующим образом.

Множество m идентичных компьютеров и множество n заданий 1, 2, ..., n. Каждому заданию j присвоены дата запуска <math>r_j \;</math> и продолжительность обработки <math>p_j \;</math>. Обозначим за <math>\mathcal{I}</math> множество допустимых экземпляров входных данных.

Можно также сделать предположения о знании алгоритмом продолжительности обработки каждого задания. В частности, стоит иметь в виду важный случай, часто встречающийся в практических приложениях, в котором pj полностью неизвестно онлайновому алгоритму до того момента, как выполнение задания будет полностью завершено (''отсутствие предвидения'') [1, 3].