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

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

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

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

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

Идея

Псевдокод

Асимптотика

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