Solving Complex Resource Management Problems: From Classical Optimization and Game Theory to Multi-Agent Technologies for Reaching Consensus

Capa

Citar

Texto integral

Resumo

Challenges and complex problems arising in the resource management of modern enterprises are considered. The existing resource planning models, methods and tools for enterprises are reviewed, and new requirements for adaptive multicriteria resource planning in real time are presented. The concept of autonomous artificial intelligence (AI) systems for adaptive resource planning based on multi-agent technologies is discussed. The evolution of the approach to solving complex resource management problems is described: from traditional optimization of a single objective function, ignoring the individual interests of participants, to game theory with their competition and cooperation. The approach to finding and maintaining a competitive equilibrium (consensus) between participants is further developed via conflict identification and negotiations for conflict resolution with mutual trade-offs. A basic model of a multi-agent demand-supply network with a virtual market and a compensation method for reaching consensus for adaptive resource planning are presented. The functionality and architecture of intelligent adaptive resource planning systems are considered. The implementation results of AI solutions for industrial applications are provided, and the possibility of improving the effectiveness of resource usage by enterprises is shown. Finally, the lessons learned from the experience in R&D work and the prospects of this approach are discussed.

Sobre autores

A. Leonidov

Lebedev Physical Institute, Russian Academy of Sciences; Moscow Institute of Physics and Technology

Autor responsável pela correspondência
Email: leonidovav@lebedev.ru

P. Skobelev

Samara Federal Research Center, Russian Academy of Sciences; Samara State Technical University

Email: p.skobelev@kg.ru

