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

[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]\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