|
NUMERICAL METHODS AND THE BASIS FOR THEIR APPLICATION
Optimization of task package execution planning in multi-stage systems under restrictions and the formation of sets
K. V. Krotov, A. V. Skatkov Sevastopol state University,
33 Universitetskaya st., Sevastopol, 299053, Russia
Abstract:
Modern methods of complex planning the execution of task packages in multistage systems are characterized by the presence of restrictions on the dimension of the problem being solved, the impossibility of guaranteed obtaining effective solutions for various values of its input parameters, as well as the impossibility of registration the conditions for the formation of sets from the result and the restriction on the interval duration of time of the system operating. The decomposition of the generalized function of the system into a set of hierarchically interconnected subfunctions is implemented to solve the problem of scheduling the execution of task packages with generating sets of results and the restriction on the interval duration of time for the functioning of the system. The use of decomposition made it possible to employ the hierarchical approach for planning the execution of task packages in multistage systems, which provides the determination of decisions by the composition of task groups at the first level of the hierarchy decisions by the composition of task packages groups executed during time intervals of limited duration at the second level and schedules for executing packages at the third level the hierarchy. In order to evaluate decisions on the composition of packages, the results of their execution, obtained during the specified time intervals, are distributed among the packages. The apparatus of the theory of hierarchical games is used to determine complex solutions. A model of a hierarchical game for making decisions by the compositions of packages, groups of packages and schedules of executing packages is built, which is a system of hierarchically interconnected criteria for optimizing decisions. The model registers the condition for the formation of sets from the results of the execution of task packages and restriction on duration of time intervals of its operating. The problem of determining the compositions of task packages and groups of task packages is NP-hard; therefore, its solution requires the use of approximate optimization methods. In order to optimize groups of task packages, the construction of a method for formulating initial solutions by their compositions has been implemented, which are further optimized. Moreover, a algorithm for distributing the results of executing task packages obtained during time intervals of limited duration by sets is formulated. The method of local solutions optimization by composition of packages groups, in accordance with which packages are excluded from groups, the results of which are not included in sets, and packages, that aren't included in any group, is proposed. The software implementation of the considered method of complex optimization of the compositions of task packages, groups of task packages, and schedules for executing task packages from groups (including the implementation of the method for optimizing the compositions of groups of task packages) has been performed. With its use, studies of the features of the considered planning task are carried out. Conclusion are formulated concerning the dependence of the efficiency of scheduling the execution of task packages in multistage system under the introduced conditions from the input parameters of the problem. The use of the method of local optimization of the compositions of groups of task packages allows to increase the number of formed sets from the results of task execution in packages from groups by 60 % in comparison with fixed groups (which do not imply optimization).
Keywords:
task packages, multi-stage system, sets of results, schedule, limiting the duration of time intervals for the system operation.
Received: 17.02.2021 Revised: 22.07.2021 Accepted: 04.08.2021
Citation:
K. V. Krotov, A. V. Skatkov, “Optimization of task package execution planning in multi-stage systems under restrictions and the formation of sets”, Computer Research and Modeling, 13:5 (2021), 917–946
Linking options:
https://www.mathnet.ru/eng/crm926 https://www.mathnet.ru/eng/crm/v13/i5/p917
|
|