FAULT-TOLERANT FAMILIES OF PRODUCTION PLANS: MATHEMATICAL MODEL, COMPUTATIONAL COMPLEXITY AND BRANCH AND BOUND ALGORITHMS

The design of fault-tolerant production and supply systems is one of the priority areas of development of modern operations research. The traditional approach to modeling such systems is based on the use of probabilistic models describing the choice of a possible scenario of actions in the event of failures in the production or transport network. Along with a number of advantages, this approach has a wellknown drawback. The occurrence of failures of an unknown nature that can jeopardize the operability of the entire modeled system significantly complicates its application. In this paper, we introduce the minimax problem of constructing fault-tolerant production plans (Reliable Production Process Design Problem, RPPDP), the purpose of which is to ensure the smooth functioning of a distributed production system with minimal guaranteed costs. It is shown that the RPPDP problem is NP-hard in the strong sense and remains intractable under fairly specific conditions. To find exact and approximate solutions with accuracy estimates for this problem, branch and bound methods have been developed based on the proposed compact model of mixed integer linear programming (MILP) and the author’s heuristics of adaptive large neighborhood search (ALNS) within the framework of extensions of the well-known Gurobi MIP-solver. High performance and complementarity of the proposed algorithms have been confirmed by the results of numerical experiments conducted on an open library of test examples developed by the authors, containing adapted problem statements from the PCGTSPLIB library.