Задача размещения с ограничениями на объемы производства предприятий на графах древесного вида

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

Аннотация

В данной работе рассматриваются сетевая задача размещения с ограничениями на объемы производства предприятий (CFLP) и ее однородный вариант (UCFLP), в котором объемы производства всех предприятий одинаковые. Мы показываем, что UCFLP на звезде решается за линейное время, если в одной вершине графа не могут одновременно находиться предприятие и клиент, и -трудна, если в каждой вершине могут находиться и предприятие, и клиент. Известно, что задача UCFLP на цепи полиномиально разрешима, мы улучшаем известную схему динамического программирования для этой задачи до оценки , где - количество предприятий, - количество клиентов. Для CFLP на цепи мы предлагаем псевдополиномиальный алгоритм ее решения на основе подхода из работы Мирчандани и др. (1996) с улучшенной временной сложностью, где - суммарный спрос клиентов.
Переведенное названиеCAPACITATED FACILITY LOCATION PROBLEM ON TREE-LIKE GRAPHS
Язык оригиналарусский
Номер статьи2
Страницы (с-по)24-44
Число страниц21
ЖурналTrudy Instituta Matematiki i Mekhaniki UrO RAN
Том28
Номер выпуска2
DOI
СостояниеОпубликовано - 2022

Предметные области OECD FOS+WOS

  • 1.01 МАТЕМАТИКА

ГРНТИ

  • 27 МАТЕМАТИКА

Fingerprint

Подробные сведения о темах исследования «Задача размещения с ограничениями на объемы производства предприятий на графах древесного вида». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать