Cтраница 2
В данном параграфе рассматривается задача построения расписания обслуживания частично упорядоченного множества требований, имеющих одинаковые длительности обслуживания, параллельными идентичными приборами, при котором не нарушаются директивные сроки. Предполагается, что граф редукции отношения строгого порядка является входящим деревом либо число приборов равно двум. [16]
Добавим к множеству N новое требование г п положим i - г для всех i N. Граф редукции отношения - -, заданного на множестве N U г, представляет собой входящее дерево. Построим й-расписание s для множества N U г. По теореме 5.1 это расписание является оптимальным. SL ( t) ( L 1, М) на остальных интервалах, получаем / г-расписание s для множества N. [17]
Добавим к множеству N новую вершину / с f j w, а к множеству U - дуги, исходящие из корней всех деревьев и заходящие в вершину / Полученный в результате граф G является, очевидно, входящим деревом. [18]
Для этого изменим ориентацию всех дуг дерева на противоположную и пронумеруем вершины, как в случае выходящего дерева. Таблица, представляющая входящее дерево, отличается от таблицы, представляющей выходящее дерево, второй и четвертой строкой. Здесь вторая строка - номер прямого потомка, а четвертая строка - минимальный п максимальный номера непосредственных предшественников. Выбор опорной вершины осуществляется по последней непустой кл етке таблицы, представляющей текущий граф: содержимое соответствующей клетки второй строки есть номер опорной вершины. Реализация процедуры преобразования входящего дерева в ш-цепь также требует выполнения не более O ( HI log n операций. [19]
Обслуживание требования i е N может быть выполнено любым из приборов и требует t единиц времени. Прерывания процесса обслуживания требования не допускаются. Каждая компонента связности G представляет собой входящее дерево. [20]
Пусть каждая компонента связности графа G является выходящим деревом. Заменим ориентацию каждой дуги этого графа на противоположную. В результате получаем граф G, каждая компонента которого является входящим деревом. Ясно, что граф G является графом редукции отношения строгого порядка, обратного исходному. [21]
Для этого изменим ориентацию всех дуг дерева на противоположную и пронумеруем вершины, как в случае выходящего дерева. Таблица, представляющая входящее дерево, отличается от таблицы, представляющей выходящее дерево, второй и четвертой строкой. Здесь вторая строка - номер прямого потомка, а четвертая строка - минимальный п максимальный номера непосредственных предшественников. Выбор опорной вершины осуществляется по последней непустой кл етке таблицы, представляющей текущий граф: содержимое соответствующей клетки второй строки есть номер опорной вершины. Реализация процедуры преобразования входящего дерева в ш-цепь также требует выполнения не более O ( HI log n операций. [22]