Жадный алгоритм в задачах о покрытии/Задачи/lpt-rule-for-scheduling

Материал из DISCOPAL
< Жадный алгоритм в задачах о покрытии‎ | Задачи
Версия от 07:45, 21 февраля 2019; StasFomin (обсуждение | вклад) (Массовая правка: замена :Решенные задачи на :Нерешенные задачи)

Перейти к: навигация, поиск


Рассмотрим задачу Планирование Задач на Одинаковых Машинах и применим к ней LPT[1]-эвристику:

  • отсортировать задачи по убыванию длины
  • для каждой задачи:
    • применять жадный алгоритм загрузки: бросать задачу на самую малозагруженную машину

Докажите, что в,

  • OPT(x) — значение этого оптимального решения.
  • — значение, найденное алгоритмом
  • ↑ Largest Processing Time

    • [ Хронологический вид ]Комментарии

    (нет элементов)

    Войдите, чтобы комментировать.

    Источник — «https://discopal.ispras.ru/index.php?title=Жадный_алгоритм_в_задачах_о_покрытии/Задачи/lpt-rule-for-scheduling&oldid=8325»