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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Эффективное решение)
Строка 5: Строка 5:
 
и втором станке различное. Нужно минимизировать время завершения всех работ.}}
 
и втором станке различное. Нужно минимизировать время завершения всех работ.}}
  
Задача <tex>R2 \mid \mid C_{max}</tex> является <tex>\mathrm{NP}</tex>-полной задачей. Доказательство смотри в книге, указанной в источниках информации.
+
Задача <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>, указанной в источниках информации.
  
 
==Неэффективное решение==
 
==Неэффективное решение==
Строка 15: Строка 15:
 
Применим для решения данной задачи [[Динамическое программирование|динамическое программирование]].
 
Применим для решения данной задачи [[Динамическое программирование|динамическое программирование]].
  
Будем  считать массив <tex>dp[i][j]</tex>, в котором будем хранить минимально время выполнения работ на втором станке, где <tex>i</tex> означает, что мы рассмотрели <tex>i</tex> работ, а <tex>j</tex> с каким временем выполнения работ на первом станке. Тогда <tex>j</tex> не превосходит суммы выполнения работ на первом станке.
+
Будем  считать массив <tex>dp[i][j]</tex>, в котором будем хранить минимально время выполнения работ на втором станке, где <tex>i</tex> означает, что мы рассмотрели <tex>i</tex> работ, а <tex>j</tex> {{---}} с каким временем выполнения работ на первом станке. Тогда <tex>j</tex> не превосходит суммы выполнения работ на первом станке. Назовем эту сумму <tex>maxTime</tex>.
  
 
Изначальное значение <tex>dp[0][0] = 0</tex>, а всё остальную таблицу проинициализируем бесконечностью.
 
Изначальное значение <tex>dp[0][0] = 0</tex>, а всё остальную таблицу проинициализируем бесконечностью.
  
