Минимальное время завершения для взвешенной системы: различия между версиями
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
(не показано 6 промежуточных версий 1 участника) | |||
Строка 9: | Строка 9: | ||
Некоторые из более простых классов задач поиска минимального времени завершения для взвешенной системы допускают использование оптимальных решений с полиномиальным временем выполнения. Среди них можно упомянуть задачу <math>P || \sum C_j \;</math>, для которой оптимальной является стратегия «самое короткое задание планировать первым»; <math>1 || \sum w_j C_j \;</math>, для которой оптимальным является следование правилу Смита [13] (планирование заданий в порядке неубывания значений <math>p_j / w_j \;</math>); <math>R || \sum C_j \;</math>, которая может быть решена при помощи техник сопоставления [2, 9]. При введении дат запуска даже простейшие классы задач минимизации времени завершения для взвешенной системы становятся строго недетерминированными с полиномиальным временем выполнения (NP-полными). Подход Афрати и др. [1] заключается в разработке схем | Некоторые из более простых классов задач поиска минимального времени завершения для взвешенной системы допускают использование оптимальных решений с полиномиальным временем выполнения. Среди них можно упомянуть задачу <math>P || \sum C_j \;</math>, для которой оптимальной является стратегия «самое короткое задание планировать первым»; <math>1 || \sum w_j C_j \;</math>, для которой оптимальным является следование правилу Смита [13] (планирование заданий в порядке неубывания значений <math>p_j / w_j \;</math>); <math>R || \sum C_j \;</math>, которая может быть решена при помощи техник сопоставления [2, 9]. При введении дат запуска даже простейшие классы задач минимизации времени завершения для взвешенной системы становятся строго недетерминированными с полиномиальным временем выполнения (NP-полными). Подход Афрати и др. [1] заключается в разработке аппроксимационных схем с полиномиальным временем выполнения (PTAS) для нескольких классов задач планирования, способствующих минимизации времени завершения для взвешенной системы с указанием дат запуска. До публикации упомянутой работы лучшие решения для минимизации времени завершения для взвешенной системы с указанием дат запуска представляли собой алгоритмы O(1)-аппроксимации (см., например, [4, 5, 11]); единственный известный PTAS-алгоритм для сильной NP-полной задачи, рассматривающей время завершения для взвешенной системы, предложили Скутелла и Вёгингер [12], разработавшие PTAS для задачи <math>P || \sum w_j C_j \;</math>. Исчерпывающий обзор задач поиска минимального времени завершения для взвешенной системы составили Чекури и Ханна [3]. | ||
== Основные результаты == | == Основные результаты == | ||
Строка 23: | Строка 23: | ||
Первым этапом преобразования на входе является геометрическое округление, при помощи которого длительность обработки и дата запуска преобразуются в степени значения <math>1 + \epsilon \;</math>, в результате чего общая эффективность снижается не более чем на <math>1 + \epsilon \;</math>. Что еще более важно, этот этап: (1) гарантирует небольшое количество различных значений длительности обработки и даты запуска; (2) позволяет разбивать время на геометрически возрастающие интервалы; и (3) выравнивает даты запуска относительно временных границ начала и конца интервалов. Все | Первым этапом преобразования на входе является ''геометрическое округление'', при помощи которого длительность обработки и дата запуска преобразуются в степени значения <math>1 + \epsilon \;</math>, в результате чего общая эффективность снижается не более чем на <math>1 + \epsilon \;</math>. Что еще более важно, этот этап: (1) гарантирует небольшое количество различных значений длительности обработки и даты запуска; (2) позволяет разбивать время на геометрически возрастающие интервалы; и (3) выравнивает даты запуска относительно временных границ начала и конца интервалов. Все эти полезные свойства могут использоваться алгоритмом динамического программирования. | ||
Вторым этапом преобразования на входе является растягивание по времени, во время которого к плану на всем его протяжении добавляются небольшие объемы времени простоя. Этот этап также увеличивает время завершения не более чем на <math>1 + O (\epsilon) \;</math>, однако он полезен для лучшей организации процесса планирования. В частности, если задание слишком велико (т. е. занимает большую часть интервала, в котором оно выполняется), его можно переместить во время простоя более позднего интервала, в котором оно будет занимать небольшую часть времени. Это гарантирует, что большинство заданий будут иметь небольшой размер по сравнению с продолжительностью интервала, в котором они выполняются, что значительно упрощает составление плана. Следующим этапом будет перемещение заданий. Рассмотрим разбиение временного интервала <math>[ 0, \infty ) \;</math> на интервалы формы <math>I_x = [(1 + \epsilon)^x,(l + \epsilon)^{x + 1}) \;</math> для целочисленных значений x. Этап перемещения заданий гарантирует, что существует почти субоптимальный план, в котором каждое задание j выполняется в пределах <math>O(log_{1 + \epsilon} (1 + \frac{1}{\epsilon})) \;</math> интервалов после | Вторым этапом преобразования на входе является ''растягивание по времени'', во время которого к плану на всем его протяжении добавляются небольшие объемы времени простоя. Этот этап также увеличивает время завершения не более чем на <math>1 + O (\epsilon) \;</math>, однако он полезен для лучшей организации процесса планирования. В частности, если задание слишком велико (т. е. занимает большую часть интервала, в котором оно выполняется), его можно переместить во время простоя более позднего интервала, в котором оно будет занимать небольшую часть времени. Это гарантирует, что большинство заданий будут иметь небольшой размер по сравнению с продолжительностью интервала, в котором они выполняются, что значительно упрощает составление плана. Следующим этапом будет ''перемещение заданий''. Рассмотрим разбиение временного интервала <math>[ 0, \infty ) \;</math> на интервалы формы <math>I_x = [(1 + \epsilon)^x,(l + \epsilon)^{x + 1}) \;</math> для целочисленных значений x. Этап перемещения заданий гарантирует, что существует почти субоптимальный план, в котором каждое задание j выполняется в пределах <math>O(log_{1 + \epsilon} (1 + \frac{1}{\epsilon})) \;</math> интервалов после <math>r_j \;</math>. Он имеет следующее интересное свойство: если мы рассмотрим блоки интервалов <math>B_0, B_1, ..., \;</math> где каждый блок <math>B_i \;</math> содержит <math>O(log_{1 + \epsilon} (1 + \frac{1}{\epsilon})) \;</math> последовательных интервалов, то задание j, начинающееся в блоке <math>B_i \;</math>, завершается в пределах следующего блока. Последующие этапы на фазе перемещения заданий гарантируют, что останется не слишком много больших заданий, распространяющихся на следующий блок; это обеспечивает эффективное осуществление динамического программирования. | ||
Строка 35: | Строка 35: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Одна из основных нерешенных задач в этой области заключается в улучшении коэффициентов аппроксимации для планирования заданий с отношениями предшествования на несвязанных или связанных машинах. Следующие задачи заслуживают отдельного упоминания. Наилучшим известным решением задачи <math>1 | prec | \sum w_j C_j \;</math> является алгоритм 2-аппроксимации Холла и др. [8]; улучшение этого коэффициента остается главным открытым вопросом теории планирования. Задача <math>R | prec | \sum_j w_j C_j \;</math>, в которой отношения предшествования формируют произвольный ациклический граф, также представляет высокую важность: единственные результаты были получены для случая, когда отношения предшествования | Одна из основных нерешенных задач в этой области заключается в улучшении коэффициентов аппроксимации для планирования заданий с отношениями предшествования на несвязанных или связанных машинах. Следующие задачи заслуживают отдельного упоминания. Наилучшим известным решением задачи <math>1 | prec | \sum w_j C_j \;</math> является алгоритм 2-аппроксимации Холла и др. [8]; улучшение этого коэффициента остается главным открытым вопросом теории планирования. Задача <math>R | prec | \sum_j w_j C_j \;</math>, в которой отношения предшествования формируют произвольный ациклический граф, также представляет высокую важность: единственные известные результаты были получены для случая, когда отношения предшествования образуют цепи [6] или деревья [10]. | ||
Также неисследованным остается направление неаппроксимируемости – имеется немало серьезных пробелов между известными гарантиями аппроксимации и коэффициентами сложности для различных классов задач. Например, известно, что задачи <math>R || \sum w_j C_j \;</math> и <math>R | r_j | \sum w_j C_j \;</math> являются сложно-аппроксимируемыми, однако лучшие известные алгоритмы, предложенные Скутеллой [11], имеют | Также неисследованным остается направление неаппроксимируемости – имеется немало серьезных пробелов между известными гарантиями аппроксимации и коэффициентами сложности для различных классов задач. Например, известно, что задачи <math>R || \sum w_j C_j \;</math> и <math>R | r_j | \sum w_j C_j \;</math> являются сложно-аппроксимируемыми, однако лучшие известные алгоритмы, предложенные Скутеллой [11], имеют коэффициенты аппроксимации 3/2 и 2, соответственно. Устранение этих пробелов представляет собой важную задачу. | ||
== См. также == | == См. также == | ||
Строка 74: | Строка 74: | ||
13. Smith, W.E.: Various optimizers for single-stage production. Nav. Res. Log. Q. 3, pp. 59-66 (1956) | 13. Smith, W.E.: Various optimizers for single-stage production. Nav. Res. Log. Q. 3, pp. 59-66 (1956) | ||
[[Категория: Совместное определение связанных терминов]] |
Текущая версия от 11:56, 22 ноября 2024
Ключевые слова и синонимы
Среднее время завершения для взвешенной системы
Постановка задачи
Задача нахождения минимального времени завершения для взвешенной системы представляет собой (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].
Основные результаты
Афрати и др. [1] первыми разработали PTAS-алгоритмы для задач поиска минимального времени завершения для взвешенной системы с указанием дат запуска. В таблице 1 приведено время выполнения этих PTAS-алгоритмов.
Результаты, представленные в таблице 1, были получены благодаря тщательному подбору последовательности преобразований на входе и последующему динамическому программированию. Преобразования на входе гарантируют, что входные данные будут иметь нужную структуру, за счет незначительного снижения оптимальности, а динамическое программирование обеспечивает эффективное перечисление всех почти оптимальных решений для хорошо структурированного экземпляра задачи.
Таблица 1. Основные результаты Афрати и др. [1]
Первым этапом преобразования на входе является геометрическое округление, при помощи которого длительность обработки и дата запуска преобразуются в степени значения [math]\displaystyle{ 1 + \epsilon \; }[/math], в результате чего общая эффективность снижается не более чем на [math]\displaystyle{ 1 + \epsilon \; }[/math]. Что еще более важно, этот этап: (1) гарантирует небольшое количество различных значений длительности обработки и даты запуска; (2) позволяет разбивать время на геометрически возрастающие интервалы; и (3) выравнивает даты запуска относительно временных границ начала и конца интервалов. Все эти полезные свойства могут использоваться алгоритмом динамического программирования.
Вторым этапом преобразования на входе является растягивание по времени, во время которого к плану на всем его протяжении добавляются небольшие объемы времени простоя. Этот этап также увеличивает время завершения не более чем на [math]\displaystyle{ 1 + O (\epsilon) \; }[/math], однако он полезен для лучшей организации процесса планирования. В частности, если задание слишком велико (т. е. занимает большую часть интервала, в котором оно выполняется), его можно переместить во время простоя более позднего интервала, в котором оно будет занимать небольшую часть времени. Это гарантирует, что большинство заданий будут иметь небольшой размер по сравнению с продолжительностью интервала, в котором они выполняются, что значительно упрощает составление плана. Следующим этапом будет перемещение заданий. Рассмотрим разбиение временного интервала [math]\displaystyle{ [ 0, \infty ) \; }[/math] на интервалы формы [math]\displaystyle{ I_x = [(1 + \epsilon)^x,(l + \epsilon)^{x + 1}) \; }[/math] для целочисленных значений x. Этап перемещения заданий гарантирует, что существует почти субоптимальный план, в котором каждое задание j выполняется в пределах [math]\displaystyle{ O(log_{1 + \epsilon} (1 + \frac{1}{\epsilon})) \; }[/math] интервалов после [math]\displaystyle{ r_j \; }[/math]. Он имеет следующее интересное свойство: если мы рассмотрим блоки интервалов [math]\displaystyle{ B_0, B_1, ..., \; }[/math] где каждый блок [math]\displaystyle{ B_i \; }[/math] содержит [math]\displaystyle{ O(log_{1 + \epsilon} (1 + \frac{1}{\epsilon})) \; }[/math] последовательных интервалов, то задание j, начинающееся в блоке [math]\displaystyle{ B_i \; }[/math], завершается в пределах следующего блока. Последующие этапы на фазе перемещения заданий гарантируют, что останется не слишком много больших заданий, распространяющихся на следующий блок; это обеспечивает эффективное осуществление динамического программирования.
Точное содержание этапов алгоритмов и их анализ довольно сложны; здесь приводится только их упрощенное схематическое представление. Подробнее об этом – в [1] и [3].
Применение
Многие задачи оптимизации в области параллельных вычислений и исследования операций можно сформулировать в виде задач планирования вычислительных машин. При введении отношений предшествования между задачами нахождение времени завершения для взвешенной системы может выступать в качестве более общей цели по сравнению с широко распространенным нахождением периода обработки, и потому оказывается важным.
Открытые вопросы
Одна из основных нерешенных задач в этой области заключается в улучшении коэффициентов аппроксимации для планирования заданий с отношениями предшествования на несвязанных или связанных машинах. Следующие задачи заслуживают отдельного упоминания. Наилучшим известным решением задачи [math]\displaystyle{ 1 | prec | \sum w_j C_j \; }[/math] является алгоритм 2-аппроксимации Холла и др. [8]; улучшение этого коэффициента остается главным открытым вопросом теории планирования. Задача [math]\displaystyle{ R | prec | \sum_j w_j C_j \; }[/math], в которой отношения предшествования формируют произвольный ациклический граф, также представляет высокую важность: единственные известные результаты были получены для случая, когда отношения предшествования образуют цепи [6] или деревья [10].
Также неисследованным остается направление неаппроксимируемости – имеется немало серьезных пробелов между известными гарантиями аппроксимации и коэффициентами сложности для различных классов задач. Например, известно, что задачи [math]\displaystyle{ R || \sum w_j C_j \; }[/math] и [math]\displaystyle{ R | r_j | \sum w_j C_j \; }[/math] являются сложно-аппроксимируемыми, однако лучшие известные алгоритмы, предложенные Скутеллой [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)