RUS  ENG
Full version
JOURNALS // Vestnik Yuzhno-Ural'skogo Universiteta. Seriya Matematicheskoe Modelirovanie i Programmirovanie // Archive

Vestnik YuUrGU. Ser. Mat. Model. Progr., 2022 Volume 15, Issue 2, Pages 70–85 (Mi vyuru640)

Programming & Computer Software

Construction of schedules for the performance of task packages in multi-stage systems when forming sets of results and limitations

K. V. Krotov, A. V. Skatkov

Sevastopol state University, Sevastopol, Russian Federation

Abstract: We consider a complex problem on scheduling of performance of task packages in a multi-stage systems when there is a limit on the duration of time intervals for its operation. Solution of such a problem implies (taking into account the requirements of forming sets of results) determination of composition of packages, groups of packages performed within time intervals of specified duration, schedules for performance of packages on devices of multi-stage system. To determine complex solutions, the apparatus of the theory of hierarchical games is used. We construct the model of a hierarchical game to make decision on the composition of packages, package groups and scheduling of package performance. The model takes into account the requirement to create sets from the results of performance of task packages. The problem of determining the composition of groups of packages is NP-hard, so solution of this problem requires the use of approximate optimization methods. We formulate a method for constructing an initial solution based on the composition of groups of packages and a method for distributing the results of performance of task packages by sets. Also, we formulate a method for optimizing the composition of groups of task packages taking into account the formation of sets. A method for construction of new solutions by composition of group of task packages is formulated. We obtain conditions that allow to determine packages excluded from groups based on the number of results of performance of task of each type, which are not included in sets. The method of local optimization of solutions by composition of packages groups is proposed. The software for the considered method of complex optimization of the compositions of task packages, groups of task packages, and schedules for performance of task packages from groups is implemented.

Keywords: task packages, multi-stage system, sets of results, restriction on duration of time intervals of system operation.

UDC: 004.453

MSC: 90B35

Received: 23.07.2021

DOI: 10.14529/mmp220206



© Steklov Math. Inst. of RAS, 2024