Kryvtsun O. Fragmentary models for PCB routing, packing and logical design problems

The thesis is devoted to the study of the fragmentary structure properties and models on the basis of these structures, which is created to find the approximate optimal solutions to the problems of PCB (printed circuit board) routing, 3D packing and logical design. The necessary and sufficient conditions of matching unlabeled connected digraph to a class of isomorphic fragmentary structures are established. The criterion of matching labeled digraph to a fragmentary structure is established. Fragmentary models for PCB routing, three-dimensional packing and logical design problems are built. For fragmentary models of PCB routing problem and logical design problem it is shown that constructed fragmentary algorithms have polynomial time complexity, and corresponding fragmentary structures have the property of reachability. The software, that generates test instances with different structures, was developed for a minimal set of axioms search problem. A comparative analysis of the quality estimates of the proposed models and methods is made. A new method for solving the problem of three-dimensional packing of various type containers is constructed.