Обсуждение участницы:Анна

[math] O \mid p_{i,j} = 1 \mid \sum T_{i} [/math]

Задача:

Дано [math]m[/math] одинаковых станков, которые работают параллельно, и [math]n[/math] работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания [math]d_i[/math] — время, до которого она должна быть выполнена. Необходимо минимизировать суммарную медлительность.

Описание алгоритма

Идея

Будем полагать, что работы заданы в порядке неубывания их дедлайнов, то есть [math]d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n[/math].

Лемма:

Пусть есть работы [math]1 \ldots n[/math] с дедлайнами [math]d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n[/math]. Тогда существует оптимальное расписание, в котором времена завершения работ идут в том же порядке, то есть [math]C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n[/math].

Доказательство:

[math]\triangleright[/math]

Рассмотрим две работы [math]i[/math] и [math]j[/math] из какого-либо оптимального расписания такие, что [math]C_i \gt C_j[/math] и [math]d_i \lt d_j[/math]. Поменяем эти работы в расписании местами, то есть [math]C'_i = C_j[/math] и [math]C'_j = C_i[/math]. Если они обе успевали выполниться вовремя, то это свойство сохранится, так как [math]d_i \lt d_j[/math], значит по-прежнему [math]T_i = 0[/math] и [math]T_j = 0[/math], то есть значение целевой функции мы не ухудшили и расписание осталось оптимальным. Если обе работы не успевали выполниться вовремя, то когда мы поменяем их местами ничего не изменится, то есть значение целевой функции останется прежним, так как мы не меняли значения времен окончаний, а только поменяли их местами. Если работа [math]j[/math] успевала выполниться, а [math]i[/math] — нет, то мы снова не ухудшим значение целевой функции. Покажем это. До того, как мы поменяли работы местами, было [math]T_i + T_j = C_i - d_i[/math], так как [math]T_j = 0[/math]. После того, как мы поменяли работы местами, [math]T_i + T_j = C'_i - d_i + C'_j - d_j = C_j - d_i + C_i - d_j = C_i - d_i + (C_j - d_j)[/math]. Но так как работа [math]j[/math] успевает выполниться до дедлайна, то [math]C_j - d_j \leqslant 0[/math].

[math]\triangleleft[/math]

Далее будем рассматривать только оптимальное расписание со свойством [math]C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n[/math].

Теорема:

Всегда существует оптимально расписание такое, что в нем [math]C_i \leqslant m + i - 1[/math] для любого [math]i = 1 \ldots n[/math], где [math]m[/math] — количество станков.

Доказательство:

[math]\triangleright[/math]

Рассмотрим оптимальное расписание [math]S^*[/math], в котором для любого [math]i = 1 \ldots k - 1[/math] выполняется [math]C_i \leqslant m + i - 1[/math], но [math]C_k \gt m + k - 1[/math], где [math]k[/math] максимально.

[math]\triangleleft[/math]

Псевдокод

Асимптотика

См. также

• [math]O2 \mid \mid C_{max}[/math]
• [math]O \mid p_{ij} = 1 \mid \sum U_i[/math]
• [math] O \mid p_{i, j} = 1, d_i \mid - [/math]
• [math] O \mid p_{i, j} = 1 \mid - \sum w_{i} U_{i}[/math]

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

• Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 171-174 ISBN 978-3-540-69515-8