Презентация на тему Теория расписаний. Минимизация приоритето-порождающих функций

задачу 1/out — tree/ ∑Cj , в которой имеется

10 требований. Требование 3 предшествует требованию 4, которое, в свою очередь, предшествует требованиям 1, 7 и 9.
Длительности обслуживания pj заданы в таблице:

Для задачи 1// ∑Cj решением было бы расписание (7, {2, 8}, 3, {1, 6, 10}, 4, 5, 9). Однако это расписание нарушает отношения предшествования:

= (i1, ... , ir) элементов множества N =

{1, ..., n}, r = 1, ..., n

П0 = {π0} = {(∅)}

где U – операция объединения множеств.

называется приоритето-порождающей (ППФ), если существует функция ω(π), π ∈

Π, называемая функцией приоритета, которая обладает следующими свойствами:

для любых перестановок π = (π1, πα, πb, π2) ∈ Πn и π' = (π1, πb, πα, π2) ∈ Πn

из ω(πα) > ω(πb) следует F(π) ≤ F(π') и
из ω(πα) = ω(πb) следует F(π) = F(π').

задано отношение предшествования (бинарное, транзитивное, антирефлексивное отношение), представленное графом

редукции этого отношения G = (N, U).

Граф G называется графом редукции отношения предшествования, если он получен из графа отношения частичного порядка путем удаления всех транзитивных дуг.

к минимизации ППФ на частично упорядоченных множествах требований.

Отношения

предшествования присутствуют в задачах, где некоторые операции используют результаты других (предшествующих) операций.

целевая функция является ППФ с функцией приоритета
ω (π)

= |{π}|/Ρ (π)
где Ρ (π) = Σpj,

для задачи 1/prec/ ΣwjCj целевая функция является ППФ с функцией приоритета
ω (π) = W(π)/Ρ(π),
где W(π) = Σwj.

задано частично упорядоченное множество N с графом редукции отношения

частичного порядка G = (N,U).

Задача состоит в минимизации F(π), π∈Πn(G), где Πn(G) - множество всех перестановок элементов множества N, допустимых относительно G.

операции над бесконтурными орграфами, не содержащими транзитивных дуг (в

т.ч. графами редукции отношения частичного порядка):

Преобразование I - [t, s] отождествления вершин t и s: замена вершин t и s одной составной вершиной [t, s].
Все входящие (исходящие) дуги в вершины t и s заменяются на входящие (исходящие) дуги в составную вершину. Удаляются появившиеся тразитивные дуги.

Преобразование II - (s, t) добавления дуги (s, t): добавление дуги (s, t) с последующим удалением тразитивных дуг.

(i1, ..., ik), где компоненты ij являются составными вершинами,

называется ω-цепью, если ω (il) ≥ ω (il+1), l = 1, ..., k - 1.
Если G представляет собой ω -цепь, то перестановка (i1, ..., ik) является оптимальной.



Если граф G – лес, то существует последовательность преобразований I и II, переводящая G в ω -цепь.

— tree/ F , где F – ППФ.
Алгоритм

минимизации ППФ на множестве Πn(G), где G - набор выходящих деревьев :

1. Вычисляем приоритеты не имеющих потомков (висячих) вершин.
2. Если G не есть набор изолированных вершин, то находим в G вершину i0, называемую опорной, все прямые потомки которой являются висячими.
Пусть этим потомкам соответствуют ω-цепи C1, ..., Сl.

Построим ω-цепь (i1, ..., iν), упорядочив все (составные) вершины цепей C1, ..., Cl по невозрастанию приоритетов.

Построим цепь (i0, i1, ..., iν).
Если ω(i0) > ω(i1),

то цепь (i0, i1, ... ,iν) является ω-цепью.
Если ω(i0) ≤ ω(i1), то объединяем i0 и i1 в составную вершину [i0, i1].

Далее сравниваем ω(i0, i1) и ω(i2) и, в случае необходимости, объединяем [i0, i1] и i2 и т.д.
Процесс продолжается до тех пор, пока цепь (i0, i1, ..., iν) не будет преобразована в некоторую ω-цепь C 0 = ([i0, i1, …, ik], ik+1, ... , iv).

Удаляем из G всех потомков вершины i0 и ставим ей в соответствие ω-цепь C 0.

Повторяем описанный процесс до тех пор, пока не будет

построен граф, состоящий из изолированных вершин.

Последовательность (составных) вершин соответствующих ω-цепям, в которой вершины упорядочены по невозрастанию приоритетов, является оптимальным решением задачи.

случае, когда граф G – входящее дерево, в качестве

опорной выбирается вершина i0, все непосредственные предшественники которой i1, ..., iν не имеют предшественников.

Формируется цепь (i1, ..., iν, i0). Она преобразуется в ω-цепь путем сравнения ω(i0) и ω(iv). Составная вершина [iν, i0] образуется, если ω(iv) ≤ ω(i0).

Далее процесс аналогичен случаю выходящего дерева.

задачу 1/out — tree/ ∑Cj, в которой имеется 10

требований. Требование 3 предшествует требованию 4, которое, в свою очередь, предшествует требованиям 1, 7 и 9.
Длительности обслуживания pj заданы в таблице:

Граф отношений предшествования:

для висячих вершин.
Функция приоритета:
ω (π) = |{π}|/Ρ (π)

где Ρ (π) = Σpj,

4, все прямые потомки которой 1, 7 и 9

являются висячими.

ω-цепь для потомков вершины 4: (7, 1, 9), поскольку значения функции ω вершин равны, соответственно, (1, 1/4, 1/9)

9) не является ω-цепью, поскольку значения функции ω вершины

4 равно 1/5<1.

Объединяем вершины 4 и 7 в составную вершину [4, 7].

Приоритет составной вершины [4, 7] равен 2/(5+1)=1/3. Цепь ([4, 7], 1, 9) является ω-цепью, т.к. 1/3>1/4.

Удаляем из графа G всех потомков вершины 4 и ставим ей в соответствие ω-цепь.

3,
ω-цепь для потомков вершины 3: ([4, 7], 1,

9)

1, 9) не является ω-цепью поскольку значения функции ω

вершины 3 равно 1/3=1/3.

Объединяем вершины 3 и [4, 7] в составную вершину [3, 4, 7]. Приоритет составной вершины [3, 4, 7] равен 3/(3+5+1)=1/3.
Цепь ([3, 4, 7], 1, 9) является ω-цепью, т.к. 1/3>1/4.

Удаляем из графа G всех потомков вершины 3 и ставим ей в соответствие ω-цепь.