Intractable problems of combinatorial optimization and the theory of PSC-algorithms

The work continues a series of works devoted to the development of the theory of PSC-algorithms and to the creation on its basis of models and methods of scheduling, operational planning, and decision-making in complex socio-economic systems with a network representation of technological processes and limited resources. The purpose of the work is to develop the authors’ theory and methodology for PSC-algorithms constructing for intractable problems of combinatorial optimization (IPCO – problems for which there are no polynomial time solving algorithms) and to create on their basis highly efficient methods to solve the studied scheduling and operational planning problems.

PSC-algorithms include the polynomial component that builds a strictly optimal solution and the exact exponential subalgorithm or the polynomial approximation of the exact algorithm (approximation or heuristic algorithm). The advantage of PSC-algorithms over existing methods is that they can be used to construct, for large-scale problems, both exact and approximation algorithms with estimates of the deviation of obtained solutions from the optimum, or heuristic algorithms.

In this work, based on the theory of PSC-algorithms, we have created new methods and efficient PSC-algorithms for five IPCO, in particular, for two of the six most complex and world-wide-known classical IPCO: NP-hard in the strong sense problems of the total weighted completion time of jobs minimization on one machine with a precedence relations and the total weighted tardiness of jobs minimization on one machine. We also investigated the efficiency of four other PSC-algorithms. Then we included the created PSC-algorithms into the mathematics and software of the four-level model of scheduling and operational planning in systems with network representation of technological processes and limited resources which we developed in the previous works. As a result, we have created an information technology and a new integrated software package for scheduling and operational planning in socio-economic systems in various fields of application.