Cтраница 4
Допускаются прерывания в обслуживании любого требования. На множестве N задано отношение строгого порядка - -, определяющее возможную последовательность обслуживания требований. [46]
Запрещены прерывания в обслуживании требований. Па множестве N задано отношение строгого порядка - -, определяющее возможную последовательность обслуживания требований. [47]
В данном параграфе рассматривается задача построения расписания обслуживания частично упорядоченного множества требований, имеющих одинаковые длительности обслуживания, параллельными идентичными приборами, при котором не нарушаются директивные сроки. Предполагается, что граф редукции отношения строгого порядка является входящим деревом либо число приборов равно двум. [48]
Рефлексивное, антисимметричное и транзитивное отношение называется отношением порядка. Антирефлексивное, асимметричное, транзитивное отношение называется отношением строгого порядка. Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности. [49]
В силу теоремы 4.1 последние два соотношения не могут выполняться одновременно. Таким образом, если на множестве М задано отношение совершенного строгого порядка А, то на множестве М2 всех пар возникает разбиение на три класса: класс пар вида ( я, я), класс пар ( х, у) таких, что хАу, и класс пар ( х, у) таких. [50]
Заменим ориентацию каждой дуги графа G отношения порядка - - на противоположную. В результате получаем граф G, который является графом отношения строгого порядка, обратного исходному. Пусть s - расписание, допустимое относительно директивных сроков D, a T ( S) maxtj ( s) - длина этого расписания. [51]
В § 1 вводится понятие приорнтето-порождающего функционала. В § 2 вводятся специфические преобразования графа G редукции отношения строгого порядка, заданного на N. Эти преобразования лежат в основе методов оптимизации прноритето-порождающпх функционалов на множестве перестановок, сохраняющих заданный на N порядок. В § § 3 и 4 рассматриваются случаи, когда граф G является древовидным и последовательно-параллельным соответственно. [52]