Cтраница 1
Ограничения предшествования заданы следующим образом. [1]
При отсутствии ограничений предшествования можно легко построить оптимальное расписание. [2]
Следствие 4.1. Задача упорядочения, в которой отсутствуют ограничения предшествования и имеются только два процессора, все еще остается NP-полной. [3]
VP-полнота этой задачи ясно показывает, что комбинаторная структура ограничений предшествования является достаточным фактором, чтобы сделать задачу трудной; при этом нам не придется опираться на сложность, присущую большим числам. [4]
Следствие 4.3. Задача минимизации среднего взвешенного времени прохождения с двумя процессорами при отсутствии ограничений предшествования является NP-полной. [5]
На самом деле мы доказали большее, чем утверждает теорема 4.3, поскольку не использовали ограничений предшествования и рассматривали только два процессора. [6]
Преобразование расписания, при котором задания на процессоре PJ будут выполнены раньше, не нарушает ограничений предшествования между заданиями в цепочке. Более того, Л; все еще выполняется перед В, и длина расписания не увеличилась. Доказательство леммы получается теперь индукцией по числу перестановок, необходимых для получения нужного расписания. [7]
Теорема 4.7. Задача упорядочения на двух процессорах, при единичных временах выполнения, одном ресурсе и ограничениях предшествования в виде леса является NP-полной. [8]
Рассмотрим систему заданий на рис. 2.17. Пусть ( / -, получается из нее изменением ориентации всех дуг, задающих ограничения предшествования. Независимо от используемого списка, списочное расписание для ( JT, ) имеет длину т - - г. Таким образом, изменение ориентации дуг приводит к более короткому списочному расписанию. Такая аномалия не возникает в расписании без прерываний общего вида. [9]
Модель процесса упорядочения, в терминах которой формулируются все последующие задачи, представлена в виде совокупности моделей, описывающих ресурсы, систему заданий, ограничения предшествования и меры оценки расписаний. В конце главы мы кратко рассмотрим вопросы, связанные с системой обозначений в этой и последующих главах. [10]
К счастью, для задач составления расписаний мы можем показать, что и в частном случае, когда времена выполнения равны 2 или даже 1 ( но при наличии ограничений предшествования), они все еще остаются yVP - полными. Следовательно, в некотором смысле структура ограничений предшествования вбирает в себя всю комбинаторную сложность, которая содержалась в больших временах выполнения. [11]
При этом выявляются ограничения предшествования между операциями. Переходам сети ставится в соответствие информация о времени выполнения, и для определения последовательности операций н сопоставления регистров, которые минимизируют время выполнения, используется полный перебор. [12]
Рассматриваются вопросы, связанные с построением алгоритмов решения задач теории расписаний для обслуживающих систем с одним и несколькими параллельными приборами. Детально исследуются задачи с ограничениями предшествования в обслуживании требований. Значительное внимание уделяется вопросам сложности решения задач теории расписаний. [13]
В рассматриваемых совокупностях деревьев ( лесах) каждое задание может иметь несколько непосредственных предшественников, но непосредственный преемник задания всегда единственный. Представляет также интерес противоположная ориентация ограничений предшествования, а именно: завершение некоторого задания может позволить начать выполнение более чем одного задания, но непосредственный предшественник задания всегда единственный. Неформально, антилес может быть построен, если у леса изменить на обратную ориентацию всех ребер. Результаты настоящего параграфа также применимы к антилесам. Для этого просто игнорируется направление ребер и строится уровне-вое расписание. [14]
К счастью, для задач составления расписаний мы можем показать, что и в частном случае, когда времена выполнения равны 2 или даже 1 ( но при наличии ограничений предшествования), они все еще остаются yVP - полными. Следовательно, в некотором смысле структура ограничений предшествования вбирает в себя всю комбинаторную сложность, которая содержалась в больших временах выполнения. [15]