4551
правка
Минимальное время завершения для взвешенной системы: различия между версиями
Перейти к навигации
Перейти к поиску
м
Минимальное время завершения для взвешенной системы (посмотреть исходный код)
Версия от 15:47, 22 сентября 2016
, 22 сентября 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
В нотации планирования, введенной Грэмом и др. [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, которые соответствуют времени завершения для взвешенной системы и полном времени завершения для невзвешенной системы, соответственно. | В нотации планирования, введенной Грэмом и др. [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, которые соответствуют времени завершения для взвешенной системы и полном времени завершения для невзвешенной системы, соответственно. | ||
Некоторые из более простых задач поиска минимального времени завершения для взвешенной системы допускают использование оптимальных решений с полиномиальным временем выполнения. Среди них можно упомянуть задачу PjjPCj, для которой оптимальной является стратегия «самое короткое задание планировать первым»; 1jj PwjCj, для которой оптимальным является следование правилу Смита [ ] (планирование заданий в порядке неубывания значений pj/wj); RjjPCj, которая может быть решена при помощи техник сопоставления [2, 9]. При введении дат запуска даже простейшие классы задач минимизации времени завершения для взвешенной системы становятся строго недетерминированными с полиномиальным временем выполнения (NP-полными). Подход Афрати и др. [ ] заключается в разработке схем аппроксимации с полиномиальным временем выполнения (PTAS) для нескольких классов задач планирования, способствующих минимизации времени завершения для взвешенной системы с указанием дат запуска. До публикации упомянутой работы лучшими решениями для минимизации времени завершения для взвешенной системы с указанием дат запуска были все алгоритмы O(1)-аппроксимации (см., например, [4, 5, 11]); единственный известный PTAS-алгоритм для сильной NP-полной задачи, рассматривающей время завершения для взвешенной системы, предложили Скутелла и Вёгингер [ ], разработавшие PTAS для задачи Pj j P wjCj. Исчерпывающий обзор задач поиска минимального времени завершения для взвешенной системы составили Чекури и Ханна [3]. | Некоторые из более простых задач поиска минимального времени завершения для взвешенной системы допускают использование оптимальных решений с полиномиальным временем выполнения. Среди них можно упомянуть задачу PjjPCj, для которой оптимальной является стратегия «самое короткое задание планировать первым»; 1jj PwjCj, для которой оптимальным является следование правилу Смита [ ] (планирование заданий в порядке неубывания значений pj/wj); RjjPCj, которая может быть решена при помощи техник сопоставления [2, 9]. При введении дат запуска даже простейшие классы задач минимизации времени завершения для взвешенной системы становятся строго недетерминированными с полиномиальным временем выполнения (NP-полными). Подход Афрати и др. [ ] заключается в разработке схем аппроксимации с полиномиальным временем выполнения (PTAS) для нескольких классов задач планирования, способствующих минимизации времени завершения для взвешенной системы с указанием дат запуска. До публикации упомянутой работы лучшими решениями для минимизации времени завершения для взвешенной системы с указанием дат запуска были все алгоритмы O(1)-аппроксимации (см., например, [4, 5, 11]); единственный известный PTAS-алгоритм для сильной NP-полной задачи, рассматривающей время завершения для взвешенной системы, предложили Скутелла и Вёгингер [ ], разработавшие PTAS для задачи Pj j P wjCj. Исчерпывающий обзор задач поиска минимального времени завершения для взвешенной системы составили Чекури и Ханна [3]. | ||
== Основные результаты == | == Основные результаты == | ||