Cтраница 1
Граф G редукции отношения - - изображен на рис. 3.1, значения параметров tt приведены в табл. 3.1. В хранилище в момент времени t 0 находится 100 единиц информации. [1]
Граф G редукции отношения - -, соответствующий множеству N, превратим в дерево, добавив новую вершину г и соединив конечные вершины графа G с этой вершиной исходящими из конечных вершин дугами. [2]
Предполагается, что граф редукции отношения строгого порядка является деревом либо число приборов равно двум. [3]
Пусть каждая компонента связности графа G редукции отношения строгого порядка - является входящим деревом. [4]
О, i 1, 17, и граф G редукции отношения строгого порядка, заданного на N, изображен на рис. 5.3, а. Требования пронумерованы в соответствии с алгоритмом, описанным в предыдущем пункте. [5]
Приводятся полиномиальные алгоритмы решения задачи в следующих случаях: а) множество требований не упорядочено; б) граф редукции отношения строгого порядка является древовидным; в) М 2 при произвольном графе редукции отношения строгого порядка. В последних двух случаях предполагается, что длительности обслуживания требований соизмеримы. [6]
В § § 5 и 6 изучается задача построения оптимального по быстродействию расписания обслуживания частично упорядоченного множества требований параллельными приборами в предположении, что а) граф редукции отношения строгого порядка является древовидным либо б) число приборов равно двум. В § 5 предполагается, что длительности обслуживания всех требований одинаковы и запрещены прерывания процесса обслуживания, а в § 6 - длительности обслуживания требований различны, но допускаются прерывания. В § 6 рассмотрен также случай, когда множество требований не упорядочено. [7]
В данном параграфе рассматривается задача построения оптимального по быстродействию расписания обслуживания частично упорядоченного множества требований, имеющих одинаковые длительности обслуживания, параллельными идентичными приборами в предположении, что а) граф редукции отношения строгого порядка является древовидным либо б) число приборов равно двум. [8]
Добавим к множеству N новое требование г п положим i - г для всех i N. Граф редукции отношения - -, заданного на множестве N U г, представляет собой входящее дерево. Построим й-расписание s для множества N U г. По теореме 5.1 это расписание является оптимальным. SL ( t) ( L 1, М) на остальных интервалах, получаем / г-расписание s для множества N. [9]
В данном параграфе рассматривается задача построения расписания обслуживания частично упорядоченного множества требований, имеющих одинаковые длительности обслуживания, параллельными идентичными приборами, при котором не нарушаются директивные сроки. Предполагается, что граф редукции отношения строгого порядка является входящим деревом либо число приборов равно двум. [10]
В § 1 вводится понятие приорнтето-порождающего функционала. В § 2 вводятся специфические преобразования графа G редукции отношения строгого порядка, заданного на N. Эти преобразования лежат в основе методов оптимизации прноритето-порождающпх функционалов на множестве перестановок, сохраняющих заданный на N порядок. В § § 3 и 4 рассматриваются случаи, когда граф G является древовидным и последовательно-параллельным соответственно. [11]
Предположим, что в графе Г существует - клика, содержащая не менее г / вершин. Рассмотрим расписание s обслуживания требований построенного множества N, при котором а) в интервале времени [ 0, у ] обслуживается у вершинных требований, соответствующих вершинам Г, б) в интервале [ г / о, у о УО ( УО - Df / 2 ] обслуживаются требования, соответствующие ребрам Г ( их уа ( уа - DiV2 штук) в порядке, допустимом относительно G ( G - граф редукции отношения - -), в) затем обслуживаются оставшиеся вершинные требования, а после них - оставшиеся реберные требования так, чтобы требования, связанные дугой в G, обслуживались непосредственно друг за другом. [12]
Пусть G ( N, U) - граф, для которого Т является декомпозиционным деревом. Покажем, что графы G и G совпадают. Граф G является графом редукции отношения строгого порядка - -, поэтому граф G не имеет контуров, кроме того, по построению он не имеет и транзитивных дуг. [13]
В третьей главе рассматриваются вопросы минимизации так называемых приоритето-порождающих функционалов на множестве перестановок элементов конечного множества N, сохраняющих заданный на N строгий порядок. В терминах минимизации приоритето-порождающих функционалов естественным образом формулируются многие задачи теории расписаний. Там же вводится понятие приоритето-порождающего функционала. В § 2 описываются преобразования графа G редукции отношения строгого порядка, заданного на N. [14]
Пусть каждая компонента связности графа G является выходящим деревом. Заменим ориентацию каждой дуги этого графа на противоположную. В результате получаем граф G, каждая компонента которого является входящим деревом. Ясно, что граф G является графом редукции отношения строгого порядка, обратного исходному. [15]