Search academic texts

Information × Registration Number 0205U006896, 0104U000886 , R & D reports Title The development of the constructive theory of intractable combinatorial problems solution as an algorithmware for informational control systems popup.stage_title Head Pavlov A.A., Registration Date 23-12-2005 Organization National Technscal University of Ukraine "Kiev Polytechnic Institute". popup.description2 The object of research is planning of complex systems functioning. 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 decompositional components) for their solution. As a result of the project release, on the basis of the new constructive theory and methodology of designing PDC-algorithms, new effective PDC-algorithms for the solution of known one-machine IPCO: Total Weighed Completion Time of Tasks Minimization when the order is set by an acyclic graph (WCT) and Total Tardiness of Independent Tasks Minimization were created; new polynomially solvable their subclasses, rules of decomposition to subtasks of the smaller size, rules of cutting unpromising branches at their decision are defined. On the basis of exact PDC-algorithms effective heuristic algorithms were developed for the solution of WCT for its special case when weight factors of all tasks of connectivity graph, except for final tasks, are zero, and for the problem of the One-machine Total Weighed Tardiness of Independent Tasks Minimization. Developed algorithms allow to solve big practical size problems. Properties investigated and the new effective solution algorithm for the problem of the Total Earliness/Tardiness Minimization for independent tasks at one machine regarding due dates was developed. The system of the interconnected algorithms were developed in structure of the Scheduling and Control System for Small-series Manufactures which in a complex solve problems of the coordinated planning with criteria of profit maximization. Product Description popup.authors popup.nrat_date 2020-04-02 Close