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

В нотации планирования, введенной Грэмом и др. [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_{j \in J} w_j C_j \;</math> либо <math>\sum_{j \in J} C_j \;</math>, которые соответствуют времени завершения для взвешенной системы и полному времени завершения для невзвешенной системы, соответственно.

Некоторые из более простых классов задач поиска минимального времени завершения для взвешенной системы допускают использование оптимальных решений с полиномиальным временем выполнения. Среди них можно упомянуть задачу PjjPCj, для которой оптимальной является стратегия «самое короткое задание планировать первым»; 1jj PwjCj, для которой оптимальным является следование правилу Смита [ ] (планирование заданий в порядке неубывания значений pj/wj); RjjPCj, которая может быть решена при помощи техник сопоставления [2, 9]. При введении дат запуска даже простейшие классы задач минимизации времени завершения для взвешенной системы становятся строго недетерминированными с полиномиальным временем выполнения (NP-полными). Подход Афрати и др. [ ] заключается в разработке схем аппроксимации с полиномиальным временем выполнения (PTAS) для нескольких классов задач планирования, способствующих минимизации времени завершения для взвешенной системы с указанием дат запуска. До публикации упомянутой работы лучшими решениями для минимизации времени завершения для взвешенной системы с указанием дат запуска были все алгоритмы O(1)-аппроксимации (см., например, [4, 5, 11]); единственный известный PTAS-алгоритм для сильной NP-полной задачи, рассматривающей время завершения для взвешенной системы, предложили Скутелла и Вёгингер [ ], разработавшие PTAS для задачи Pj j P wjCj. Исчерпывающий обзор задач поиска минимального времени завершения для взвешенной системы составили Чекури и Ханна [3].