Гимади Э.Х. Цидулко О.Ю. Штепа А.А.
Улучшенный точный алгоритм для задачи размещения с ограничениями на объемы производства на графе-цепи
Докладчик: Штепа А.А.
Исследуется задача размещения с ограничениями на объемы производства (Capacitated Facility Location Problem, CFLP). Дан неориентированный граф G=(V,E), множество вершин V графа состоит из двух не пересекающихся подмножеств: множества M, |M|=m возможных мест размещения предприятий по производству некоторого продукта и множества N, |N|=n потребителей этого продукта. Для вершины i из M известны: стоимость открытия предприятия fi и объем производства предприятия ai. Для вершины j из N известен спрос потребителя bj. Для каждого ребра e из E дана стоимость транспортировки единицы продукта ce. Требуется разместить предприятия таким образом, чтобы удовлетворить спрос всех потребителей и ограничения на объемы производства с минимальными затратами на открытие предприятий и транспортировку продукта потребителям. В работе предлагается точный псевдополиномиальный алгоритм решения этой задачи на графе-цепи с трудоемкостью O(mB), что быстрее, чем лучший известный алгоритм в статье [Mirchandani et. al, 1996] со временем работы O(mB min{amax,B}), где B=∑bj - суммарный спрос, amax - максимальный объем производства предприятия.
К списку докладов