Search academic texts

Information × Registration Number 0203U002689, 0102U000585 , R & D reports Title The constructive theory development for effective exact algorithms construction for intractable combinatorial problems as the base of mathematical models of complicated systems research popup.stage_title Head Pavlov A.A., Registration Date 26-12-2003 Organization The research institute of information processes of NTUU "KPI" popup.description2 The work's purpose is the development of new created by the authors world analogs-less constructive theory of intractable problems of combinatorial optimization (IPCO) solution, development of theoretical bases and methods of building the effective exact PDC-algorithms (algorithms with polynomial and decopositional components) for their solution. Properties of two types of PDC-algorithms - with additive and unadditive structure - are considered for example problems Maximum Independent Set (MIS), Minimization of Total Weighted Tasks Completion Times Under Order Relation Given by Oriented Acyclic Graph" (MWC). The properties of these problems are investigated, the original exact PDC-algorithms of their solution are developed. The polynomially solvable subclasses of this problems, rules of cuts and computations parallelizing for solution effectiveness increasing are defined. Two algorithms of reduction of the Feasibility problem to MIS are developed. The new original effective algorithms of these problemssolution are developed: Minimization of the Total Weighed Tardiness of Tasks (TWT), Minimization of the Total Tardiness of Tasks (TT). On the basis of these algorithms the approximate algorithms with an estimation of a deviation of solutions from optimum are developed. The conditions at which optimum schedule is reached in polynomial from the problem size time are deduced. The solution algorithms for MWC, TWT and TT and their software were included in the structure of the algorithmware of the Adaptive Automized Scheduling and Functioning Control System for small-series manufactures (SFCSM) that is developed by the authors. We have an engineering and program documentation for SFCSM system, the demonstration version of the system. The project doesn't have analogs in Ukraine. Product Description popup.authors popup.nrat_date 2020-04-02 Close