Понимание планирования, чтобы минимизировать проблему опозданий - PullRequest
0 голосов
/ 07 октября 2018

Я читал следующую ссылку, чтобы лучше понять оптимальность алгоритма.Мне было интересно, зачем «инверсия» нужна для доказательства оптимальности?Я почесал голову об этом некоторое время.Любая помощь приветствуется.Спасибо!

https://kartikkukreja.wordpress.com/2013/11/24/scheduling-to-minimize-lateness/

1 Ответ

0 голосов
/ 09 октября 2018

Логика такова:

Предположим, что существует оптимальное решение: 1) Всегда существует вариант решения без инверсии по сравнению с оптимальным решением без дополнительной задержки;

2) Если 1) является надежным, то мы можем сузить проблему до того, как планировать задания для минимизации времени простоя

3) Очевидно, что предлагаемое решение уже минимизирует время простоя, поскольку время простоя равно 0.

Итак, короче говоря, введение инверсии должно сузить проблему, чтобы минимизировать время простоя.

...