Software Journal:
Theory and Applications

Send article

Entrance Registration

Results for точное решение

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

    И.Е. Уткина Национальный исследовательский университет Высшая школа экономики, Нижний Новгород, Russian Federation;
    М.В. Бацын Национальный исследовательский университет Высшая школа экономики, Нижний Новгород, Russian Federation;

    The article was published in issue №4

    Задача о формировании производственных ячеек является NP-трудной задачей оптимизации ячеечных производственных систем. Из-за большой вычислительной сложности представленной задачи было создано множество эвристических алгоритмов, но малое количество точных.

    В статье предлагается метод ветвей и границ, который находит точное решение для текущей задачи, используя групповую эффективность в качестве целевой функции. Для линеаризации этой целевой функции используется метод Динкельбаха. Представленный алгоритм находит оптимальные решения для 24 из 35 известных тестовых данных из литературы, а для оставшихся находит хорошее решение, близкое к известному. Различие от лучшего известного решения всегда меньше 1,5 % в значении целевой функции.