Registration Number
0220U100685,
0117U000460
, R & D reports
Title
Intractable combinatorial optimization problems and the theory of PSC-algorithms
popup.stage_title
Head
Pavlov Oleksandr A., Доктор технічних наук
Registration Date
23-01-2020
Organization
National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
popup.description2
The work continues a series of works devoted to the development of the authors’ theory and methodology of PSC-algorithms constructing for intractable problems of combinatorial optimization (IPCO – problems for which there are no polynomial time solving 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. 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.
Product Description
popup.authors
Zhdanova Olena G.
Kovaliuk Tetiana V.
Lysetskyi Taras M.
Misura Elena B.
Melnikov Oleg V.
Pavlov Alexander A.
Sperkach Maya O.
Khalus Elena A.
popup.nrat_date
2020-04-02
