PSumCi — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Описание алгоритма == Дано <tex>n</tex> работ с временами выполнения <tex>p_{i}</tex>. И <tex>m</tex> один...»)
(нет различий)

Версия 18:42, 4 июня 2016

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

Дано [math]n[/math] работ с временами выполнения [math]p_{i}[/math]. И [math]m[/math] одинаковых параллельных машин. Нужно минимизировать суммарные времена завершения.

Идея

Пусть [math]p_{i}[/math] заданы в порядке невозрастания ([math]p_{1} \geqslant p_{2} \geqslant \ldots \geqslant p_{n} [/math]). Пусть теперь [math]b_{k} = \dfrac{k}{m}[/math]. Тогда в оптимальном расписании работа с номером [math]i[/math] будет выполнена на станке [math]i \bmod m[/math], [math]b_{i}[/math]-ой с конца.