Минимальное время завершения для взвешенной системы
Ключевые слова и синонимы
Среднее время завершения для взвешенной системы
Постановка задачи
Задача нахождения минимального времени завершения для взвешенной системы представляет собой (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, которые соответствуют времени завершения для взвешенной системы и полном времени завершения для невзвешенной системы, соответственно.
Некоторые из более простых задач поиска минимального времени завершения для взвешенной системы допускают использование оптимальных решений с полиномиальным временем выполнения. Среди них можно упомянуть задачу PjjPCj, для которой оптимальной является стратегия «самое короткое задание планировать первым»; 1jj PwjCj, для которой оптимальным является следование правилу Смита [ ] (планирование заданий в порядке неубывания значений pj/wj); RjjPCj, которая может быть решена при помощи техник сопоставления [2, 9]. При введении дат запуска даже простейшие классы задач минимизации времени завершения для взвешенной системы становятся строго недетерминированными с полиномиальным временем выполнения (NP-полными). Подход Афрати и др. [ ] заключается в разработке схем аппроксимации с полиномиальным временем выполнения (PTAS) для нескольких классов задач планирования, способствующих минимизации времени завершения для взвешенной системы с указанием дат запуска. До публикации упомянутой работы лучшими решениями для минимизации времени завершения для взвешенной системы с указанием дат запуска были все алгоритмы O(1)-аппроксимации (см., например, [4, 5, 11]); единственный известный PTAS-алгоритм для сильной NP-полной задачи, рассматривающей время завершения для взвешенной системы, предложили Скутелла и Вёгингер [ ], разработавшие PTAS для задачи Pj j P wjCj. Исчерпывающий обзор задач поиска минимального времени завершения для взвешенной системы составили Чекури и Ханна [3].
Основные результаты
Афрати и др. [ ] первыми разработали PTAS-алгоритмы для задач поиска минимального времени завершения для взвешенной системы с указанием дат запуска. В таблице 1 приведено время выполнения этих PTAS-алгоритмов.
Результаты, представленные в таблице 1, были получены благодаря тщательному подбору последовательности преобразований на входе и последующему динамическому программированию. Преобразования на входе гарантируют, что входные данные будут иметь нужную структуру, за счет незначительного снижения оптимальности, а динамическое программирование обеспечивает эффективное перечисление всех почти оптимальных решений для хорошо структурированного экземпляра задачи.
Первым этапом преобразования на входе является геометрическое округление, при помощи которого длительность обработки и дата запуска преобразуются в степени значения 1 + e, в результате чего общая эффективность снижается не более чем на 1 + e. Что еще более важно, этот этап: (1) гарантирует небольшое количество различных значений длительности обработки и даты запуска; (2) позволяет разбивать время на геометрически возрастающие интервалы; и (3) выравнивает даты запуска относительно временных границ начала и конца интервалов. Это полезные свойства, которые могут использоваться алгоритмом динамического программирования.
Задача Время выполнения схем PTAS
Mn\T,wjq 0(2Р°М?)п+п|одп) PjrjjPwjCj O((m + 1 У0'* е >n + n log n) Pjrj;pmtnjPwjCj 0(2P°Mi-)n+n|ogn) Rmjrj jPwjCj O(f(m, ^)poly(n)) Rmjrj; pmtn jP wjCj O(f(m, j)n + nlogn) RmjjPwjCj O(f(m, j)n + nlogn)
Таблица 1. Основные результаты Афрати и др. [ ]
Вторым этапом преобразования на входе является растягивание по времени, во время которого к плану на всем его протяжении добавляются небольшие объемы времени простоя. Этот этап также увеличивает время завершения не более чем на 1 + O(e), однако он полезен для лучшей организации процесса планирования. В частности, если задание слишком велико (т.е. занимает большую часть интервала, в котором оно выполняется), его можно переместить во время простоя более позднего интервала, в котором оно будет занимать небольшую часть времени. Это гарантирует, что большинство заданий будут иметь небольшой размер по сравнению с продолжительностью интервала, в котором они выполняются, что значительно упрощает составление плана. Следующим этапом будет перемещение заданий. Рассмотрим разбиение временного интервала [0, 1) на интервалы формы Ix = [(1 + e)x,(l + e)x+1) для целочисленных значений x. Этап перемещения заданий гарантирует, что существует практически субоптимальный план, в котором каждое задание j выполняется в пределах O(log1+e(l + j-)) интервалов после rj. Он имеет следующее интересное свойство: если мы рассмотрим блоки интервалов B0, B1, ..., где каждый блок Bi содержит O(log1+e(l + i)) последовательных интервалов, то задание j, начинающееся в блоке Bi, завершается в пределах следующего блока. Последующие этапы на фазе перемещения заданий гарантируют, что останется не слишком много больших заданий, распространяющихся на следующий блок; это обеспечивает эффективное осуществление динамического программирования.
Точное содержание этапов алгоритмов и их анализ довольно сложны; здесь приводится только их упрощенное схематическое представление. Подробнее об этом – в [1] и [3].