Применение метода ветвей и границ для задач календарного планирования (стр. 3 из 3)
Пример 6. Рассмотрим задачу .трех станков, условия которой приведены в табл. 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 |
Нулевой шаг. s = 0.
dA(s = 0) = A(0) +
+ 
= 0 + 14 + 3 = 17;dB(s = 0) = В(0) +
+ mincj= 0 + 15 + 2 = 17;dC(s = 0) = С(0) +
=14 .Тогда
∆ (s = 0) = max {17, 17,14} = 17.
Первый шаг. Конструируем все возможные последовательности длиной 1
s1(1) = 1; s2(1) = 2; s3(1) = 3; s4(1) = 4; s5(1) = 5.
Находим
dA(1) = A1 +
+ 
= 14 + 3 = 17;dB(1)(s = 0) = В1 +
+ 
= 5 + 12 + 2 = 19;dC(1) = С1 +
= 9 + 10 = 19 .Откуда ∆ (1) = max {17, 19, 19} = 19.
Аналогично определяем ∆ (2), ∆ (3), ∆ (4), ∆ (5).
Второй шаг. Среди множества подпоследовательностей длиной 1, s1(1) = 1, s2(1) = 2,..., s5(1) = 5 выбираем наиболее перспективную s = 1, для которой величина оценки-прогноза ∆ (s) оказывается наименьшей. Далее развиваем ее, конструируя возможные варианты длиной 2, т. е. (1.2), (1.3), (1.4), (1.5).
Для каждого из этих вариантов вновь определяем оценки по формулам (1) — (4).
Процесс вычислений продолжаем аналогично.
Процесс построения дерева вариантов приведен на рис. 1.
Каждой конечной вершине дерева вариантов будет отвечать полная последовательность s = i1,i2,,.in. Если для некоторой такой вершины величина оценки ∆ (s) не превосходит величины оценок для всех остальных вершин, то эта оценка определяет искомый оптимальный вариант. В противном случае разбиваем более перспективный вариант с наилучшей оценкой.
Конечная вершина определяет вариант (последовательность)
= 3, 1, 5, 2, 4 с наилучшей оценкой ∆ = 20. Поэтому данный вариант является оптимальным.Непосредственной проверкой убеждаемся, что время обработки всей последовательности деталей для этого варианта совпадает со значением оценки-прогноза и является минимальным:
Летература
1)Зайченко Ю. П., «Исследование операций», Киев «Высшая школа» 1975г.
2)Акулич И.Л., «Математическое программирование в примерах и задачах», Москва «В ысшая школа» 1993г.
3)Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. «Математическое программирование», Москва «В ысшая школа» 1980г.