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

Минимизация
приоритето-порождающих функций
Задача 1/out — tree/ ∑Cj
Решить задачу 1/out — tree/ ∑Cj , в которой имеется 10 требований. Требование 3 предшествует требованию 4, которое, в свою очередь, предшествует требованиям 1, 7 и 9.
Длительности обслуживания pj заданы в таблице:
Для задачи 1// ∑Cj решением было бы расписание (7, {2, 8}, 3, {1, 6, 10}, 4, 5, 9). Однако это расписание нарушает отношения предшествования:

Минимизация
приоритето-порождающих функций
Обозначим
Пr - множество всех перестановок πr = (i1, ... , ir) элементов множества N = {1, ..., n}, r = 1, ..., n
П0 = {π0} = {(∅)}
где U – операция объединения множеств.

Минимизация
приоритето-порождающих функций
Функция F(π), определенная на множестве Пn называется приоритето-порождающей (ППФ), если существует функция ω(π), π ∈ Π, называемая функцией приоритета, которая обладает следующими свойствами:
для любых перестановок π = (π1, πα, πb, π2) ∈ Πn и π' = (π1, πb, πα, π2) ∈ Πn
из ω(πα) > ω(πb) следует F(π) ≤ F(π') и
из ω(πα) = ω(πb) следует F(π) = F(π').

Минимизация
приоритето-порождающих функций
Множество N является частично упорядоченным, если задано отношение предшествования (бинарное, транзитивное, антирефлексивное отношение), представленное графом редукции этого отношения G = (N, U).
Граф G называется графом редукции отношения предшествования, если он получен из графа отношения частичного порядка путем удаления всех транзитивных дуг.

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

Примеры
приоритето-порождающих функций
Можно доказать, что:
для задачи 1/prec/ ΣCj целевая функция является ППФ с функцией приоритета
ω (π) = |{π}|/Ρ (π)
где Ρ (π) = Σ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 в ω -цепь.

Алгоритм минимизации ППФ на частично упорядоченных множествах
Задача 1/out — 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.

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

Алгоритм минимизации ППФ на частично упорядоченных множествах (продолжение)
В случае, когда граф G – входящее дерево, в качестве опорной выбирается вершина i0, все непосредственные предшественники которой i1, ..., iν не имеют предшественников.
Формируется цепь (i1, ..., iν, i0). Она преобразуется в ω-цепь путем сравнения ω(i0) и ω(iv). Составная вершина [iν, i0] образуется, если ω(iv) ≤ ω(i0).
Далее процесс аналогичен случаю выходящего дерева.

Пример реализации алгоритма.
Задача 1/out — tree/ ∑Cj
Решить задачу 1/out — tree/ ∑Cj, в которой имеется 10 требований. Требование 3 предшествует требованию 4, которое, в свою очередь, предшествует требованиям 1, 7 и 9.
Длительности обслуживания pj заданы в таблице:
Граф отношений предшествования:

Пример реализации алгоритма (продолжение).
1. Вычислим значение функции приоритета для висячих вершин.
Функция приоритета: ω (π) = |{π}|/Ρ (π) где Ρ (π) = Σpj,

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

Пример реализации алгоритма (продолжение).
2б. Цепь (4, 7, 1, 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,
ω-цепь для потомков вершины 3: ([4, 7], 1, 9)

Пример реализации алгоритма (продолжение).
3б. Цепь (3, [4, 7], 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 и ставим ей в соответствие ω-цепь.