Алгоритм решения задач оптимального распределения реентерабельных ресурсов на сетевых графиках
- Авторы: Косоруков О.А1,2, Лемтюжникова Д.В3,4
-
Учреждения:
- МГУ им. М. В. Ломоносова
- РАНХиГС при Президенте РФ
- Институт проблем управления им. В. А. Трапезникова РАН
- МАИ (национальный исследовательский университет)
- Выпуск: № 2 (2024)
- Страницы: 23-29
- Раздел: Математические проблемы управления
- URL: https://bakhtiniada.ru/1819-3161/article/view/273419
- DOI: https://doi.org/10.25728/pu.2024.2.2
- ID: 273419
Цитировать
Полный текст
Аннотация
Рассматривается задача распределения реентерабельных ресурсов при выполнении комплекса взаимозависимых работ, представленного в виде сетевого графика. Предполагается линейная зависимость времени выполнения работ от используемых ресурсов. Обосновывается алгоритм построения решения для работ с предопределенной последовательностью наступления событий в сетевом графике комплекса работ. Предлагается алгоритм сведения задачи общего вида к вспомогательной задаче с упорядоченными временами наступления событий, а также алгоритм построения оптимального решения исходной задачи. Сходимость данного алгоритма обусловлена конечностью итераций на каждом из этапов. Общая вычислительная сложность алгоритма может быть оценена как O(n2), где n – количество вершин в исходном сетевом графике. Представляется перспективным применение предложенного алгоритма для планирования комплексов взаимосвязанных работ с использованием реентерабельных ресурсов.
Ключевые слова
Об авторах
О. А Косоруков
МГУ им. М. В. Ломоносова; РАНХиГС при Президенте РФ
Email: kosorukovoa@mail.ru
г. Москва, Россия
Д. В Лемтюжникова
Институт проблем управления им. В. А. Трапезникова РАН; МАИ (национальный исследовательский университет)
Email: darabbt@gmail.com
г. Москва, Россия
Список литературы
- Давыдов Э.Г. Игры, графы, ресурсы. – М.: Радио и связь, 1981. – 113 c. [Davydov, E.G. Igry, grafy, resursy. – M.: Radio I svyaz’, 1981. – 113 s. (In Russian)] ]
- Бурков В.Н., Горгидзе И.А., Ловецкий С.Е. Прикладные задачи теории графов. – Тбилиси: Мецнииреба, 1974. – 234 с. [Burkov, V.N., Gorgidze ,I.A., Loveckij, S.E. Prikladnye zadachi teorii grafov. – Tbilisi: Mecniireba, 1974. – 234 s. (In Russian)]
- Косоруков О.А., Лемтюжникова Д.В., Мищенко А.В. Методы и модели управления ресурсами проекта в условиях неопределенности // Известия РАН. Теория и системы управления. – 2023. – № 3. – С. 38–56. [Kosorukov, O.A., Lemtyuzhnikova, D.V., Mishchenko, A.V. Metody i modeli upravleniya resursami proekta v usloviyah neopredelennosti // Izvestiya RAN. Teoriya i sistemy upravleniya. – 2023. – No. 3. – P. 38–56. (In Russian)]
- Mironov, A.A., Tsurkov, V.I. Transport-Type Problems with a Minimax Criterion // Automation and Remote Control. – 1995. – No. 12. – P. 109–118.
- Ляхов О.А. Ресурсы в сетевом планировании сложных комплексов работ // Проблемы информатики. – 2013. – № 1 (18). – С. 27–36. [Lyahov, O.A. Resursy v setevom planirovanii slozhnyh kompleksov rabot // Problemy informatiki. – 2013. – No. 1 (18). – P. 27–36. (In Russian)]
- Разумихин Б.С. Задача об оптимальном распределении ресурсов // Автоматика и телемеханика. – 1965. – Т. 26. – Вып. 3. – С. 1227–1247. [Razumikhin, B.S. The Problem on Optimal Resources Distribution // Automation and Remote Control. – 1965. – Vol. 26, no. 7. – P. 1227–1246. (In Russian)]
- Mishenko, А., Kosorukov, О., Sviridova, О. Optimization of Works Management of the Investment Project // The 2-nd International & European Conference «Modelling and Simulation of Social-Behavioural Phenomena in Creative Societies» (MSBC-2022). – Vilnius, 2022. – P. 201–217.
- Gehring, М., Volk, R., Schultmann, F. On the Integration of Diverging Material Flows into Resource‐Constrained Project Scheduling // European Journal of Operational Research. – 2022. – Vol. 303, iss. 3. – P. 1071–1087.
- Bianco, L., Caramia, M., Giordani, S. Project Scheduling with Generalized Precedence Relations: A New Method to Analyze Criticalities and Flexibilities // European Journal of Operational Research. – 2022. – Vol. 298, iss. 2. – P. 451–462.
- de Lima, V.L., Alves, C., Clautiaux, F., et al. Arc Flow Formulations Based on Dynamic Programming: Theoretical Foundations and Applications // European Journal of Operational Research. – 2022. – Vol. 296, iss. 1. – P. 3–21.
- Майника Э. Алгоритмы оптимизации на сетях и графах. – М.: Изд-во «Мир», 1981. – 319 с. [Minieka, E. Optimization Algorithms for Networks and Graphs. – New York: M. Dekker, 1978.]
- Филиппова А.С., Поречный С. С., Рамазанова Р.Р. Основы комбинаторных алгоритмов. – Уфа: Изд-во БГПУ, 2018. – 131 с. [Filippova, A.S., Porechnyj, S.S., Ramazanova, R.R. Osnovy kombinatornyh algoritmov. – Ufa: Izd-vo BGPU, 2018. – 131 s. [(In Russian)]
Дополнительные файлы