Bibliografia

  1. Capitalizing on Complexity? Insights from the Global Chief Executive Officer Study. – USA: IBM, 2010. – 70 p. – URL: http://www-935.ibm.com/services/us/ceo/ceostudy2010/index.html (дата обращения 04.01.2025). [Accessed January 4, 2025].
  2. Skobelev, P., Trentesaux, D. Disruptions Are the Norm: Cyber-Physical Multi-Agent Systems for Autonomous Real Time Resource Management / In: Service Orientation in Holonic and Multi-agent Manufacturing, series “Studies in Computational Intelligence”. Ed. by T. Borangiu, D. Trentesaux, A. Thomas, et al. – Vol. 694. – Switzerland: Springer, 2017. – P. 287–294.
  3. GARTNER. Top Strategic Predictions for 2016 and Beyond: The Future Is a Digital Thing. – Stamford: Gartner, Inc., 2015. – URL: https://www.gartner.com/en/documents/3142020 (дата обращения 05.01.2025). [Accessed January 5, 2025].
  4. Perez, J.A., Deligianni, F., Ravi, D., Yang, G.-Z. Artificial Intelligence and Robotics. UK-RAS White Paper. – London: Imperial College, 2017. – 48 p. – URL: https://arxiv.org/pdf/1803.10813 (дата обращения 05.01.2025). [Accessed January 5, 2025].
  5. Rzevski, G., Skobelev, P. Managing Complexity. – London-Boston: WIT Press, 2014. – 216 p.
  6. Handbook of Scheduling: Algorithms, Models and Performance Analysis / Ed. by J. Y.-T. Leung. – London-New York: Chapman & Hall/CRC, 2004. – 1224 p.
  7. Vos, S. Meta-heuristics: The State of the Art. Local Search for Planning and Scheduling / In: Lecture Notes in Computer Science. Ed. by A. Nareyek. – Berlin: Springer-Verlag, 2001. – Vol. 2148. – P. 1–23.
  8. Binitha, S., Sathya, S.S. A Survey of Bio inspired Optimization Algorithms // International Journal of Soft Computing and Engineering. – 2012. – Vol. 2, iss. 2. – P. 137–151.
  9. Handbook of Constraint Programming / Ed. by F. Rossi, P. Van Beek, T. Walsh. – Amsterdam: Elsevier, 2006. – 978 p.
  10. Wooldridge, M. An Introduction to Multi-Agent Systems. – Hoboken: John Wiley & Sons, 2009. – 488 p.
  11. Shoham, Y., Leyton-Brown, K. Multi-agent Systems: Algorithmic, Game Theoretic and Logical Foundations. – Cambridge: Cambridge Univ. Press, 2009. – 483 p.
  12. Словохотов Ю.Л., Новиков Д.А. Распределенный интеллект мультиагентных систем. Ч. 1. Основные характеристики и простейшие формы // Проблемы управления. – 2023. – № 5. – С. 3–22. [Slovokhotov, Yu.L., Novikov, D.A. Distributed Intelligence of Multi-Agent Systems. Part I: Basic Features and Simple Forms // Control Sciences. – 2023. – No. 5. – P. 2–17.]
  13. Словохотов Ю.Л., Новиков Д.А. Распределенный интеллект мультиагентных систем. Ч. 2. Коллективный интеллект социальных систем // Проблемы управления. –2023. – № 6. – С. 3–21. [Slovokhotov, Yu.L., Novikov, D.A. Distributed Intelligence of Multi-Agent Systems. Part II: Collective Intelligence of Social Systems // Control Sciences. – 2023. – No. 6. – P. 2–17.]
  14. Davidsson, P., Persson, J., Holmgren, J. On the Integration of Agent-Based and Mathematical Optimization Techniques / In: Agent and Multi-Agent Systems: Technologies and Applications. KES-AMSTA 2007. Lecture Notes in Computer Science. Ed. by N.T. Nguyen, A. Grzech, R.G. Howlett, L.C. Jain. – Berlin, Heidelberg: Springer, 2007. – Vol. 4496. – P. 1–10.
  15. Shen, W., Norrie, D.H. Agent-Based Systems for Intelligent Manufacturing: A State-of-the-Art Survey // Knowledge and Information Systems. – 1999. – Vol. 1. – P. 129–156.
  16. Shen, W., Wang, L., Qi, H. Agent-Based Distributed Manufacturing Process Planning and Scheduling: A State-of-the-Art Survey // IEEE Transactions on Systems, Man and Cybernetics. – 2006. – Vol. 36. – P. 563–577.
  17. Quelhadj, D., Petrovich, S. A Survey of Dynamic Scheduling in Manufacturing Systems // Journal of Scheduling. – 2009. – Vol. 12. – P. 417–431.
  18. Barbati, M., Bruno, M., Genovese, A. Applications of Agent-Based Models for Optimization Problems: A Literature Review // Expert Systems with Applications. – 2012. – Vol. 39. – P. 6020–6028.
  19. Agnestis, A. Multiagent Scheduling Problems // INFORMS Tutorials on Operational Research. – 2014. – P. 151–170.
  20. Lin, G. Y.-J., Solberg, J.J. Intergated Shop Floor Control Using Autonomous Agents // IIE Transactions. – 1992. – Vol. 24. – P. 57–71.
  21. Frey, D., Nimis, J., Worn, H., Lockemann, P. Benchmarking and Robust Multi-agent-Based Production and Control // Engineering Applications of Artificial Intelligence. – 2003. – Vol. 16. – P. 307–320.
  22. Mes, M., van der Heijen, M., van Haarten, A. Comparison of Agent-Based Scheduling to Look-Ahead Heuristics for Real-Time Transportation Problems // European Journal of Operational Research. – 2007. – Vol. 181. – P. 59–75.
  23. Smith, R.G. The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver // IEEE Transactions on Computers. – 1980. – Vol. 29. – P. 1104–1113.
  24. Davis, R., Smith, R.G. Negotiation as a Metaphor for Distributed Problem Solving // Artificial Intelligence. – 1983. – Vol. 20. – P. 63–109.
  25. Reaidy, J., Masotte, P., Diep, D. Comparison of Negotiation Protocols in Dynamic Agent-Based Manufacturing Systems // International Journal of Production Economics. – 2006. – Vol. 99. – P. 117–130.
  26. Ferguson, D., Yemini, Y., Nikolaou, C. Microeconomic Algorithms for Load Balancing in Distributed Computer Systems // Proc. of the 8th International Conference on Distributed Computing Systems. – San Jose, 1988. – P. 491–499.
  27. Waldspurger, C.A., Hogg, T., Huberman, B.A., et al. Spawn: A Distributed Computational Economy // IEEE Transactions on Software Engineering. – 1992. – Vol. 18. – P. 103–117.
  28. Huberman, B.A., Hogg, T. Distributed Computation as an Economic System // Journal of Economic Perspectives. – 1995. – Vol. 9. – P. 141–152.
  29. Wang, J., Hong, Y., Xu J., et al. Cooperative and Competitive Multi-Agent Systems: From Optimization to Games // IEEE/CAA Journal of Automatica Sinica. – 2022. – Vol. 9. – P. 763–783.
  30. Renna, P. A Review of Game Theory Models to Support Production Planning, Scheduling, Cloud Manufacturing and Sustainable Production Systems // Designs. – 2024. – Vol. 8, iss. 2. – Art. no. 26.
  31. Yang, B., Johansson, M. Distributed Optimization and Games: A Tutorial Overview / In: Networked Control Systems. Lecture Notes in Control and Information Sciences. Ed. by A. Bemporad, M. Heemels, M. Johansson. – London: Springer, 2010. – Vol. 406. – P. 109–148.
  32. Madsen, J.R., Shamma, J.S. Game Theory and Distributed Control // Handbook of Game Theory and Applications. – 2015. – Vol. 4. – P. 861–899.
  33. Briand, C., Ngueveu, S.U., Sucha, P. Finding an Optimal Nash Equilibrium to the Multi-agent Scheduling Problem // Journal of Scheduling. – 2017. – Vol. 20. – P. 475–491.
  34. Agnetis, A., Briand, C., Ngueveu, S.U., Sucha, P. Price of Anarchy and Price of Stability in Multi-agent Project Scheduling // Annals of Operations Research. – 2020. – Vol. 285. – P. 97–119.
  35. Hogg, T., Huberman, B.A., Williams, C.P. Phase Transitions and the Search Problem // Artificial Intelligence. – 1996. – Vol. 81. – P. 1–15.
  36. Herroelen, W., De Reyck, B. Phase Transitions in Project Scheduling // Journal of the Operational Research Society. – 1999. – Vol. 50. – P. 148–156.
  37. Easley, D., Kleinberg, J. Networks, Crowds, and Markets: Reasoning about a Highly Connected World. – Cambridge: Cambridge University Press, 2010. – URL: http://www.cs.38. cornell.edu/home/kleinber/networks-book/ (дата обращения 06.01.2025.) [Accessed January 6, 2025].
  38. Wellman, M., Walsh, W.E., Wurman, P., Makkie-Mason, K. Auction Protocols for Decentralized Scheduling // Games and Economic Behavior. – 2001. – Vol. 35. – P. 291–303.
  39. Hall, N.G., Liu, Z. On Auction Protocols for Decentralized Scheduling // Games and Economic Behavior. – 2011. – Vol. 72. – P. 583–585.
  40. Chen, W., Maturana, F., Norrie, D.H. MetaMorph II: An Agent-Based Architecture for Distributed Intelligent Design and Manufacturing // Journal of Intelligent Manufacturing. – 2000. – Vol. 11. – P. 237–251.
  41. Munich, L. Schedule Situations and Their Cooperative Game Theoretic Representations // European Journal of Operational Research. – 2024. – Vol. 316. – P. 767–778.
  42. Cavalieri, S., Garetti, M., Macchi, M., Taisch, M. An Experimental Benchmarking of Two Multi-agent Architectures for Production Scheduling and Control // Computers in Industry. – 2000. – Vol. 43. – P. 139–152.
  43. Brennan, R.W., Norrie, D.H. Evaluating the Performance of Reactive Control Architectures for Manufacturing Production Control // Computers in Industry. – 2001. – Vol. 46. – P. 235–245.
  44. Messie, D., Oh, J.C. Cooperative Game Theory within Multi-agent Systems for Systems Scheduling // Proc. of the 4th International Conference on Hybrid Intelligent Systems (HIS'04). – Kitakyushu, Japan, 2004. – P. 166–171.
  45. Ramos, C. An Architecture and a Negotiation Protocol for the Dynamic Scheduling of Manufacturing Systems // Proc. of the 1994 IEEE International Conference on Robotics and Automation. – San Diego, 1994. – Vol. 4. – P. 3161–3166.
  46. Maturana, F., Shen, W., Norrie, D.H. MetaMorph: An Adaptive Agent-Based Architecture for Intelligent Manufacturing // International Journal of Production Research. – 1999. – Vol. 37. – P. 2159–2173.
  47. Paccagnan, D., Chandan, R., Marsden, J.R. Utility and Mechanism Design in Multi-agent Systems: An Overview // Annual Reviews in Control. – 2022. – Vol. 53. – P. 315–328.
  48. Brussel, H.V., Wyns, J., Valckenaers, P. Reference Architecture for Holonic Manufacturing Systems: PROSA // Computer in Industry. – 1998. – Vol. 37, no. 3. – P. 255–274.
  49. Bongaerts, L., Monostori, L., Mcfarlane, D., Kadar, B. Hierarchy in Distributed Shop Control // Computers in Industry. – 2000. – Vol. 43. – P. 123–137.
  50. Rabelo, R.J., Camarinha-Matos, L.M. Negotiation in Multi-agent Based Dynamic Scheduling // Robotics & Computer-Integrated Manufacturing. – 1994. – Vol. 11. – P. 303–309.
  51. Gou, L., Luh, P.B., Kyoya, Y. Holonic Manufacturing Scheduling: Architecture, Cooperation Mechanism, and Implementation // Computers in Industry. – 1998. – Vol. 37. – P. 213–231.
  52. Skobelev, P. Open Multi-agent Systems for Decision-Making Support // Avtometriya. – 2002. – No. 6. – P. 45–61.
  53. Скобелев П.О., Виттих В.А. Мультиагентные модели взаимодействия для построения сетей потребностей и возможностей в открытых системах // Автоматика и телемеханика. – 2003. – № 1. – С. 177–185. [Skobelev, P.O., Vittikh, V.A. Multiagent Interaction Models for Constructing the Needs-and-Means Networks in Open Systems // Automation and Remote Control. – 2003. – Vol. 64. – P. 162–169.]
  54. Vittikh, V., Skobelev, P. The Compensation Method of Agents Interactions for Real Time Resource Allocation // Avtometriya. – 2009. – No. 2. – P. 78–87.
  55. Skobelev, P. Multi-Agent Systems for Real Time Adaptive Resource Management / In: Industrial Agents: Emerging Applications of Software Agents in Industry. Ed. by P. Leitão, S. Karnouskos. – Amsterdam: Elsevier, 2015. – P. 207–230.
  56. Peretz-Andersson, E., Tabares, S., Mikalef, P., Parida, V. Artificial Intelligence Implementation in Manufacturing SMEs: A Resource Orchestration Approach // International Journal of Information Management. – 2024. – Vol. 77, no. 1. – Art. no. 102781. – doi: 10.1016/j.ijinfomgt.2024.102781
  57. Dwivedi, Y.K. et al. Artificial Intelligence (AI): Multidisciplinary Perspectives on Emerging Challenges, Opportunities, and Agenda for Research, Practice and Policy // International Journal of information management. – 2021. – Vol. 57. – Art. no. 101994.
  58. Yang, W., Li, W., Cao, Y., et al. An Information Theory Inspired Real-Time Self-Adaptive Scheduling for Production-Logistics Resources: Framework, Principle, and Implementation // Sensors. – 2020. – Vol. 20. – Art. no. 7007. – DOI: https://doi.org/10.3390/s20247007
  59. Mourtzis, D. Advances in Adaptive Scheduling in Industry 4.0 // Front. Manuf. Technol. – 2022. – Vol. 2. – Art. no. 937889. – doi: 10.3389/fmtec.2022.937889
  60. Leitão, P., Colombo, A., Karnouskos, S. Industrial Automation Based on Cyber-physical Systems Technologies: Prototype Implementations and Challenges // Computers in Industry. – 2016. – Vol. 81. – P. 11–25.
  61. Городецкий В.И., Ларюхин В.Б., Скобелев П.О. Концептуальная модель цифровой платформы для кибер-физического управления современными предприятиями. Часть I. Цифровая платформа и цифровая экосистема // Мехатроника, автоматизация, управление. – 2019. – T. 20, № 6. – С. 323–332. [Gorodeckij, V.I., Laryuhin, V.B., Skobelev, P.O. Konceptual'naya model' cifrovoj platformy dlya kiber-fizicheskogo upravleniya sovremennymi predpriyatiyami. Part I. Cifrovaya platforma i cifrovaya ekosistema // Mekhatronika, avtomatizaciya, upravlenie. – 2019. – Vol. 20, no. 6. – P. 323–332. (In Russian)]
  62. Rzevski, G., Skobelev, P., Zhilyaev, A. Emergent Intelligence in Smart Ecosystems: Conflicts Resolution by Reaching Consensus in Resource Management // Mathematics. – 2022. – Vol. 10, iss. 11. – Art. no. 1923.
  63. Galuzin, V., Galitskaya, A., Grachev, S., et al. The Autonomous Digital Twin of Enterprise: Method and Toolset for Knowledge-Based Multi-Agent Adaptive Management of Tasks and Resources in Real Time // Mathematics. – 2022. – Vol. 10, iss. 10. – Art. no. 1662.
  64. Грачев С.П., Жиляев А.А., Ларюхин В.Б. Методы и средства построения интеллектуальных систем для решения сложных задач адаптивного управления ресурсами в реальном времени // Автоматика и телемеханика. – 2021. – № 11. – С. 30–67. [Grachev, S.P., Zhilyaev, A.A., Laryukhin, V.B., et al. Methods and Tools for Developing Intelligent Systems for Solving Complex Real-Time Adaptive Resource Management Problems // Automation and Remote Control. – 2021. – Vol. 82, no. 11. – P. 1857–1885.]
  65. Skobelev, P.O., Borovik, S.Y. On the Way from Industry 4.0 to Industry 5.0: From Digital Manufacturing to Digital Society // Industry 4.0. – 2017. – Vol. 2, iss. 6. – P. 307–311.

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML
Baixar


Creative Commons License
Este artigo é disponível sob a Licença Creative Commons Atribuição 4.0 Internacional.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».