4501
правка
Минимальное время завершения для взвешенной системы: различия между версиями
Перейти к навигации
Перейти к поиску
Минимальное время завершения для взвешенной системы (посмотреть исходный код)
Версия от 22:53, 18 сентября 2016
, 18 сентября 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача нахождения минимального времени завершения для взвешенной системы представляет собой (1) набор J из n заданий, каждому из которых присвоены положительный вес (wj для j 2 J) и дата запуска, ранее которой это задание не может быть спланировано; (2) набор из m вычислительных машин, каждая из которых может обрабатывать не более одного задания в одно и то же время; (3) произвольный набор положительных значений fpi;jg, где рц обозначает время обработки задания j на машине i. План представляет собой назначение заданий машинам и выбор порядка их обработки. Обозначим за Cj время завершения задания j в рамках выполнения конкретного плана. Определим время завершения для взвешенной системы как Pj2J wjCj. Задача заключается в вычислении плана, имеющего минимальное время завершения. | |||
В нотации планирования, введенной Грэмом и др. [7], задача планирования задается триплетом a j f$ j у, где a обозначает машинную среду, f$ – дополнительные ограничения для заданий, а у – целевую функцию. В данном случае нас главным образом будут интересовать значения параметра a, равные 1, P, R или Rm, которые означают, соответственно, одну машину, идентичные параллельные машины (например, для фиксированного задания j и для каждой машины i pi,j равно значению pj, независимому от i), несвязанные машины (значения pi,j зависят и от задания i, и от машины j) и фиксированное количество m (не являющееся компонентом входных данных) несвязанных машин. Поле f$ принимает следующие значения: rj обозначает, что у заданий имеются даты запуска; pmtn – что разрешено вытеснение заданий; prec – что задача может включать отношения предшествования между заданиями, что также налагает ограничения на составление плана. Поле у содержит значения P wjCj либо P Cj, которые соответствуют времени завершения для взвешенной системы и полном времени завершения для невзвешенной системы, соответственно. | |||