Cтраница 1
Конвейерная задача, которая упоминается в строках 15 и 16, состоит в следующем. [1]
В заключение данной главы мы рассматриваем конвейерную задачу. В этом случае набор заданий состоит из цепочек длины т, в которых задания, стоящие на i - м месте, должны выполняться на процессоре Pt. Цепочки заданий можно интерпретировать следующим образом: первое задание соответствует процессу ввода, который должен быть осуществлен с устройства чтения с перфокарт, второе соответствует счету на процессоре, и третье соответствует выводу на печатающее устройство. Мы предлагаем алгоритм для двухпроцессорной конвейерной задачи. [2]
Читателям предлагается это проделать, учитывая отсутствие упорядочения процессоров, имеющегося в конвейерной задаче. [3]
Это наводит на мысль, что в хорошем эвристическом алгоритме минимизации среднего времени завершения в конвейерных задачах большой размерности следует вначале получить улучшенное начальное решение с помощью метода ветвей и границ без возвратов, а затем попытаться улучшить решение с помощью поиска в локальной окрестности. [4]
Следовательно, с помощью простого правила мы можем трансформировать входные данные задачи о ранце в исходные данные конвейерной задачи ( т3) таким образом, что оптимальное решение конвейерной задачи будет найдено в том и только в том случае, когда исходная задача о ранце имеет решение. Следовательно, мы вправе ожидать, что данная задача имеет по крайней мере такую же сложность, как и задача о ранце. [5]
Следовательно, с помощью простого правила мы можем трансформировать входные данные задачи о ранце в исходные данные конвейерной задачи ( т3) таким образом, что оптимальное решение конвейерной задачи будет найдено в том и только в том случае, когда исходная задача о ранце имеет решение. Следовательно, мы вправе ожидать, что данная задача имеет по крайней мере такую же сложность, как и задача о ранце. [6]
Метод ветвей и границ, описанный в этом параграфе, тесно связан с динамическим программированием, но мы отложим обсуждение этой связи до § 6.5. В следующем параграфе дан обзор приближенных алгоритмов и представлены результаты практических расчетов для конвейерной задачи. [7]
Двухпроцессорная конвейерная задача, которую мы рассмотрели, не охватывает все три фазы исполнения программ, а именно: ввод, вычисления, вывод. Хотя трехпро-цессорная конвейерная задача является УУР-полной, существует частный случай, относительно которого можно сделать важные утверждения. Пусть теперь цепочка С, состоит из трех задач, имеющих времена выполнения а -, ( Зг и YJ. Рассмотрим, например, систему ввода-вывода ( / / 0), в которой считается, что в процессе вывода имеется некоторое время простоя. [8]
Выводы относительно результатов экспериментов. Результаты машинных экспериментов для описанных алгоритмов решения конвейерной задачи позволяют сделать следующие выводы. [9]
Для применения точных алгоритмов метода ветвей и границ к конвейерной задаче были выбраны следующие параметры. [10]
Среднее число соседних решений, которые необходимо проверить ( выбрать и сравнить их стоимость со стоимостью базового решения) прежде, чем будет найден локальный оптимум, может быть использовано в качестве меры оценки времени, требуемого для реализации процедуры локального поиска. Оно также дает количество вычислений функции стоимости. В конвейерной задаче с п работами и т машинами каждое вычисление стоимости требует времени, линейно зависящего от произведения тп, поскольку времена завершения каждой из п работ на т машинах должны быть вычислены с помощью рекурсивной процедуры построения перестановочного расписания, выполняющейся до тех пор, пока для всех п работ не будет назначено время начала на каждой машине. [11]
Подход к решению комбинаторных задач, развитый в гл. Как показано в § 1.5, этот подход применим и к другим задачам упорядочения и может оказаться полезным при решении общей задачи составления расписаний. Например, можно легко показать, что произвольное расписание для конвейерной задачи может быть длиннее оптимального примерно в т раз. Представляет интерес исследование простых и удобных в применении эвристических алгоритмов и определение границ их эффективности. Это позволит определить, могут ли характеристики этих алгоритмов в наихудшем случае быть доведены до приемлемого уровня. Оказывается, что часто довольно трудно найти столь же простые хорошие эвристические алгоритмы, как рассмотренные в гл. Имеется недавний обзор [34], в котором сравниваются эвристические алгоритмы для конвейерной задачи. [12]
Во время пребывания в вычислительной системе программа обрабатывается различными устройствами. Все программы проходят фазы ввода, исполнения и вывода; поэтому система заданий может быть представлена в виде цепочек, состоящих из т заданий, в которых i - e задание обрабатывается на устройстве Pt. Определение расписания минимальной длины в данной ситуации составляет предмет так называемой конвейерной задачи. Для больших значений т задача является УУР-полной ( см. гл. [13]
В следующем параграфе вводится общая схема для алгоритмов ветвей и границ. Она включает ситуации переполнения памяти, превышения времени счета, а также остановки при достижении заданной точности. За этим следуют доказательство корректности и ряд недавних результатов, касающихся зависимости потребностей в вычислительных ресурсах от правил отсечения, определения допустимых решений, от правила доминирования, нижней оценки и заданной степени точности. Далее мы рассмотрим приближенные алгоритмы, включающие эвристические процедуры и поиск в локальной окрестности. В заключение представлены результаты расчетов для двухмашинной конвейерной задачи, которая упоминалась выше. Описаны характеристики точных, приближенных и гарантирующих заданную точность алгоритмов. Особое внимание уделено извлечению из результатов машинных расчетов наиболее полезной информации - в виде допустимых решений и нижних оценок оптимальных решений. [14]
Приближенные алгоритмы - это любые схемы, которые могут привести к получению допустимого решения с низкой стоимостью. Плодотворный подход часто формируется при исследовании частных случаев, и правило, дающее оптимальный результат в простых случаях, такое, как первой назначается работа с наименьшей длительностью, может быть перенесено на сложные ситуации. Несмотря на кажущуюся уязвимость этого подхода, в последние десятилетия появилось несколько общих методов, которые представляются эффективными для широкого круга задач. Одним из них является поиск в локальной окрестности, другим - - - метод ветвей и границ без возвратов. Мы рассмотрим оба этих подхода совместно с экспериментальными результатами для среднего времени завершения в конвейерной задаче для двух машин. [15]