ЭЛЕКТРОННЫЙ НАУЧНЫЙ ЖУРНАЛ:

ПРОГРАММНЫЕ ПРОДУКТЫ, СИСТЕМЫ И АЛГОРИТМЫ

Добавить статью

Вход Регистрация

Результаты для запроса: точное решение


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

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

    Статья была опубликована в выпуске №4 от 29 сентября 2017 г.

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

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