TY - JOUR

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

AU - Ageev, Alexander Alexandrovich

AU - Gimadi, Edward Khairutdinovich

AU - Tsidulko, O. Yu

AU - Shtepa, Alexandr Alexandrovich

N1 - Агеев А.А., Гимади Э.Х., Цидулко О.Ю., Штепа А.А. Задача размещения с ограничениями на объемы производства предприятий на графах древесного вида // Труды института математики и механики УрО РАН. – 2022. – Т. 28. – № 2. – С. 24-44. Работа выполнена в рамках государственного задания ИМ СО РАН (проект FWNF-2022-0019) и при финансовой поддержке РФФИ (проект 20-31-90091).

PY - 2022

Y1 - 2022

N2 - В данной работе рассматриваются сетевая задача размещения с ограничениями на объемы производства предприятий (CFLP) и ее однородный вариант (UCFLP), в котором объемы производства всех предприятий одинаковые. Мы показываем, что UCFLP на звезде решается за линейное время, если в одной вершине графа не могут одновременно находиться предприятие и клиент, и -трудна, если в каждой вершине могут находиться и предприятие, и клиент. Известно, что задача UCFLP на цепи полиномиально разрешима, мы улучшаем известную схему динамического программирования для этой задачи до оценки , где - количество предприятий, - количество клиентов. Для CFLP на цепи мы предлагаем псевдополиномиальный алгоритм ее решения на основе подхода из работы Мирчандани и др. (1996) с улучшенной временной сложностью, где - суммарный спрос клиентов.

AB - В данной работе рассматриваются сетевая задача размещения с ограничениями на объемы производства предприятий (CFLP) и ее однородный вариант (UCFLP), в котором объемы производства всех предприятий одинаковые. Мы показываем, что UCFLP на звезде решается за линейное время, если в одной вершине графа не могут одновременно находиться предприятие и клиент, и -трудна, если в каждой вершине могут находиться и предприятие, и клиент. Известно, что задача UCFLP на цепи полиномиально разрешима, мы улучшаем известную схему динамического программирования для этой задачи до оценки , где - количество предприятий, - количество клиентов. Для CFLP на цепи мы предлагаем псевдополиномиальный алгоритм ее решения на основе подхода из работы Мирчандани и др. (1996) с улучшенной временной сложностью, где - суммарный спрос клиентов.

KW - Capacitated Facility Location Problem

KW - dynamic programming

KW - NP-hard problem

KW - path graph polynomial time algorithm

KW - pseudo-polynomial time algorithm

KW - star graph

KW - Uniform Capacitated Facility Location Problem

UR - http://www.scopus.com/inward/record.url?scp=85134827224&partnerID=8YFLogxK

UR - https://elibrary.ru/item.asp?id=48585943

UR - https://www.mendeley.com/catalogue/04b24995-6c56-3ea5-96a2-a0811a69b727/

U2 - 10.21538/0134-4889-2022-28-2-24-44

DO - 10.21538/0134-4889-2022-28-2-24-44

M3 - статья

AN - SCOPUS:85134827224

VL - 28

SP - 24

EP - 44

JO - Trudy Instituta Matematiki i Mekhaniki UrO RAN

JF - Trudy Instituta Matematiki i Mekhaniki UrO RAN

SN - 0134-4889

IS - 2

M1 - 2

ER -