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

Задача заключается в эффективном планировании заданий в системе с множеством ресурсов для обеспечения хорошего качества обслуживания. В литературе по планированию было рассмотрено несколько моделей для моделирования постановки задачи и изучено несколько различных метрик качества. В данной статье рассматривается следующая модель: имеется несколько одинаковых машин, и задания выпускаются с течением времени. Каждое задание характеризуется своим размером, то есть объемом требований по обработке, необходимым ему для выполнения, и временем выпуска, до которого оно не может быть спланировано. В этой модели Леонарди и Раз исследовали задачу минимизации средней продолжительности потока, где продолжительность потока – это длительность времени с момента его выпуска до выполнения требований по обработке. Продолжительность потока также называется временем отклика или длительностью пребывания и является очень естественной и часто используемой метрикой качества расписания.

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