Кибернетика / Реферат: Применение метода ветвей и границ для задач календарного планирования

Реферат: Применение метода ветвей и границ для задач календарного планирования

Способ конструирования вариантов после-
довательностей s и вычисления оценок D(s) для каждого из них состоит в следующем.

Пусть имеется начальная подпоследовательность s. Тогда вычисляются величины:

d_C (s) = С(s) +, (1)

d_B (s) = В (s) ++ minc_j , (2)

d_A (s) = A (s) + + (3)

где J (s) — множество символов, образующих последовательность s.

За оценку критерия С (s) для варианта s можно принять величину

D(s) = max {d_A (s), d_B (s), d_C (s)}.(4)

Тогда ход решения задачи трех станков можно представить следующей формальной схемой.

Нулевой шаг. Задание множества G⁽⁰⁾ , образуется всеми возможными последовательностями (s = 0).

Вычисление оценки для множества G₀ :

гдеD(0) = max {d_A (0), d_B (0), б_C (0)},

; ; .

Первый шаг.Образование множеств G₁ ⁽¹⁾ UG₁ ⁽²⁾ U... …G₁ ⁽ⁿ⁾ .

Подмножество G_k определяется всеми последовательностями с началом i_k ( k — 1, ...,n ).

Вычисление оценок . Оценку для последовательности s_k определяют из соотношения (4), т. е.

D(s_k ) = max {d_A (s_k ), d_B (s_k ), d_C (s_k )}; k = 1, n.

Выбор варианта для продолжения. Из всех подпоследовательностей, построенных на предыдущем шаге, выбирают наиболее перспективную последовательность s_k с наименьшей оценкой, т. е.

D(s_k ⁽¹⁾ )=min D(s_j ⁽¹⁾ ).

Ветвление. Выбрав наиболее перспективный вариант последовательности s_k ⁽¹⁾ , развивают его построением всех возможных подпоследовательностей длиной 2с началом s_k ⁽¹⁾ вида s_k+1 ⁽²⁾ = (s_k ⁽¹⁾ , j ), где j не входит в s_k .

Вычисление оценок производят в соответствии с соотношениями (1), (2), (3).

k - ш а г. Допустим, что уже проведено k шагов, в результате чего построены варианты s₁ ^(k) ,s₂ ⁽ ^k) ,…,s_vk ⁽ ^k) , а именно подпоследовательности длиной k .

Выбираем самый перспективный вариант s_S ⁽ ^k) такой, что

D(s_s ^(k) )=min D(s_j ^(k) ).

Множество G_s ⁽ ^k ⁾ разбиваем на (п — k ) подмножеств, каждое из которых образуется добавлением к последовательности s_s ⁽ ^k ⁾ некоторого элемента i _k ₊₁ такого, что i _k ₊₁ .

Оценка определяется в соответствии с соотношениями (1) — (4).

В результате строим дерево вариантов следующего вида: вершина О отвечает s = 0, вершины первого уровня G ₁ ⁽¹⁾ , G ₂ ⁽¹⁾ ..., G _n ⁽¹⁾ соответствуют последовательностям длиной 1, т. е. s₁ ⁽¹⁾ = 1, s₂ ⁽¹⁾ = 2,..., s_n ⁽¹⁾ = п и т. д. Каждая конечная вершина отвечает последовательности максимальной длины п.

Признак оптимальности. Если s_v ⁽ ⁿ⁾ отвечает конечной вершине дерева, причем оценка наименьшая из оценок всех вершин, то s_v ⁽ ⁿ⁾ — искомый вариант, иначе переходим к продолжению варианта с наименьшей оценкой.