Применение метода ветвей и границ для задач календарного планирования (стр. 2 из 3)

Согласно 2-му пункту нашего плана, составим 2 новых системы ограничений для (7):

(12) и (13).

Выполним 3-й пункт алгоритма. Для начала, решим задачу (7), (12) с помощью табличного процессора MicrosoftExcel (см. Приложение 2) и получим X₂ = (2; 1)[2], z₂ = 10 (14). Так как z₂ ≥ z₀, «оптимальным» становится план Х₀.

Решим задачу (7), (13). Из последнего уравнения очевидно, что x₂ = 0. Отсюда следует, что x₁ = 3 (максимально возможное). Тогда Х₃ = (3; 0), z₃ = 13 (15), а следовательно, данный план является оптимальным (теперь уже без кавычек).

Нам не пришлось выполнять 4-й пункт нашего алгоритма в связи с тем, что оптимальное решение найдено, переменные целочисленные. К тому же, все необходимые моменты решения уже были показаны в пунктах 1-3.

Пример, в котором всё складывается не так просто, приведен в Приложении 3.

календарное планирование программирование

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

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

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

§1. Алгоритм решения задачи трех станков методом ветвей и границ

Заданыnдеталей d_i (i= 1, 2, ..., n), последовательно обрабатываемых на трех станках R₁, R₂, R₃, причем технологические маршруты всех деталей одинаковы. Обозначим a_i ,b_i ,c_i — длительность обработки деталей d_iна первом, втором и третьем станках соответственно.

Определить такую очередность запуска деталей в обработку, при которой минимизируется суммарное время завершения всех работ T_ц.

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

Обозначимs_k = (i₁, i₂ , ..., i_k) — некоторую последовательность очередности запуска длиной k(1 £k£n) и A(s_k), В (s_k), С (s_k) — время окончания обработки последовательности деталей s_kна первом, втором и третьем станках соответственно.

Необходимо найти такую последовательность s_опт, что

С(s_опт) = min С (s). (16)

§1.1 Реккурентное вычисление A(s_k), В(s_k), C(s_k) и условие доминирования

Покажем, как можно рекуррентно вычислять A(s_k), В (s_k), С (s_k). Пусть s_k+1 = (s_k ,i_k+i), т. е. последовательность деталей s_k+1получена из деталей s_kс добавлением еще одной детали i_k+1. Тогда:

A (s_k+1) = A (s_k)+

(17),

В (s_k+1) = max [A(s_k+1); В (s_k)] +

(18),

С (s_k+1) = max [В (s_k+1); С (s_k)] +

(19).

Логика выражений (17) – (19) очевидна, особенно если рассмотреть задачу двух станков.

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

Если s — некоторая начальная последовательность, а

— подпоследовательность, образованная из s перестановкой некоторых символов, то вариант s доминирует над , когда выполняются следующие неравенства:

А (s) £ А (

), В (s) £ В ( ), С (s) £ С ( ) (20),

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

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

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

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

d_C(s) = С(s) +

, (21)

d_B(s) = В (s) +

+ , (22)

d_A(s) = A (s) +

+ (23),

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

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

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

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

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

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

D(0) = max {d_A(0), d_B (0), d_C (0)} (25), где

; ; (26).

2) Первыйшаг. ОбразованиемножествG₁⁽¹⁾, G₂⁽¹⁾ , …, G_n⁽¹⁾, подмножествоG_kопределяется всеми последовательностями с началом i_k(k, ...,n).

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

Выбор варианта для продолжения. Из всех подпоследовательностей, построенных на предыдущем шаге, выбирают наиболее перспективную последовательность s_k с наименьшей оценкой, т. е. D(s_k⁽¹⁾)=minD(s_j⁽¹⁾). (28)

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

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

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

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

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

Множество G_s^(k) разбиваем на (n — k) подмножеств, каждое из которых образуется добавлением к последовательности s_s^(k) некоторого элемента i_k+1 такого, что i_k+1

.

Оценка

определяется в соответствии с соотношениями (21) — (24).

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

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

наименьшая из оценок всех вершин, то s_v⁽ⁿ⁾ — искомый вариант.

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

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

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

Таблица 1

Длительность операций	Деталь
	1	2	3	4	5
ai bi ci	2 3 4	5 2 4	1 1 2	3 4 2	3 5 2

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

d_A(s = 0) = A(0) +

+ = 0 + 14 + 3 = 17;

d_B(s = 0) = В(0) +

+ = 0 + 15 + 2 = 17;

d_C(s = 0) = С(0) +

=14 .