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

Докажите, что в случае этот алгоритм находит оптимальное решение. (OPT(x) — значение этого оптимального решения).


  1. Largest Processing Time