Алгоритм ветвей и границ для задачи о формировании производственных ячеек

Программные продукты, системы и алгоритмы. 2017. № 4. С. 1–10.

Уткина И. Е., Бацын М. В.

Задача о формировании производственных ячеек является NP-трудной задачей оптимизации ячеечных производственных систем. Из-за большой вычислительной сложности представленной задачи, было создано множество эвристических алгоритмов, но малое количество точных. В этой статье мы предлагаем метод ветвей и границ, который находит точное решение для текущей задачи, используя групповую эффективность в качестве целевой функции. Для линеаризации этой целевой функции мы используем метод Динкельбаха. Наш алгоритм находит оптимальные решения для 24 из 35 известных тестовых данных из литературы, а для оставшихся находит хорошее решение, близкое к известному. Различие от лучшего известного решения всегда меньше 1.5% в значении целевой функции. 

Ключевые слова: бикластеризация, Branch and Bound algorithm, cell formation problem, метод ветвей и границ, biclustering, Dinkelbach algorithm, точное решение, exact solution, Формирование производственных ячеек, метод Динкельбаха