Results for точное решение
-
Алгоритм ветвей и границ для задачи о формировании производственных ячеек
The article was published in issue №4
Задача о формировании производственных ячеек является NP-трудной задачей оптимизации ячеечных производственных систем. Из-за большой вычислительной сложности представленной задачи было создано множество эвристических алгоритмов, но малое количество точных.
В статье предлагается метод ветвей и границ, который находит точное решение для текущей задачи, используя групповую эффективность в качестве целевой функции. Для линеаризации этой целевой функции используется метод Динкельбаха. Представленный алгоритм находит оптимальные решения для 24 из 35 известных тестовых данных из литературы, а для оставшихся находит хорошее решение, близкое к известному. Различие от лучшего известного решения всегда меньше 1,5 % в значении целевой функции.