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

В нотации планирования, введенной Грэмом и др. [7], задача планирования задается триплетом <math>\alpha | \beta | \gamma \;</math>, где <math>\alpha \;</math> обозначает машинную среду, <math>\beta \;</math> – дополнительные ограничения для заданий, а <math>\gamma \;</math> – целевую функцию. В данном случае нас главным образом будут интересовать значения параметра <math>\alpha \;</math>, равные 1, P, R или Rm, которые означают, соответственно, одну машину, идентичные параллельные машины (то есть для фиксированного задания j и для каждой машины i <math>p_{i,j} \;</math> равно значению <math>p_j \;</math>, независимому от i), несвязанные машины (значения <math>p_{i,j} \;</math> зависят и от задания i, и от машины j) и фиксированное количество m (не являющееся компонентом входных данных) несвязанных машин. Поле <math>\beta \;</math> принимает следующие значения: <math>r_j \;</math> обозначает, что у заданий имеются даты запуска; pmtn – что разрешено вытеснение заданий; prec – что задача может включать отношения предшествования между заданиями, что также налагает ограничения на составление плана. Поле <math>\gamma \;</math> содержит значения <math>\sum w_j C_j \;</math> либо <math>\sum C_j \;</math>, которые соответствуют времени завершения для взвешенной системы и полному времени завершения для невзвешенной системы, соответственно.