ВЫПУСКА ИЗДЕЛИЙ

Введем некоторые обозначения. Пусть {a₁…a_L} - множество всевозможных последовательностей выпуска продукции L модификации; - количество оборудования в группе , где =1,…,N; - время, необходимое на переналадку единицы оборудования -ой группы при переходе с выпуска i-ой модификации на выпуск j-ой модификацию.

Пусть G - ориентированный граф, вершины которого представляют продукты, а существование дуги (х_i, х_i) означает, что продукт j может следовать за продуктом i без перенастройки оборудования. Тогда, если в этом графе есть гамильтонов цикл (ориентированный цикл, проходящий через каждую вершину графа), то существует последовательность выпуска продуктов, не требующая перенастройки оборудования. Если не существует циклической последовательности выпуска продуктов, не требующей перенастройки оборудования, то задача сводится к нахождению последовательности выпуска продуктов, требующих наименьших затрат на перенастройку оборудования.

Пусть х_ij =1, если после продукции i-ой модификации выпускается продукция j-ой модификации; х_ij=0, если после продукции i-ой модификации продукция j-ой модификации не выпускается.

С так введенными переменными ставим задачу:

Минимизировать функцию

(1)

при условиях

, , . (2)

В качестве дополнительных ограничений необходимо наложить условие «петель», для устранения подконтуров в задаче

(3)

Задача (1)-(3) полностью аналогична классической задаче коммивояжера:

(4)

при условиях

, , . (5)

условие «петель»

(6)

В задаче коммивояжера (4)-(6) ищется оптимальная последовательность обхода «городов», а в задаче (1)-(3) оптимальная последовательность выпуска продукции. В задаче (4)-(6) матрица D с элементами является матрица расстояний между N «городами», этой матрице соответствует матрица В в задаче (1)-(3) с элементами , которая является матрицей времени переналадки оборудования

Таким образом, задачу оптимизации последовательности выпуска изделий можно решить методами решения задачи коммивояжера.

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

Существует несколько точных метолов решения задачи коммивояжера: метод ветвей и границ, динамическое программирование и другие. Методов ветвей и границ с использованием ЭВМ можно решать задачи коммивояжера для n£40, динамического программирования – для n£17.

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

На обширном статистическом материале показано, что с увеличением числа городов n ошибка решения убывает. Поэтому при n£40 можно применять точные методы, а при n>40 - приближенные типа «ближайшего соседа».

Рассмотрим алгоритм решения задачи коммивояжера методом ветвей и границ.

Организация метода ветвей и границ содержит следующие этапы:

1) построение дерева допустимых вариантов;

2) составление оценочных задач;

3) формирование правила обхода дерева вариантов;

4) формулировка принципа отбрасывания неперспективного множества вариантов;

5) критерий останова.

1. Построение дерева вариантов осуществляется на основе разбиения множеств на конечное число непересекающихся подмножеств. Факт разбиения множества называется ветвлением и производится на очередном шаге метода в соответствии со сформированным правилом: где где - зафиксированный номер координаты .

2. Оценкой целевой функции называется такое число , что .

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

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

3. Правило обхода дерева вариантов в процессе работы алгоритма называют стратегией обхода дерева. В соответствии с этим правилом на очередном шаге выбирается множество для дальнейшего рассмотрения (ветвления множества).

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

4. Будем называть множество неперспективным, если относительно него принимается решение о выбрасывании его из дальнейшего рассмотрения. Отбрасывание подмножества обеспечивает сокращение перебора.

Рекордным значением называют значение целевой функции в "лучшей" (с минимальным значением целевой функции) из имеющихся допустимых точек к данному моменту времени. По мере получения допустимых точек в процессе работы алгоритма рекорд обновляется. Очевидно справедливо следующее утверждение: если оценка некоторого подмножества больше имеющегося рекорда, то среди точек данного подмножества нет оптимальных точек.

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

5. Признак останова: все подмножества, образовавшиеся в процессе работы алгоритма, оказываются закрытыми. Решением является точка, в которой получено последнее рекордное значение.