Аноним

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

Материал из WEGA
Нет описания правки
Строка 6: Строка 6:




Дано:
'''Дано:'''


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




Цель:
'''Цель:'''


Цель заключается в минимизации продолжительности среднего потока (или среднего времени отклика) заданий. Обозначим за Cj время завершения выполнения задания j системой. Продолжительность потока или время отклика Fj задания j определяется как Fj = Cj — rj. Цель заключается в минимизации значения
Цель заключается в минимизации продолжительности ''среднего потока'' (или ''среднего времени отклика'') заданий. Обозначим за <math>C_j \;</math> время завершения выполнения задания j системой. Продолжительность потока или время отклика <math>F_j \;</math> задания j определяется как <math>F_j = C_j - r_j \;</math>. Цель заключается в минимизации значения


mm —  и  j=1 Fj.
<math>min \frac{1}{n} \sum_{j = 1}^n F_j</math>.




Поскольку n является частью входных данных, задача эквивалентна минимизации общей продолжительности потока, т. е.
Поскольку n является частью входных данных, задача эквивалентна минимизации ''общей'' продолжительности потока, т. е. <math>\sum_{j = 1}^n F_j</math>.


Оффлайновые и онлайновые конфигурации
'''Оффлайновые и онлайновые конфигурации'''


В оффлайновой конфигурации экземпляр входных данных полностью известен алгоритму. В частности, для любого значения j = 1... n алгоритму известны rj и pj.
В оффлайновой конфигурации экземпляр входных данных полностью известен алгоритму. В частности, для любого значения j = 1... n алгоритму известны rj и pj.
4551

правка