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

Обложка

Цитировать

Полный текст

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

Аннотация

Вопросы проектирования устойчивых к сбоям систем производства и поставок продукции составляют одно из приоритетных направлений развития современного исследования операций. Традиционный подход к моделированию таких систем основывается на привлечении вероятностных моделей, описывающих выбор возможного сценария действий в случае возникновения неполадок в производственной или транспортной сети. Наряду с рядом преимуществ данный подход обладает известным недостатком. Возникновение неполадок неизвестной природы, способных поставить под угрозу работоспособность всей моделируемой системы, существенно затрудняют его применение. В данной работе вводится в рассмотрение минимаксная задача построения отказоустойчивых планов производства (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

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

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») на элемент с текстом «Принять и продолжить».