Отказоустойчивые семейства планов производства: математическая модель, вычислительная сложность и алгоритмы ветвей и границ

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