Opij1sumwu

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

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

Задача:
Дано [math]m[/math] одинаковых станков, которые работают параллельно, и [math]n[/math] работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется за единицу времени. Для каждой работы есть время окончания [math]d_i[/math] — время, до которого она должна быть выполнена. Требуется минимизировать [math]\sum w_{i} U_{i}[/math], то есть суммарный вес всех просроченных работ.

Алгоритм

Доказательство корректности

Время работы

См. также

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

  • Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — c. 168 - 171. ISBN 978-3-540-69515-8