Допустим мы посчитали динамику для <tex>i</tex> работ. Теперь надо пересчитать её для <tex>(i + 1)</tex>-ой работы. Переберём время выполнения работ на первом станке и посчитаем какое минимально время выполнения мы можем получить при на втором станке при фиксированном первом времени. Так как <tex>(i + 1)</tex>-ю работу мы можем выполнить либо на первом станке, либо на втором, то <tex> dp[i + 1][j + p_1[i + 1]]</tex> надо прорелаксировать значением <tex>dp[i][j] </tex>, что соответсвует выполнению работы на первом станке. А <tex>dp[i + 1][j] </tex> релаксируем значением <tex> dp[i][j]+p_2[i + 1]</tex> (выполнение на втором станке).
+
Допустим мы посчитали динамику для <tex>i</tex> работ. Теперь надо пересчитать её для <tex>(i + 1)</tex>-ой работы. Переберём время выполнения работ на первом станке и посчитаем какое минимально время выполнения мы можем получить на втором станке при фиксированном первом времени. Так как <tex>(i + 1)</tex>-ю работу мы можем выполнить либо на первом станке, либо на втором, то <tex> dp[i + 1][j]</tex> надо прорелаксировать значением <tex>dp[i][j - p_1[i + 1]] </tex>, что соответсвует выполнению работы на первом станке, и значением <tex> dp[i][j]+p_2[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>dp[i + 1][j] = \min
 
\begin{cases}
 
dp[i][j] + p_2[i + 1]\\
 
dp[i][j - p_1[i + 1]]\\
 
\end{cases}
 
</tex>
 
  
Тогда ответом на задачу будет минимум среди всех максимумов из <tex>j</tex> и <tex>dp[n][j]</tex>.
+
Тогда ответом на задачу будет минимум среди всех <tex>\max(j, dp[n][j])</tex>.
  
Так же можно заметить, что во время каждой итерации алгоритма используется только два столбца массива <tex> dp </tex>. Это позволяет уменьшить использование памяти до <tex dpi=130> O(\sum\limits_{i = 1}^{n} p_1[i])</tex>.
+
Так же можно заметить, что во время каждой итерации алгоритма используется только два столбца массива <tex> dp </tex>. Это позволяет уменьшить использование памяти с <tex>O(n \cdot maxTime)</tex> до <tex> O(maxTime)</tex>.
  
 
==Доказательство корректности алгоритма==
 
==Доказательство корректности алгоритма==
Строка 41: Строка 35:
 
Корректность расписания, составленного алгоритмом очевидна. Надо доказать его оптимальность.
 
Корректность расписания, составленного алгоритмом очевидна. Надо доказать его оптимальность.
  
Пусть расписание, составленное этим алгоритмом <tex>S</tex> не оптимальное. Пусть в конце работы алгоритма минимум достигается в <tex>\max(time, d[n][time])</tex>. Рассмотрим оптимальное решение <tex>O</tex>.  
+
Пусть расписание, составленное этим алгоритмом <tex>S</tex> не оптимальное и в конце работы алгоритма минимум достигается в <tex>\max(time, d[n][time])</tex>. Рассмотрим оптимальное решение <tex>O</tex>.  
  
 
Рассмотрим произвольную работу, выполненную на первом станке в оптимальном расписании, но на втором в расписании, составленном алгоритмом. Пусть у этой работы номер <tex>i</tex>. Если её выполнить на первом станке, то время окончания всех работ будет <tex>\max(time + p_{1}[i], d[n][time + p_{1}[i]])</tex>. Однако <tex>\max(time, d[n][time]) \leqslant \max(time + p_{1}[i], d[n][time + p_{1}[i]])</tex>
 
Рассмотрим произвольную работу, выполненную на первом станке в оптимальном расписании, но на втором в расписании, составленном алгоритмом. Пусть у этой работы номер <tex>i</tex>. Если её выполнить на первом станке, то время окончания всех работ будет <tex>\max(time + p_{1}[i], d[n][time + p_{1}[i]])</tex>. Однако <tex>\max(time, d[n][time]) \leqslant \max(time + p_{1}[i], d[n][time + p_{1}[i]])</tex>
Строка 51: Строка 45:
  
 
==Псевдокод==
 
==Псевдокод==
  <font color=green>//Функция принимает количество работ n, список времён выполнения работ на первом станке p1 и времён выполнения на втором станке p2.<br>//Функция возвращает минимальное время выполнения всех работ на двух станках.</font>
+
  <font color=green>// Функция принимает количество работ n, список времён выполнения работ на первом станке p1 и времён выполнения на втором станке p2.<br>// Функция возвращает минимальное время выполнения всех работ на двух станках.</font>
  '''function''' getCmax(n, p1, p2)
+
'''function''' getCmax(n : int, p1 : int[], p2 : int[]): int
      maxTime = 0
+
    int maxTime = 0
      '''for''' i = 0 .. n - 1
+
    '''for''' i = 0 .. n - 1:
        maxTime += p1[i]
+
      maxTime += p1[i]
      dp[][] = INF
+
    int[][] dp
      dp[0][0] = 0
+
    fill(dp, <tex>\infty</tex>)
      '''for''' i = 0 .. n - 1
+
    dp[0][0] = 0
        '''for''' j = 0 .. maxTime
+
    '''for''' i = 0 .. n - 1:
            '''if''' dp[i + 1][j + p1[i]] > dp[i][j]:
+
      '''for''' j = 0 .. maxTime:
              dp[i + 1][j + p1[i]] = dp[i][j]
+
          dp[i + 1][j] = min(dp[i][j - p1[i + 1]], dp[i][j] + p2[i + 1])
            '''if''' dp[i + 1][j] > dp[i][j] + p2[i]:
+
    int answer = <tex>\infty</tex>
              dp[i + 1][j] = dp[i][j] + p2[i]
+
    '''for''' j = 0 .. maxTime:
      answer = INF
+
      answer = min(answer, max(j, dp[n][j]))
      for j = 0 .. maxTime
+
    '''return''' answer
        answer = '''min'''(answer, '''max'''(j, dp[n][j]))
 
      '''return''' answer
 
 
==Время работы==
 
==Время работы==
 
Время работы <tex>O(n \cdot maxTime)</tex> {{---}} псевдополиномиальный алгоритм. Кроме того, если время выполнения работ, будет вещественные числа, то придется приводить их до целых, либо считать приблежённое значения.
 
Время работы <tex>O(n \cdot maxTime)</tex> {{---}} псевдополиномиальный алгоритм. Кроме того, если время выполнения работ, будет вещественные числа, то придется приводить их до целых, либо считать приблежённое значения.
 
==Источники информации==
 
* J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1:343–362, 1977.
 
  
 
==См. также==
 
==См. также==
 
* [[F2Cmax|<tex>F2\mid\mid C_{max}</tex>]]
 
* [[F2Cmax|<tex>F2\mid\mid C_{max}</tex>]]
 
* [[O2Cmax|<tex>O2\mid\mid C_{max}</tex>]]
 
* [[O2Cmax|<tex>O2\mid\mid C_{max}</tex>]]
 +
 +
==Примечания==
 +
<references/>
 +
 +
==Источники информации==
 +
* J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, стр. 358–360, 1977.
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Версия 16:25, 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]\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(n : int, p1 : int[], p2 : int[]): 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.