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.

Bibliographie

[1] Haefner J. W., “Parallel computers and individual-based models: an overview”, Individual-based models and approaches in ecology, Chapman and Hall/CRC, 2018, 126–164 | DOI

[2] Gupta C.B., Optimization techniques in operation research, 2-nd Kindle edition, U.K. International Publishing House, 2012, 386 pp.

[3] Wooldridge M., An Introduction to Multi-Agent Systems, 2nd Edition, John Wiley Sons, Chichester, U.K, 2009, 484 pp.

[4] Deng C. et all., “An effective grid-based and density-based spatial clustering algorithm to support parallel computing”, Pattern Recognition Letters, 109 (2018), 81–88 | DOI

[5] Pinedo M.L., Scheduling. Theory: Algorithms and systems, Springer. Science+Business media, 2016, 670 pp. | MR | Zbl

[6] Khodr Y.M., Scheduling Problems and Solutions, Computer Science, Technology and Application, Nova Science Pub Inc, 2012, 330 pp.

[7] Drozdowski M., Scheduling for Parallel Processing, Computer Communications and Networks, Springer, 2009, 386 pp. | DOI | MR | Zbl

[8] Gawiejnowicz S., Time-Dependent Scheduling, Monographs in Theoretical Computer Science. An EATCS Series, Springer, 2008, 380 pp. | MR | Zbl

[9] Ching W.K., Huang X., Ng M.K., Siu T.K., Markov Chains: Models, Algorithms and Applications, International Series in Operations Research Management Science, 189, Springer Science + Business Media NY, 2013, 241 pp. | MR | Zbl

[10] Yang T., Zhang L., Yin X., “Time-varying gain-scheduling-error mean square stabilization of semi-Markov jump linear systems”, IET Control Theory Applications, 10:11 (2016), 1215–1223 | DOI | MR

[11] Jiang Q., Xi H.-S., Yin B.-Q., “Event-driven semi-Markov switching state-space control processes”, IET Control Theory Applications, 6:12 (2012), 1861–1869 | DOI | MR

[12] Janssen J., Manca R., Applied Semi-Markov processes, Springer US, 2005, 310 pp. | MR

[13] Ivutin A.N., Larkin E.V., “Simulation of Concurrent Games”, Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, Chelyabinsk, 8:2 (2015), 43–54 | Zbl

[14] Larkin E.V., Ivutin A.N., Kotov V.V., Privalov A.N., “Simulation of Relay-races”, Bulletin of the South Ural State University. Mathematical Modelling, Programming Computer Software, 9:4 (2016), 117–128 | Zbl

[15] Larkin E., Bogomolov A., Privalov A., “Discrete model of mobile robot assemble fault-tolerance”, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 11659, 2019, 204–215

[16] Akimenko T.A., Larkin E.V., “The temporal characteristics of a wandering along parallel semi-Markov chains”, 4th International Conference on Data Mining and Big Data (Chiang Mai, Thailand, 2019), Communications in Computer and Information Science, 1071, 2019, 80–89 | DOI

[17] Bielecki T.R., Jakubowski J., Niewęgłowski M., “Conditional Markov chains: Properties, construction and structured dependence”, Stochastic Processes and their Applications, 127:4 (2017), 1125–1170 | DOI | MR | Zbl

[18] Deo N., Graph theory with applications to Engineering and computer science, Dover Publications, N.Y., 2016, 496 pp. | MR

[19] Oltean M., “A light-based device for solving the Hamiltonian path problem”, Unconventional Computing, Lecture Notes in Computer Science, 4135, Springer, 2006, 217–227 | DOI | MR | Zbl

[20] Björklund A., “Determinant sums for undirected Hamiltonicity”, Proc. 51-st IEEE Symposium on Foundations of Computer Science, FOCS'10, 2010, 173–182

[21] Kobayashi H., Marl B.L., Turin W., Probability, Random Processes and Statistical Analysis, Cambridge University Press, 2012, 812 pp. | MR | Zbl

[22] Grimmett G.R., Stirzaker D.R., Probability and Random Processes, Clarendon Press, Oxford, 2001, 608 pp. | MR

[23] Larkin E.V., Ivutin A.N., Troshina A., “Model of interruptions in Swarm unit”, Advances in swarm intelligence, Proceedings of 8-th International conference ICSI (Fukuoka, Japan 2017), v. 1, 50–59