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

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

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

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

D(0) = max {dA(0), dB (0), dC (0)} (25), где

; ; (26).

2) Первый шаг. Образование множеств G1(1), G2(1) , …, Gn(1), подмножество Gk определяется всеми последовательностями с началом ik(k, .,n).

Вычисление оценок. Оценку для последовательности sk определяют из соотношения (24), т. е. D(sk) = max {dA(sk), dB (sk), dC (sk)}; k = 1,…,n. (27).

Выбор варианта для продолжения. Из всех подпоследовательностей, построенных на предыдущем шаге, выбирают наиболее перспективную последовательность sk с наименьшей оценкой, т. е. D(sk(1))=min D(sj(1)). (28)

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

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

3) k-й шаг. Допустим, что уже проведено k шагов, в результате чего построены варианты s1(k), s2(k) ,…,sk(k), а именно подпоследовательности длиной k.

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

D(ss(k))=min D(sj(k)).

Множество Gs(k) разбиваем на (n - k) подмножеств, каждое из которых образуется добавлением к последовательности ss(k) некоторого элемента ik+1 такого, что ik+1.

Оценка определяется в соответствии с соотношениями (21) - (24).

В результате строим дерево вариантов следующего вида: вершина О отвечает s = 0, вершины первого уровня G1(1), G2(1) ., Gn(1) соответствуют последовательностям длиной 1, т. е. s1(1) = 1, s2(1) = 2, ., sn(1) = п и т. д. Каждая конечная вершина отвечает последовательности максимальной длины n.

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

§2. Пример использования метода ветвей и границ в задаче трех станков

Для того, чтобы придать формальной схеме прикладное значение, рассмотрим конкретный пример задачи трех станков.

Решим задачу трех станков, условия которой приведены в табл. 1:

Таблица 1

1) Нулевой шаг. s = 0.

dA(s = 0) = A(0) + + = 0 + 14 + 3 = 17;

dB(s = 0) = В(0) + + = 0 + 15 + 2 = 17;

dC(s = 0) = С(0) + =14 .

Тогда

∆ (s = 0) = max {17, 17,14} = 17.