R2Cmax

Материал из Викиконспекты
Перейти к: навигация, поиск

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