Изменения
Новая страница: «== Описание алгоритма == Дано <tex>n</tex> работ с временами выполнения <tex>p_{i}</tex>. И <tex>m</tex> один...»
== Описание алгоритма ==
Дано <tex>n</tex> работ с временами выполнения <tex>p_{i}</tex>. И <tex>m</tex> одинаковых параллельных машин. Нужно минимизировать суммарные времена завершения.
== Идея ==
Пусть <tex>p_{i}</tex> заданы в порядке невозрастания (<tex>p_{1} \geqslant p_{2} \geqslant \ldots \geqslant p_{n} </tex>). Пусть теперь <tex>b_{k} = \dfrac{k}{m}</tex>. Тогда в оптимальном расписании работа с номером <tex>i</tex> будет выполнена на станке <tex>i \bmod m</tex>, <tex>b_{i}</tex>-ой с конца.
Дано <tex>n</tex> работ с временами выполнения <tex>p_{i}</tex>. И <tex>m</tex> одинаковых параллельных машин. Нужно минимизировать суммарные времена завершения.
== Идея ==
Пусть <tex>p_{i}</tex> заданы в порядке невозрастания (<tex>p_{1} \geqslant p_{2} \geqslant \ldots \geqslant p_{n} </tex>). Пусть теперь <tex>b_{k} = \dfrac{k}{m}</tex>. Тогда в оптимальном расписании работа с номером <tex>i</tex> будет выполнена на станке <tex>i \bmod m</tex>, <tex>b_{i}</tex>-ой с конца.
