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

В нотации планирования, введенной Грэмом и др. [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, которые соответствуют времени завершения для взвешенной системы и полном времени завершения для невзвешенной системы, соответственно.