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

'''Нотация'''

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