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

Ключевые слова и синонимы

Среднее время завершения для взвешенной системы

Постановка задачи

Задача нахождения минимального времени завершения для взвешенной системы представляет собой (1) набор J из n заданий, каждому из которых присвоены положительный вес ([math]\displaystyle{ w_j \; }[/math] для [math]\displaystyle{ j \in J \; }[/math]) и дата запуска [math]\displaystyle{ r_j \; }[/math], ранее которой это задание не может быть спланировано; (2) набор из m вычислительных машин, каждая из которых может обрабатывать не более одного задания в одно и то же время; (3) произвольный набор положительных значений [math]\displaystyle{ \{ p_{i, j} \} \; }[/math], где [math]\displaystyle{ p_{i, j} \; }[/math] обозначает время обработки задания j на машине i. План представляет собой назначение заданий машинам и выбор порядка их обработки. Обозначим за [math]\displaystyle{ C_j \; }[/math] время завершения задания j в рамках выполнения конкретного плана. Определим время завершения для взвешенной системы как [math]\displaystyle{ \sum_{j \in J} w_j C_j \; }[/math]. Задача заключается в вычислении плана, имеющего минимальное время завершения.

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

Некоторые из более простых классов задач поиска минимального времени завершения для взвешенной системы допускают использование оптимальных решений с полиномиальным временем выполнения. Среди них можно упомянуть задачу [math]\displaystyle{ P || \sum C_j \; }[/math], для которой оптимальной является стратегия «самое короткое задание планировать первым»; [math]\displaystyle{ 1 || \sum w_j C_j \; }[/math], для которой оптимальным является следование правилу Смита [13] (планирование заданий в порядке неубывания значений [math]\displaystyle{ p_j / w_j \; }[/math]); [math]\displaystyle{ R || \sum C_j \; }[/math], которая может быть решена при помощи техник сопоставления [2, 9]. При введении дат запуска даже простейшие классы задач минимизации времени завершения для взвешенной системы становятся строго недетерминированными с полиномиальным временем выполнения (NP-полными). Подход Афрати и др. [1] заключается в разработке схем аппроксимации с полиномиальным временем выполнения (PTAS) для нескольких классов задач планирования, способствующих минимизации времени завершения для взвешенной системы с указанием дат запуска. До публикации упомянутой работы лучшими решениями для минимизации времени завершения для взвешенной системы с указанием дат запуска были все алгоритмы O(1)-аппроксимации (см., например, [4, 5, 11]); единственный известный PTAS-алгоритм для сильной NP-полной задачи, рассматривающей время завершения для взвешенной системы, предложили Скутелла и Вёгингер [12], разработавшие PTAS для задачи [math]\displaystyle{ P || \sum w_j C_j \; }[/math]. Исчерпывающий обзор задач поиска минимального времени завершения для взвешенной системы составили Чекури и Ханна [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].

Применение

Многие задачи оптимизации в области параллельных вычислений и исследования операций можно сформулировать в виде задач планирования вычислительных машин. При введении отношений предшествования между задачами нахождение времени завершения для взвешенной системы может выступать в качестве более общей цели по сравнению с широко распространенным нахождением периода обработки, и потому оказывается важным.

Открытые вопросы

Одна из основных нерешенных задач в этой области заключается в улучшении коэффициентов аппроксимации для планирования заданий с отношениями предшествования на несвязанных или связанных машинах. Следующие задачи заслуживают отдельного упоминания. Наилучшим известным решением задачи 1 jprecj P wjCj является алгоритм 2-аппроксимации Холла и др. [8]; улучшение этого коэффициента остается главным открытым вопросом теории планирования. Задача _R|prec| ^ wjCj, в которой отношения предшествования формируют произвольный ациклический граф, также представляет высокую важность: единственные результаты были получены для случая, когда отношения предшествования формируют цепи [6] или деревья [10].

Также неисследованным остается направление неаппроксимируемости – имеется немало серьезных пробелов между известными гарантиями аппроксимации и коэффициентами сложности для различных классов задач. Например, известно, что задачи Rj j P wj Cj и R j rj j P wj Cj являются сложно-аппроксимируемыми, однако лучшие известные алгоритмы, предложенные Скутеллой [11], имеют коэффициента аппроксимации 3/2 и 2, соответственно. Устранение этих пробелов представляет собой важную задачу.

См. также

• Минимизация продолжительности потока
• Списочное планирование
• Минимальная продолжительность потока
• Минимальный период обработки на несвязанных машинах

Литература

1. Afrati, F.N., Bampis, E., Chekuri, C., Karger, D.R., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Skutella, M., Stein, C., Sviridenko, M.: Approximation schemes for minimizing average weighted completion time with release dates. In: Proc. of Foundations of Computer Science, pp. 32-44 (1999)

2. Bruno, J.L., Coffman, E.G., Sethi, R.: Scheduling independent tasks to reduce mean finishing time. Commun. ACM 17, 382-387(1974)

3. Chekuri, C., Khanna, S.: Approximation algorithms for minimizing weighted completion time. In: J. Y-T. Leung (eds.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, Boca Raton (2004)

4. Chekuri, C., Motwani, R., Natarajan, B., Stein, C.: Approximation techniques for average completion time scheduling. SIAM J.Comput.31(1), 146-166(2001)

5. Goemans, M., Queyranne, M., Schulz, A., Skutella, M., Wang, Y.: Single machine scheduling with release dates. SIAM J. Discret. Math. 15,165-192(2002)

6. Goldberg, L.A., Paterson, M., Srinivasan, A., Sweedyk, E.: Better approximation guarantees for job-shop scheduling. SIAM J. Discret. Math. 14,67-92 (2001)

7. Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math. 5,287-326 (1979)

8. Hall, L.A., Schulz, A.S., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: off-line and on-line approximation algorithms. Math. Oper. Res. 22(3), 513-544 (1997)

9. Horn, W.: Minimizing average flow time with parallel machines. Oper. Res. 21,846-847 (1973)

10. Kumar, V.S.A., Marathe, M.V., Parthasarathy, S., Srinivasan, A.: Scheduling on unrelated machines under tree-like precedence constraints. In: APPROX-RANDOM, pp. 146-157(2005)

11. Skutella, M.: Convex quadratic and semi-definite relaxations in scheduling. J.ACM 46(2), 206-242 (2001)

12. Skutella, M., Woeginger, G.J.: A PTAS for minimizing the weighted sum of job completion times on parallel machines. In: Proc. of 31st Annual ACM Symposium on Theory of Computing (STOC'99), pp. 400^07 (1999)

13. Smith, W.E.: Various optimizers for single-stage production. Nav. Res. Log. Q. 3, pp. 59-66 (1956)