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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Эффективное решение)
м (rollbackEdits.php mass rollback)
 
(не показано 6 промежуточных версий 3 участников)
Строка 5: Строка 5:
 
и втором станке различное. Нужно минимизировать время завершения всех работ.}}
 
и втором станке различное. Нужно минимизировать время завершения всех работ.}}
  
Задача <tex>R2 \mid \mid C_{max}</tex> является <tex>\mathrm{NP}</tex>-полной задачей. Доказательство смотри в книге, указанной в источниках информации.
+
Задача <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>.
  
 
==Неэффективное решение==
 
==Неэффективное решение==
Строка 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
 
\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>dp[i + 1][j] = \min(dp[i][j] + p_2[i + 1], dp[i][j - p_1[i + 1]])</tex>
  
Так же можно заметить, что во время каждой итерации алгоритма используется только два столбца массива <tex> dp </tex>. Это позволяет уменьшить использование памяти до <tex dpi=130> O(\sum\limits_{i = 1}^{n} p_1[i])</tex>.
+
Тогда ответом на задачу будет <tex>\min\limits_{j}(\max(j, dp[n][j]))</tex>. Другими словами мы перебираем время работы на первом станке и смотрим сколько ещё потребуется работать на втором станке. Время выполнения всех работ {{---}} это максимум из этих двух величин. И в конце из всех времен выбираем минимальное.
 +
 
 +
Также можно заметить, что во время каждой итерации алгоритма используется только два столбца массива <tex> dp </tex>. Это позволяет уменьшить использование памяти с <tex>O(n \cdot maxTime)</tex> до <tex> O(maxTime)</tex>.
  
 
==Доказательство корректности алгоритма==
 
==Доказательство корректности алгоритма==
Строка 41: Строка 37:
 
Корректность расписания, составленного алгоритмом очевидна. Надо доказать его оптимальность.
 
Корректность расписания, составленного алгоритмом очевидна. Надо доказать его оптимальность.
  
Пусть расписание, составленное этим алгоритмом <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: Строка 47:
  
 
==Псевдокод==
 
==Псевдокод==
  <font color=green>//Функция принимает количество работ n, список времён выполнения работ на первом станке p1 и времён выполнения на втором станке p2.<br>//Функция возвращает минимальное время выполнения всех работ на двух станках.</font>
+
  <font color=green>// Функция принимает количество работ n, список времён выполнения работ на первом станке p1 и времён выполнения на втором станке p2.<br>// Функция возвращает минимальное время выполнения всех работ на двух станках.</font>
  '''function''' getCmax(n, p1, p2)
+
'''function''' getCmax(p1 : '''int'''[n], p2 : '''int'''[n]): '''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.
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Текущая версия на 19:25, 4 сентября 2022

[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.