4551
правка
Минимизация продолжительности потока: различия между версиями
Перейти к навигации
Перейти к поиску
Минимизация продолжительности потока (посмотреть исходный код)
Версия от 12:01, 6 августа 2018
, 6 августа 2018→Постановка задачи
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Дано: | '''Дано:''' | ||
Множество m идентичных компьютеров и множество n заданий 1, 2, | Множество m идентичных компьютеров и множество n заданий 1, 2, ..., n. Каждому заданию j присвоены дата запуска <math>r_j \;</math> и продолжительность обработки <math>p_j \;</math>. Обозначим за <math>\mathcal{I}</math> множество допустимых экземпляров входных данных. | ||
Цель: | '''Цель:''' | ||
Цель заключается в минимизации продолжительности среднего потока (или среднего времени отклика) заданий. Обозначим за | Цель заключается в минимизации продолжительности ''среднего потока'' (или ''среднего времени отклика'') заданий. Обозначим за <math>C_j \;</math> время завершения выполнения задания j системой. Продолжительность потока или время отклика <math>F_j \;</math> задания j определяется как <math>F_j = C_j - r_j \;</math>. Цель заключается в минимизации значения | ||
<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. | ||