Минимальное время завершения для взвешенной системы

Ключевые слова и синонимы

Среднее время завершения для взвешенной системы

Постановка задачи

Задача нахождения минимального времени завершения для взвешенной системы представляет собой (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, которые соответствуют времени завершения для взвешенной системы и полном времени завершения для невзвешенной системы, соответственно.