Cтраница 2
Подход к решению комбинаторных задач, развитый в гл. Как показано в § 1.5, этот подход применим и к другим задачам упорядочения и может оказаться полезным при решении общей задачи составления расписаний. Например, можно легко показать, что произвольное расписание для конвейерной задачи может быть длиннее оптимального примерно в т раз. Представляет интерес исследование простых и удобных в применении эвристических алгоритмов и определение границ их эффективности. Это позволит определить, могут ли характеристики этих алгоритмов в наихудшем случае быть доведены до приемлемого уровня. Оказывается, что часто довольно трудно найти столь же простые хорошие эвристические алгоритмы, как рассмотренные в гл. Имеется недавний обзор [34], в котором сравниваются эвристические алгоритмы для конвейерной задачи. [16]