Mathematical models and methods creation for hierarchical planning and decision making in production systems with limited resources
The overall fundamental problem to be solved by the project is the development of mathematical models and methods of hierarchical planning and decision making in a complex organizational and production systems with network representation of technological processes and limited resources.
The methodology for hierarchical models of planning and decision-making constructing in the complex organizational and production systems was created. On its basis the hierarchical planning model corresponding to a new level of mathematical software was developed, in which a general mathematical model of the scheduling problem is replaced by a sequence of discrete mathematical models which are compatible with the hierarchy of decisions that must be taken at each level of management. The system of interrelated models and methods created for solving them takes into account a wide variety of industrial ties, available resources, the production complexity, a large number of production stages, nonsimultaneous inflow of tasks. In contrast to existing methods of planning, the best of which contain a linear or a random combination of different preference rules that does not guarantee the quality of obtained solutions, the strategy for finding a global optimum is defined in the process of solving the planning problem, which allows to obtain solutions close to optimal.
On the basis of the constructive theory for the intractable combinatorial optimization problems solution, which was developed by the authors and has no analogues in the world, a system of new highly interrelated algorithms was created for solving planning problems for different optimization criteria, effective accurate methods and the new modified PDC-algorithms (algorithms with polynomial and decompositional components) for solution of well-known NP-hard scheduling problems underlying the developed models, according to the criteria of total tardiness minimization on single machine (TT) and minimizing the total penalty for tardiness on single machine (TPT). For the TT problem the upper bound of computational complexity of the polynomial component of the algorithm was defined as a third-degree polynomial on the number of jobs; for the exponential component of the algorithm the conditions were defined that in the process of implementation of the algorithm lead to a significant increase of calculations. Statistical investigations have shown that outside these conditions for any individual problem the realized number of directed permutations and pruning for exponential component of the algorithm allows to obtain an exact solution for problems of dimension up to 1000 jobs that can not be done by existing methods. For the TPT problem were obtained solutions for problems not solvable by known techniques, their optimality was proven. The conditions obtained for the polynomial component execution and pruning for the exponential component of the algorithm. The algorithm also allows by implementation of decomposition rules and additional pruning conditions for unpromising options to build fast effective heuristic algorithms with the value of the quality index, which differs slightly from the optimum, with an estimation of this difference for each individual problem.
Based on the new author’s approach of solving the multi-criteria choice problem the mathematical model of optimization were created for linear and convex quadratic programming in Saaty Analytic Hierarchy Process for finding the weights on well or poorly consistent heterogeneous matrices of paired comparisons, the matrices of paired comparisons that do not contain digital information and the matrices of paired comparisons with one-sided constraints. New optimization models solve the problem of finding the weights on poorly consistent heterogeneous matrix and of the solution effectiveness justification, which significantly expands the possibilities of their practical use.
The information technology and integrated software suite were created that implement the planning problems solution in complex organizational and production systems for various optimization criteria and the problem of multi-criteria choice on the basis of new optimization models on heterogeneous matrices of paired comparisons for finding the weights in Saaty Analytic Hierarchy Process. Thus, for the first time the problem of constructing schedules on different optimization criteria and selecting the best of them was solved as the complex.