|
2. Ослабление некоторых ограничений частичного упорядочивания. 3. Уменьшение некоторых времен выполнения. 4. Увеличение количества ресурсов. Грахам разработал общую граничную оценку с двойным исполнением множества задач. Во время первого выполнения задачи характеризуются параметрами т, <, L, п и ш (длина плана), а во время второго выполнения т', <', L', п' и ш’, так что т'<т, каждое ограничение <’ содержится в <. Результатом данной оценки является следующее выражение: — <1 + [(п-1)/и’]. Показано, что эта оценка является лучшей из возможных, и для п = п ’ отношение 2-1/л может быть достигнуто изменение,м любой из величин (L, т или <). Особым случаем подхода «наидлиннейшей динамической цепочки» является ситуация, когда < является пустым, т. е. задачи независимые. Для этого случая определена наилучшая оценка как WL/W„i4/3-l/3n. Очевидно, что для автора первоочередной причиной определения этих ограничений является обеспечение хороших субоптимальных планов при лишь частичных вычислительных затратах, необходимых для получения оптимального решения. Предположим, что во время изучения множества из г планируемых задач определено, что размер множества слишком велик для использования методов перебора. Тогда привлекательным выглядит следующий альтернативный алгоритм генерации (для случая < = 0): оптимальным образом спланировать к наидлиннейших задач (к>0), а оставшиеся гк задач спланировать произвольным образом. Сравнительный коэффициент для этого подхода имеет вид: 1-1/п w0 1 + [к / и] ’ 59 |
3. Уменьшение некоторых времен выполнения. 4. Увеличение количества процессоров. Грахам разработал общую граничную оценку с двойным исполнением множества задач. Во время первого выполнения задачи характеризуются параметрами т, <, L, п и w (длина плана), а во время второго выполнения т', <’, L', п' и w’, так что т’<т, каждое ограничение <’ содержится в <. Результатом данной оценки является следующее выражение: — <1 + [(«-1)/л']. w Показано, что эта оценка является лучшей из возможных, и для п = п ’ отношение 2-1/и может быть достигнуто изменением любой из величин (£, т или <). Особым случаем подхода «наидлиннейшей динамической цепочки» является ситуация, когда < является пустым, т. е. задачи независимые. Для. этого случая определена наилучшая оценка как РГ£М<4/3-1/3.п. Очевидно, что для автора первоочередной причиной определения этих ограничений является обеспечение хороших субоптимальных планов при лишь частичных вычислительных затратах, необходимых для получения оптимального решения. Предположим, что во время изучения множества из г планируемых задач определено, что размер множества слишком велик для использования методов перебора. Тогда привлекательным выглядит следующий альтернативный алгоритм генерации (для случая < = 0): оптимальным образом спланировать к наидлиннейших задач (к>$\ а оставшиеся г-к задач спланировать произвольным образом. Сравнительный коэффициент для этого подхода имеет вид: !-1/и w0 1 + [к / п\ ’ где п число используемых процессоров. Имеют место два особых случая для этого результата. 1) Когда к = О, 65 |