Cтраница 3
Определение 4.1. Отношение А на множестве М называется отношением строгого порядка ( или строгим порядком), если оно антирефлексивно и тран-зитивно. [31]
Кроме того, на множестве N может быть задано отношение строгого порядка, и тогда поиск оптимального расписания должен осуществляться среди расписаний, допустимых относительно этого порядка. [32]
Между отношениями совершенного нестрогого порядка на множестве М и отношениями совершенного строгого порядка на множестве М существует такая же простая зависимость, как между нестрогими и строгими порядками. [33]
Приведенные в таблицах оценки сложности алгоритмов справедливы в предположении, что отношение строгого порядка, заданное на множестве требований ( если оно не пусто), представлено своим графом редукции. Отметим, что переход от произвольного бесконтурного графа к его транзитивному замыканию или к графу редукции требует выполнения не более 0 ( п3) операций [7], где п - число вершин графа. [34]
О, i 1, 17, и граф G редукции отношения строгого порядка, заданного на N, изображен на рис. 5.3, а. Требования пронумерованы в соответствии с алгоритмом, описанным в предыдущем пункте. [35]
Во многих случаях граф G ( X, U) редукции отношения строгого порядка - удобно задавать списками предшественников и ( или) потомков его вершин. Такая форма задания позволяет, в частности, отыскивать множество всех минимальных ( максимальных) относительно - элементов множества X и удалять из X данный минимальный ( максимальный) элемент, выполняя при этом не более 0 ( Х) операций. [36]
Пусть дано множество М, отношение совершенного строгого порядка на нем и отношение строгого порядка гф. [37]
Транзитивное и антирефлекспвное отношение, заданное на множестве X, будем называть отношением строгого порядка ( пли строгим порядком), а множество X в этом случае - строго упорядоченным. [38]
Пусть А я В - задачи из описанного класса, G и G - графы редукции отношений строгого порядка, определенные на множествах требований этих задач соответственно, и G получается из G подстановкой цепей. [39]
Таким образом, если М 2, di 0, tt i, ii n, ч отношение строгого порядка - - задано в транзитивно замкнутой форме, то для построения допустимого относительно директивных сроков расписания ( если оно существует) достаточно: а) вычислить модифицированные директивные сроки DI ( требуется выполнить не более 0 ( п2) операций); б) получить список А, требований, упорядоченных по неубыванию значений DI ( не более O ( nlogn) операций - см. гл. В результате выполнения не более 0 ( п2) операций будет построено допустимое расписание, либо сделано заключение о том, что допустимого расписания не существует. [40]
Приводятся полиномиальные алгоритмы решения задачи в следующих случаях: а) множество требований не упорядочено; б) граф редукции отношения строгого порядка является древовидным; в) М 2 при произвольном графе редукции отношения строгого порядка. В последних двух случаях предполагается, что длительности обслуживания требований соизмеримы. [41]
В § § 5 и 6 изучается задача построения оптимального по быстродействию расписания обслуживания частично упорядоченного множества требований параллельными приборами в предположении, что а) граф редукции отношения строгого порядка является древовидным либо б) число приборов равно двум. В § 5 предполагается, что длительности обслуживания всех требований одинаковы и запрещены прерывания процесса обслуживания, а в § 6 - длительности обслуживания требований различны, но допускаются прерывания. В § 6 рассмотрен также случай, когда множество требований не упорядочено. [42]
В данном параграфе рассматривается задача построения оптимального по быстродействию расписания обслуживания частично упорядоченного множества требований, имеющих одинаковые длительности обслуживания, параллельными идентичными приборами в предположении, что а) граф редукции отношения строгого порядка является древовидным либо б) число приборов равно двум. [43]
Приводятся полиномиальные алгоритмы решения задачи в следующих случаях: а) множество требований не упорядочено; б) граф редукции отношения строгого порядка является древовидным; в) М 2 при произвольном графе редукции отношения строгого порядка. В последних двух случаях предполагается, что длительности обслуживания требований соизмеримы. [44]
Отношением нестрогого порядка ( нестрогим порядком) называется отношение, обладающее свойствами рефлексивности, антисимметричности и транзитивности. Отношением строгого порядка ( строгим порядком) называется отношение, обладающее свойствами антирефлексивности, асимметричности и транзитивности. [45]