PSumCi — различия между версиями
(Новая страница: «== Описание алгоритма == Дано <tex>n</tex> работ с временами выполнения <tex>p_{i}</tex>. И <tex>m</tex> один...») |
|||
| Строка 1: | Строка 1: | ||
| − | == | + | <tex dpi = "200">P \mid \mid \sum C_{i}</tex> |
| − | Дано <tex>n</tex> работ с временами выполнения <tex>p_{i}</tex>. И <tex>m</tex> | + | {{Задача |
| + | |definition = Дано <tex>n</tex> работ с заданными временами выполнения <tex>p_{i}</tex>. И <tex>m</tex> параллельных станков с одинаковой скоростью выполнения работ.<br>Цель {{---}} составить такое расписание, чтобы суммарное время окончания всех работ было минимальным. | ||
| + | }} | ||
== Идея == | == Идея == | ||
Пусть <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>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>-ой с конца. | ||
Версия 18:48, 4 июня 2016
| Задача: |
| Дано работ с заданными временами выполнения . И параллельных станков с одинаковой скоростью выполнения работ. Цель — составить такое расписание, чтобы суммарное время окончания всех работ было минимальным. |
Идея
Пусть заданы в порядке невозрастания (). Пусть теперь . Тогда в оптимальном расписании работа с номером будет выполнена на станке , -ой с конца.
