Просмотр кода страницы Минимальная длительность выполнения на несвязанных машинах

== Ключевые слова и синонимы ==
Расписание минимальной длины на разных машинах (''Schedule of minimum length on different machines'')
 
== Постановка задачи ==
Рассмотрим следующую задачу планирования. Имеется <math>m</math> параллельных машин и <math>n</math> независимых заданий. Каждое задание должно быть назначено одной из машин. Обработка задания <math>j</math> на машине <math>i</math> требует <math>p_{ij}</math> единиц времени. Цель состоит в том, чтобы найти расписание, которое минимизирует длительность выполнения, определяемую как время, за которое все задания будут выполнены. Эта задача обозначается <math>R||C_{max}</math> в стандартной нотации планирования [6].


Существует несколько важных частных случаев этой задачи: задача об ограниченном назначении с <math>p_{ij} \in \{ 1, \infty \}</math>, идентичные параллельные машины с <math>p_{ij} = p_j</math> и однородные параллельные машины <math>p_{ij} = p_j/s_i</math>, где <math>s_i > 0</math> – скорость машины <math>i</math>. Эти задачи обозначаются соответственно <math>R|p_{ij} \in \{ 1, \infty \}|C_{max}</math>, <math>P||C_{max}</math> и <math>Q||C_{max}</math>. Две последние задачи допускают схемы аппроксимации с полиномиальным временем выполнения [4, 5].


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

<math>(1) \; \sum_{i = 1}^m x_{ij} = 1, j = 1, ..., n</math>,

<math>(2) \; \sum_{j = 1}^n p_{ij} x_{ij} \le T, i = 1, ..., m</math>,

<math>(3) \; x_{ij} = 0</math>, если <math>p_{ij} > T</math>,

<math>(4) \; x_{ij} \in \{ 0, 1 \} \; \forall i, j</math>.


Переменная <math>x_{ij} = 1</math>, если задание <math>j</math> назначено машине <math>i</math>, и <math>x_{ij} = 0</math> в противном случае. Ограничение (1) соответствует назначению заданий. Ограничение (2) ограничивает совокупное время обработки заданий, назначенных одной машине. Ограничение (3) запрещает назначение задания машине, если время его обработки превышает целевую длительность выполнения T.

== Основные результаты ==
'''Теорема 1 (Теорема об округлении). Рассмотрим релаксацию линейного программирования целочисленной программы (1)-(4), достигаемую путем ослабления ограничения целочисленности (4) с помощью ограничения'''

<math>(5) \; x_{ij} \ge 0 \; \forall i, j</math>.

'''Если линейная программа (1)-(3),(5) имеет выполнимое решение для некоторого значения параметра <math>T = T^*</math>, то существует выполнимое решение целочисленной программы (1)-(4) с параметром <math>T = T^* + p_{max}</math>, где <math>p_{max} = max_{i, j} p_{ij}</math>, и такое решение может быть найдено за полиномиальное время.'''
 

Идея доказательства заключается в том, чтобы начать с базисного выполнимого решения линейной программы (1)-(3),(5). Свойства базисных решений подразумевают ограничение на количество дробных переменных, что, в свою очередь, означает, что двудольный граф, определяемый заданиями и машинами, с ребрами, соответствующими дробным переменным, имеет совершенно особенную структуру. Ленстра, Шмойс и Тардос [7] показали, что можно округлить дробные ребра таким образом, что каждая вершина, представляющая машину, имеет не более одного ребра (переменной), округленного в большую сторону, из чего следует ограничение на длительность выполнения.


Из теоремы 1 в сочетании с бинарным поиском по параметру <math>T</math> проистекает

'''Следствие 1'''. Существует алгоритм 2-аппроксимации для задачи минимизации длительности выполнения на несвязанных параллельных машинах, который работает за время, полиномиальное от размера входных данных.


Ленстра, Шмойс и Тардос [7] доказали результат о неаппроксимируемости, который справедлив даже для случая задачи об ограниченном назначении.


'''Теорема 2. Для каждого <math>\rho < 3/2</math> не существует полиномиального алгоритма <math>\rho</math>-аппроксимации для задачи минимизации длительности выполнения на несвязанных параллельных машинах, за исключением случая P = NP.'''


'''Обобщения'''

Естественным обобщением задачи планирования является добавление дополнительных требований к ресурсам <math>\sum_{i, j} c_{ij} x_{ij} \le B</math>, т. е. существует стоимость <math>c_{ij}</math>, связанная с назначением задания <math>i</math> машине <math>j</math>. Цель состоит в том, чтобы найти назначение заданий машинам с общей стоимостью не более <math>B</math>, минимизирующее длительность выполнения. Эта задача известна как обобщенная задача о назначении. Шмойс и Тардос [8] доказали аналогичную теорему об округлении, ведущую к алгоритму 2-аппроксимации.


Еще более общая задача возникает, когда каждая машина <math>i</math> имеет несколько режимов <math>s = 1, ..., k</math> для обработки задания <math>j</math>. Каждый режим имеет время обработки <math>p_{ijs}</math> и связанную с ним стоимость <math>c_{ijs}</math>. Цель состоит в том, чтобы найти распределение заданий по машинам и режимам с общей стоимостью не более <math>B</math>, минимизирующее длительность выполнения. Рассмотрим следующую аналогичную формулировку задачи в формате целочисленного программирования:

<math>(6) \; \sum_{i = 1}^m \sum_{s = 0}^k x_{ijs} = 1,j = 1, ..., n</math>,

