R2Cmax — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 5: Строка 5:
 
и втором станке различное. Нужно минимизировать время завершения всех работ.}}
 
и втором станке различное. Нужно минимизировать время завершения всех работ.}}
  
Задача <tex>R2 \mid \mid C_{max}</tex> является [[Классы_NP_и_Σ₁|<tex>\mathrm{NP}</tex>-полной задачей]]. Доказательство смотри в книге<ref>* J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1:343–362, 1977.</ref>.
+
Задача <tex>R2 \mid \mid C_{max}</tex> является [[Классы_NP_и_Σ₁#def1|<tex>\mathrm{NP}</tex>-полной задачей]]<ref>* J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1:343–362, 1977.</ref>.
  
 
==Неэффективное решение==
 
==Неэффективное решение==
Строка 23: Строка 23:
 
Таким образом: <tex>dp[i + 1][j] = \min(dp[i][j] + p_2[i + 1], dp[i][j - p_1[i + 1]])</tex>
 
Таким образом: <tex>dp[i + 1][j] = \min(dp[i][j] + p_2[i + 1], dp[i][j - p_1[i + 1]])</tex>
  
Тогда ответом на задачу будет минимум среди всех <tex>\max(j, dp[n][j])</tex>.
+
Тогда ответом на задачу будет <tex>\min\limits_{j}(\max(j, dp[n][j]))</tex>. Другими словами мы перебираем время работы на первом станке и смотрим сколько ещё потребуется работать на втором станке. Время выполнения всех работ {{---}} это максимум из этих двух величин. И в конце из всех времен выбираем минимальное.
  
Так же можно заметить, что во время каждой итерации алгоритма используется только два столбца массива <tex> dp </tex>. Это позволяет уменьшить использование памяти с <tex>O(n \cdot maxTime)</tex> до <tex> O(maxTime)</tex>.
+
Также можно заметить, что во время каждой итерации алгоритма используется только два столбца массива <tex> dp </tex>. Это позволяет уменьшить использование памяти с <tex>O(n \cdot maxTime)</tex> до <tex> O(maxTime)</tex>.
  
 
==Доказательство корректности алгоритма==
 
==Доказательство корректности алгоритма==
Строка 46: Строка 46:
 
==Псевдокод==
 
==Псевдокод==
 
  <font color=green>// Функция принимает количество работ n, список времён выполнения работ на первом станке p1 и времён выполнения на втором станке p2.<br>// Функция возвращает минимальное время выполнения всех работ на двух станках.</font>
 
  <font color=green>// Функция принимает количество работ n, список времён выполнения работ на первом станке p1 и времён выполнения на втором станке p2.<br>// Функция возвращает минимальное время выполнения всех работ на двух станках.</font>
  '''function''' getCmax(n : int, p1 : int[], p2 : int[]): int
+
  '''function''' getCmax(p1 : '''int'''[n], p2 : '''int'''[n]): '''int'''
     int maxTime = 0
+
     '''int''' maxTime = 0
     '''for''' i = 0 .. n - 1:
+
     '''for''' i = 0 .. n - 1
 
       maxTime += p1[i]
 
       maxTime += p1[i]
     int[][] dp
+
     '''int'''[][] dp
 
     fill(dp, <tex>\infty</tex>)
 
     fill(dp, <tex>\infty</tex>)
 
     dp[0][0] = 0
 
     dp[0][0] = 0
     '''for''' i = 0 .. n - 1:
+
     '''for''' i = 0 .. n - 1
       '''for''' j = 0 .. maxTime:
+
       '''for''' j = 0 .. maxTime
 
           dp[i + 1][j] = min(dp[i][j - p1[i + 1]], dp[i][j] + p2[i + 1])
 
           dp[i + 1][j] = min(dp[i][j - p1[i + 1]], dp[i][j] + p2[i + 1])
     int answer = <tex>\infty</tex>
+
     '''int''' answer = <tex>\infty</tex>
     '''for''' j = 0 .. maxTime:
+
     '''for''' j = 0 .. maxTime
 
       answer = min(answer, max(j, dp[n][j]))
 
       answer = min(answer, max(j, dp[n][j]))
 
     '''return''' answer
 
     '''return''' answer

Версия 17:06, 22 мая 2016

[math]R2 \mid\mid C_{max} [/math]


Задача:
Дано два разных неоднородных станка, которые работают параллельно. Есть [math]n[/math] работ, время выполнения которых на первом и втором станке различное. Нужно минимизировать время завершения всех работ.


Задача [math]R2 \mid \mid C_{max}[/math] является [math]\mathrm{NP}[/math]-полной задачей[1].

Неэффективное решение

Переберём все битовые маски длины [math]n[/math]. Для каждой маски вычислим завершение последней работы. Работы будем выполнять следующим образом, если на [math]i[/math] -й позиции стоит [math]0[/math], то [math]i[/math] -ая работа будет выполняться на первом станке, иначе на втором. Среди всех масок выберем ту, у которой [math]C_{max}[/math] минимальный.

Время работы алгоритма [math]O(n \cdot 2^n)[/math]

Эффективное решение

Применим для решения данной задачи динамическое программирование.

Будем считать массив [math]dp[i][j][/math], в котором будем хранить минимально время выполнения работ на втором станке, где [math]i[/math] означает, что мы рассмотрели [math]i[/math] работ, а [math]j[/math] — с каким временем выполнения работ на первом станке. Тогда [math]j[/math] не превосходит суммы выполнения работ на первом станке. Назовем эту сумму [math]maxTime[/math].

Изначальное значение [math]dp[0][0] = 0[/math], а всё остальную таблицу проинициализируем бесконечностью.

Допустим мы посчитали динамику для [math]i[/math] работ. Теперь надо пересчитать её для [math](i + 1)[/math]-ой работы. Переберём время выполнения работ на первом станке и посчитаем какое минимально время выполнения мы можем получить на втором станке при фиксированном времени на первом. Так как [math](i + 1)[/math]-ю работу мы можем выполнить либо на первом станке, либо на втором, то [math] dp[i + 1][j][/math] надо прорелаксировать значением [math]dp[i][j - p_1[i + 1]] [/math], что соответсвует выполнению работы на первом станке, и значением [math] dp[i][j]+p_2[i + 1][/math] (выполнение на втором станке).

Таким образом: [math]dp[i + 1][j] = \min(dp[i][j] + p_2[i + 1], dp[i][j - p_1[i + 1]])[/math]

Тогда ответом на задачу будет [math]\min\limits_{j}(\max(j, dp[n][j]))[/math]. Другими словами мы перебираем время работы на первом станке и смотрим сколько ещё потребуется работать на втором станке. Время выполнения всех работ — это максимум из этих двух величин. И в конце из всех времен выбираем минимальное.

Также можно заметить, что во время каждой итерации алгоритма используется только два столбца массива [math] dp [/math]. Это позволяет уменьшить использование памяти с [math]O(n \cdot maxTime)[/math] до [math] O(maxTime)[/math].

Доказательство корректности алгоритма

Теорема:
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
Доказательство:
[math]\triangleright[/math]

Корректность расписания, составленного алгоритмом очевидна. Надо доказать его оптимальность.

Пусть расписание, составленное этим алгоритмом [math]S[/math] не оптимальное и в конце работы алгоритма минимум достигается в [math]\max(time, d[n][time])[/math]. Рассмотрим оптимальное решение [math]O[/math].

Рассмотрим произвольную работу, выполненную на первом станке в оптимальном расписании, но на втором в расписании, составленном алгоритмом. Пусть у этой работы номер [math]i[/math]. Если её выполнить на первом станке, то время окончания всех работ будет [math]\max(time + p_{1}[i], d[n][time + p_{1}[i]])[/math]. Однако [math]\max(time, d[n][time]) \leqslant \max(time + p_{1}[i], d[n][time + p_{1}[i]])[/math]

Рассмотрим произвольную работу, выполненную в оптимальном расписании на втором станке, но на первом в расписании, составленном алгоритмом. Пусть номер этой работы [math]j[/math]. Если выполнять эту работу на втором станке, то время выполнения всех работ будет [math]\max(time - p_{1}[j], d[n][time - p_{1}[j]])[/math]. Но [math] \max(time, d[n][time]) \leqslant \max(time - p_{1}[j], d[n][time - p_{1}[j]]) [/math].

В итоге если превратить решение [math]S[/math] в решение [math]S'[/math] эквивалентное [math]O[/math], то ответ [math]S[/math] не будет превосходить ответ [math]S'[/math]. Тогда расписание [math]S[/math] оптимальное.
[math]\triangleleft[/math]

Псевдокод

// Функция принимает количество работ n, список времён выполнения работ на первом станке p1 и времён выполнения на втором станке p2.
// Функция возвращает минимальное время выполнения всех работ на двух станках.
function getCmax(p1 : int[n], p2 : int[n]): int int maxTime = 0 for i = 0 .. n - 1 maxTime += p1[i] int[][] dp fill(dp, [math]\infty[/math]) dp[0][0] = 0 for i = 0 .. n - 1 for j = 0 .. maxTime dp[i + 1][j] = min(dp[i][j - p1[i + 1]], dp[i][j] + p2[i + 1]) int answer = [math]\infty[/math] for j = 0 .. maxTime answer = min(answer, max(j, dp[n][j])) return answer

Время работы

Время работы [math]O(n \cdot maxTime)[/math] — псевдополиномиальный алгоритм. Кроме того, если время выполнения работ, будет вещественные числа, то придется приводить их до целых, либо считать приблежённое значения.

См. также

Примечания

  1. * J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1:343–362, 1977.

Источники информации

  • J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, стр. 358–360, 1977.