Метод ветвей и границ является универсальным методом решения комбинаторных задач дискретного программирования. Сложность практического применения метода заключается в трудностях нахождения способа ветвления множества на подмножества и вычисления соответствующих оценок, которые зависят от специфики конкретной задачи.
Для того, чтобы выяснить области применения данного метода и ознакомиться с практической его формой, мы обратимся к задаче трех станков, как к классическому примеру.
§1. Алгоритм решения задачи трех станков методом ветвей и границ
Заданы n деталей di (i = 1, 2, ., n), последовательно обрабатываемых на трех станках R1, R2, R3, причем технологические маршруты всех деталей одинаковы. Обозначим ai ,bi ,ci - длительность обработки деталей di на первом, втором и третьем станках соответственно.
Определить такую очередность запуска деталей в обработку, при которой минимизируется суммарное время завершения всех работ Tц.
Можно показать, что в задаче трех станков очередность выполнения первых, вторых и третьих операций в оптимальном решении может быть одинаковой (для четырех станков это свойство уже не выполняется). Поэтому достаточно определить очередность запуска только на одном станке (например, третьем).
Обозначим sk = (i1, i2 , ., ik) - некоторую последовательность очередности запуска длиной k (1 £ k £ n) и A (sk), В (sk), С (sk) - время окончания обработки последовательности деталей sk на первом, втором и третьем станках соответственно.
Необходимо найти такую последовательность sопт, что
С(sопт) = min С (s). (16)
§1.1 Реккурентное вычисление A(sk), В(sk), C(sk) и условие доминирования
Покажем, как можно рекуррентно вычислять A (sk), В (sk), С (sk). Пусть sk+1 = (sk ,ik+i), т. е. последовательность деталей sk+1 получена из деталей sk с добавлением еще одной детали ik+1. Тогда:
A (sk+1) = A (sk)+ (17),
В (sk+1) = max [A (sk+1); В (sk)] + (18),
С (sk+1) = max [В (sk+1); С (sk)] + (19).
Логика выражений (17) - (19) очевидна, особенно если рассмотреть задачу двух станков.
Для задачи трех станков можно использовать следующее правило доминирования:
Если s - некоторая начальная последовательность, а - подпоследовательность, образованная из s перестановкой некоторых символов, то вариант s доминирует над
, когда выполняются следующие неравенства:
А (s) £ А (), В (s) £ В (
), С (s) £ С (
) (20),
причем хотя бы одно из них выполняется как строгое неравенство.
§1.2 Способ конструирования вариантов последовательностей s и вычисления оценок D(s) для каждого из них
Способ конструирования вариантов последовательностей s и вычисления оценок D(s) для каждого из них состоит в следующем:
Пусть имеется начальная подпоследовательность s. Тогда вычисляются величины:
dC(s) = С(s) +, (21)
dB(s) = В (s) + +
, (22)
dA(s) = A (s) + +
(23),
где J (s) - множество символов, образующих последовательность s.
За оценку критерия С(s) для варианта s можно принять величину
D(s) = max {dA(s), dB (s), dC (s)} (24).
Управление персоналом предприятия делится на три главных направления: стратегическое, оперативное и обеспечение.
Наиболее ранним подходом к оценке стиля управления был взгляд, основанный на оценке личных качеств.