<math>(7) \; \sum_{j = 1}^n \sum_{s = 0}^k x_{ijs} p_{ijs} \le T, i = 1, ..., m</math>,

<math>(8) \; \sum_{j = 1}^n \sum_{i = 1}^m \sum_{s = 0}^k x_{ijs} c_{ijs} \le B</math>,

<math>(9) \; x_{ijs} = 0</math>, если <math>p_{ijs} > T</math>,

<math>(10) \; x_{ijs} \in \{ 0, 1 \} \; \forall i, j, s</math>.


'''Теорема 3 (Общая теорема об округлении). Рассмотрим релаксацию линейного программирования целочисленной программы (6)-(10), достигаемую путем ослабления ограничения целочисленности (10) с помощью ограничения'''

<math>(11) \; x_{ijs} \ge 0 \; \forall i, j, s</math>.


Если линейная программа (6)-(9), (11) имеет выполнимое решение для некоторого значения параметра <math>T = T^*</math>, то существует выполнимое решение целочисленной программы (6)-(10) с параметром <math>T = T^* + p_{max}</math>, где <math>p_{max} = max_{i, j, s} p_{ijs}</math>, и такое решение может быть найдено за полиномиальное время.


Рандомизированная версия этой теоремы была первоначально доказана Ганди, Хуллером, Партасаратхи и Сринивасаном [2]. Детерминированная версия впервые появилась в работе [3].

== Применение ==
Планирование работы несвязанных параллельных машин является одной из основных моделей планирования, имеющих множество промышленных вариантов применения – см., например, [1, 9]. Теорема округления Ленстры-Шмойса-Тардос и ее обобщения нашли многочисленные способы применения в проектировании и анализе алгоритмов аппроксимации, где довольно часто приходится решать обобщенную задачу о назначении в качестве подпрограммы.

== Открытые вопросы ==
Наиболее интересной нерешенной проблемой является устранение разрыва между положительными (следствие 1) и отрицательными (теорема 2) результатами для <math>R||C_{max}</math>. Очень простой пример показывает, что разрыв целостности релаксации линейного программирования (1)-(3), (5) равен 2, и поэтому для улучшения 2-аппроксимации необходима более сильная линейная программа.


Этот пример состоит из <math>m(T - 1)</math> заданий, таких, что для каждого <math>i \in 1, ..., m</math> время обработки <math>p_{ij} = 1</math> для <math>j = (T - 1)(i - 1) + 1, ..., (T - 1)i</math> и <math>p_{ij} = \infty</math> в противном случае. Иными словами, каждая машина имеет <math>T - 1</math> заданий с единичным временем обработки, которые не могут быть обработаны на любой другой машине. Кроме того, есть одно большое задание <math>b</math> со временем обработки <math>p_{ib} = T</math> для <math>i = 1, ..., m</math>.


Одним из способов определения более сильной линейной программы является определение переменных <math>x_{iS}</math> для каждого возможного множества заданий <math>S</math>. Переменная <math>x_{iS} = 1</math>, если множество заданий <math>S</math> назначено для обработки на машине <math>i</math>. Множество заданий <math>S</math> является выполнимым для машины <math>i</math>, если <math>\sum_{j \in S} p_{ij} \le T</math>. Обозначим за <math>C_i</math> набор выполнимых множеств для машины <math>i</math>. Рассмотрим следующую релаксацию линейного программирования:

<math>(12) \; \sum_{i, S \in C_i: j \in S} x_{iS} = 1, j = 1, ..., n</math>,

<math>(13) \; \sum_{S \in C_i} x_{iS} = 1, i = 1, ..., m</math>,

<math>(14) \; x_{iS} \ge 0 \; \forall i, S \in C_i</math>.


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

== См. также ==
* [[Минимизация продолжительности потока]]
* [[Списочное планирование]]
* [[Балансировка нагрузки]]
* [[Минимальная продолжительность потока]]
* [[Минимальное время завершения для взвешенной системы]]

== Литература ==
1.	Jeng-Fung, C.: Unrelated parallel machine scheduling with secondary resource constraints. Int. J. Adv. Manuf. Technol. 26, 285-292 (2005)

2.	Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding and its applications to approximation algorithms. J. ACM 53(3), 324-360 (2006)

3.	Grigoriev, A., Sviridenko, M., Uetz, M.: Machine scheduling with resource dependent processing times. Math. Program. 110(1 B), 209-228 (2002)

4.	Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. Assoc. Comput. Mach. 34(1), 144-162 (1987)

5.	Hochbaum, D.S., Shmoys, D.B.: A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation  approach. SIAM J. Comput.  17(3), 539-551 (1988)

6.	Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: Sequencing and Scheduling: Algorithms and Complexity. In: Graves, S.C., Rinnooy Kan, A.H.G., Zipkin, P.H. (eds.) Logistics of Production and Inventory. Handbooks in Operations Research and Management Science, vol. 4, pp. 445-522. North-Holland, Amsterdam (1993)

7.	Lenstra, J.K., Shmoys, D., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46(3A), 259-271 (1990)

8.	Shmoys, D., Tardos, E.: An approximation algorithm for the generalized assignment problem. Math. Program. 62(3A), 461-474 (1993)

9.	Yu, L., Shih, H., Pfund, M., Carlyle, W., Fowler, J.: Scheduling of unrelated parallel machines: an application to PWB manufacturing. IIETrans. 34,921-931 (2002)