Paired discrete competition with a free route choice

E. V. Larkin ; A. N. Privalov ; Yu. I. Bogatyreva

Čebyševskij sbornik, Tome 22 (2021) no. 2, pp. 145-159

Résumé

The paper considers the problem of optimizing the operation schedule for multiprocessor systems. The solution to this problem involves the formation of a rigid work schedule, which determines the rhythm of the processes, but in practice the functioning of systems is influenced by many side factors that make the intervals of work execution random. In the work, a semi-Markov model of the formation of a stochastic schedule in conditions of pair competition is constructed. It is shown that if during the functioning of the system it is possible to execute the items of the schedule in an arbitrary order, then the evolution of the semi-Markov process follows the Hamiltonian path. It is proved that all possible realizations of Hamiltonian paths form a complete group of incompatible events. It is noted that, due to the imposition of restrictions on the nature of evolution, the evolution process is not strictly semi-Markov, and therefore a method of forming a strictly semi-Markov process with a tree structure from the primary model is proposed. Dependences are obtained for calculating the distribution densities and the probabilities of switching from states of a semi-Markov process to conjugate states, as well as the time of walking from the starting to absorbing states. Using the concept of paired discrete competition and a distributed penalty, the effectiveness of the choice of a Hamiltonian path by one of the subjects is estimated, taking into account the fact that the algorithm of his opponent's behavior is known up to the construction of a semi-Markov model.

Détail

Keywords: competition, route, Hamiltonian path, full group of inconsistent events, discrete distribution, forfeit discipline.