ОТКАЗОУСТОЙЧИВЫЕ СЕМЕЙСТВА ПЛАНОВ ПРОИЗВОДСТВА: МАТЕМАТИЧЕСКАЯ МОДЕЛЬ, ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ И АЛГОРИТМЫ ВЕТВЕЙ И ГРАНИЦ

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Вопросы проектирования устойчивых к сбоям систем производства и поставок продукции составляют одно из приоритетных направлений развития современного исследования операций. Традиционный подход к моделированию таких систем основывается на привлечении вероятностных моделей, описывающих выбор возможного сценария действий в случае возникновения неполадок в производственной или транспортной сети. Наряду с рядом преимуществ данный подход обладает известным недостатком. Возникновение неполадок неизвестной природы, способных поставить под угрозу работоспособность всей моделируемой системы, существенно затрудняют его применение. В данной работе вводится в рассмотрение минимаксная задача построения отказоустойчивых планов производства (Reliable Production Process Design Problem, RPPDP), целью которой является обеспечение бесперебойного функционирования распределенной производственной системы при минимальных гарантированных издержках. Показывается, что задача RPPDP NP-трудна в сильном смысле и сохраняет труднорешаемость при достаточно специфических условиях. Для поиска точных и приближенных решений с оценками точности для данной задачи разработаны методы ветвей и границ, основанные на предложенной компактной модели смешанного целочисленного линейного программирования (Mixed Integer Linear Program, MILP) и авторской эвристике адаптивного поиска в больших окрестностях (Adaptive Large Neighborhood Search, ALNS) в рамках расширений известного MIP-солвера Gurobi. Высокая производительность и взаимодополняемость предложенных алгоритмов подтверждена результатами численных экспериментов, проведенных на разработанной авторами открытой библиотеке тестовых примеров, содержащей адаптированные постановки задач из библиотеки PCGTSPLIB. Библ. 25. Фиг. 5. Табл. 3.

Об авторах

Ю. Ю. Огородников

ИММ им. Н. Н. Красовского УрО РАН

Email: yogorodnikov@imm.uran.ru
Екатеринбург, Россия

Р. А. Рудаков

ИММ им. Н. Н. Красовского УрО РАН

Email: r.a.rudakov@gmail.com
Екатеринбург, Россия

Д. М. Хачай

KEDGE Business School

Email: daniil.khachai@kedgebs.com
Talence, France

М. Ю. Хачай

ИММ им. Н. Н. Красовского УрО РАН

Email: mkhachay@imm.uran.ru
Екатеринбург, Россия

Список литературы

  1. Schilling L., Seuring S. Linking the digital and sustainable transformation with supply chain practices // Int. J. Prod. Res. 2023. https://doi.org/10.1080/00207543.2023.2173502
  2. Fan Y., Schwartz F., Vob S., Woodruff D. L. Catastrophe insurance and flexible planning for supply chain disruption management: a stochastic simulation case study // Int. J. Prod. Res. 2023. https://doi.org/10.1080/00207543.2023.2176179
  3. Fortune S., Hopcroft J., Wyllie J. The directed subgraph homeomorphism problem // Theor. Comput. Sci. 1980. V. 10. N 2. P. 111–121.
  4. Eilam-Tzoreff T. The disjoint shortest paths problem // Discret. Appl. Math. 1998. V. 85. N 2. P. 113–138.
  5. Ferone D., Festa P., Guerriero F., Laganà D. The constrained shortest path tour problem // Comput. Oper. Res. 2016. V. 74. P. 64–77.
  6. Ferone D., Festa‘P., Guerriero F. An efficient exact approach for the constrained shortest path tour problem // Optim. Methods Softw. 2020. V. 35. N 1. P. 1–20.
  7. Martin S., Magnouche Y., Juvigny C., Leguay J. Constrained shortest path tour problem: branch-and-price algorithm // Comp. Oper. Res. 2022. V. 144. P. 105819. https://doi.org/10.1016/j.cor.2022.105819
  8. Saksena J. P., Kumar S. The routing problem with ’k’ specified nodes // Oper. Res. 1966. V. 14. N 5. P. 909–913.
  9. Kudriavtsev A., Khachay D., Ogorodnikov Y., Ren J., Shao S. C., Zhang D., Khachay M. The shortest simple path problem with a fixed number of must-pass nodes: a problem-specific branch-and-bound algorithm // LNCS. 2021. V. 12931. P. 198–210.
  10. Andrade R. C. d. New formulations for the elementary shortest-path problem visiting a given set of nodes // Eur. J. Oper. Res. 2016. V. 254. N 3. P. 755–768.
  11. Gutin G., Punnen A. P. The Traveling Salesman Problem and Its Variations. B.: Springer. 2007.
  12. Papadimitriou C. Euclidean TSP is NP-complete // Theor. Comput. Sci. 1977. V. 4. P. 237–244.
  13. Khachay M., Ukolov S., Petunin A. Problem-Specific Branch-and-Bound Algorithms for the Precedence Constrained Generalized Traveling Salesman Problem // LNCS. 2021. V. 13078. P. 136–148.
  14. Chentsov A. G., Khachai M. Y., Khachai D. M. An exact algorithm with linear complexity for a problem of visiting megalopolises // Proc. Steklov Inst. Math. 2016. V. 295. N 1. P. 38–46.
  15. Khachai M. Y., Neznakhina E. D. Approximation schemes for the Generalized Traveling Salesman Problem // Proc. Steklov Inst. Math. 2017. V. 299. Suppl. 1. P. 97–105.
  16. Khachay M., Neznakhina K. Complexity and approximability of the Euclidean Generalized Traveling Salesman Problem in grid clusters // Ann. Math. Artif. Intell. 2020. V. 88. N 1. P. 53–69.
  17. Khachay M., Kudriavtsev A., Petunin A. PCGLNS: A heuristic solver for the Precedence Constrained Generalized Traveling Salesman Problem // LNCS. 2020. V. 12422. P. 196–208.
  18. Morin T. L., Marsten R. E. Branch-and-bound strategies for dynamic programming // Oper. Res. 1976. V. 24. N 4. P. 611–627.
  19. Khachai D., Sadykov R., Battaia O., Khachay M. Precedence Constrained Generalized Traveling Salesman Problem: Polyhedral study, formulations, and branch-and-cut algorithm // Eur. J. Oper. Res. 2023. V. 309. N 2. P. 488–505.
  20. Salman R., Ekstedt F., Damaschke P. Branch-and-bound for the Precedence Constrained Generalized Traveling Salesman Problem // Oper. Res. Lett. 2020. V. 48. N 2. P. 163–166.
  21. Gurobi Optimization. Gurobi optimizer reference manual (2021), https://www.gurobi.com/ documentation/9.5/refman/index.html
  22. Ropke S., Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows // Transp. Sci. 2006. V. 40. P. 455–472.
  23. Kalateh Ahani I., Salari M., Hosseini S. M., Iori M. Solution of minimum spanning forest problems with reliability constraints // Comput. Ind. Eng. 2020. Vol. 142. P. 106365. https://doi.org/10.1016/j.cie.2020.106365
  24. Smith S. L., Imeson F. GLNS: An effective large neighborhood search heuristic for the Generalized Traveling Salesman Problem // Comp. Oper. Res. 2017. V. 87. P. 1–19.
  25. Gendreau M., Potvin J.-Y. Handbook of Metaheuristics. Cham: Springer. 2019.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2024