Жадный алгоритм в задачах о покрытии/Задачи/lpt-rule-for-scheduling-p-is-2 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 18: | Строка 18: | ||
См. также [[Жадный алгоритм в задачах о покрытии/Задачи/lpt-rule-for-scheduling]] | См. также [[Жадный алгоритм в задачах о покрытии/Задачи/lpt-rule-for-scheduling]] | ||
| − | [[Категория: | + | [[Категория:Решенные задачи]] |
Версия 10:01, 5 октября 2020
Рассмотрим задачу Планирование Задач на Одинаковых Машинах
и применим к ней LPT[1]-эвристику:
- отсортировать задачи по убыванию длины
- для каждой задачи:
- применять жадный алгоритм загрузки: бросать задачу на самую малозагруженную машину
Докажите, что в случае p=2,
- OPT(x) — значение этого оптимального решения.
- — значение, найденное алгоритмом.
- ↑ Largest Processing Time