Планирование с учетом наименьшего прошедшего времени обработки: различия между версиями

Обозначим за <math>\mathcal{J} = \{ 1, 2, ..., n \}</math> множество заданий во входном экземпляре задачи. Каждое задание j характеризуется временем освобождения <math>r_j</math> и требованием к обработке <math>p_j</math>. В онлайновом режиме задание j сообщается планировщику только в момент времени <math>r_j</math>. Еще одним ограничением является режим ''с отсутствием предвидения'', в котором в момент <math>r_j</math> раскрывается только существование задания j; в частности, <math>p_j</math> планировщику неизвестно до тех пор, пока задание не выполнит свое требование к обработке и не покинет систему. Пусть имеется расписание, тогда время завершения <math>c_j</math> задания – это самое раннее время, в которое задание j получает объем обслуживания <math>p_j</math>. Продолжительность потока <math>f_j</math> задания j определяется как <math>c_j - r_j</math>. Протяженность задания определяется как отношение времени потока к его объему. Протяженностью также называют нормализованную продолжительность потока или замедление, и она является естественной мерой справедливости, поскольку измеряет время ожидания задания на единицу полученного обслуживания. Расписание называется вытесняющим, если задание может быть прервано произвольно, и его выполнение может быть возобновлено позже с момента прерывания без каких-либо штрафов. Хорошо известно, что вытеснение необходимо для получения разумных гарантий времени потока даже в оффлайновом режиме [5].