Search academic texts

Information × Registration Number 0201U008143, 0100U000390 , R & D reports Title The development and algorithmical realization of mathematical apparatus for the constructive theory of combinatorial optimization problems decision popup.stage_title Head Pavlov O.A., Registration Date 19-12-2001 Organization The research institute of information processes of NTUU "KPI" popup.description2 The researched object is scheduling of complicated systems functioning. The work purpose is development of theoretical bases, methods and effective exact PDC-algorithms (algorithms with polynomial and decompositional components) for solution of NP-hard combinatorial optimization problems. The intractable problems of combinatorial optimization "Minimization of the total weighed completing moment with the order relation given by oriented acyclic graph" (MWM) and "Minimization of the total penalty for independent tasks completing with due times" (MTP) were investigated. They are included in the structure of the scheduling and functioning control system for small-series manufacture in market conditions (SCSSM). For the MWM problem the exact effective PDC-algorithm of its solution was obtained and its new polynomially solvable subclasses were defined. On the basis of the researches of the MTP problem properties performed, the new properties of optimum solutions of this problem were obtained. The new exact and new approximate algorithms of the MTP problem solution were developed; for the approximate algorithm the estimation of a deviation of solutions from optimum was obtained. The effective fast algorithms for inter-cell scheduling in SCSSM system by criteria of enterprise penalty minimization for delaying products for which due times are given, and also under conditions of such products existence, for which due times during realization can not be broken and minimum duration of cell setup required when a cell consists of one workplace. The researches show that the obtained algorithms are effective and can be used for a solution of some classes of NP-hard problems in polynomial time. Product Description popup.authors popup.nrat_date 2020-04-02 Close