Paired discrete competition with a free route choice
https://doi.org/10.22405/2226-8383-2021-22-2-145-159
Abstract
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.
About the Authors
Evgenii Vasil’evich Larkin
Tula State University
Russian Federation
Russian Federation
doctor of technical sciences
Alexander Nikolaevich Privalov
Tula State Lev Tolstoy Pedagogical University
Russian Federation
Russian Federation
doctor of technical sciences
Yulia Igorevna Bogatyreva
doctor of pedagogical sciences
Russian Federation
Russian Federation
Tula State Lev Tolstoy Pedagogical University
References
1. Haefner J. W., 2018, “Parallel computers and individual-based models: an overview” In:
2. Individual-based models and approaches in ecology, Chapman and Hall/CRC, pp. 126 - 164.
3. Gupta C.B., 2012, Optimization techniques in operation research, 2-nd Kindle edition. U.K.
4. International Publishing House, 386 p.
5. Wooldridge M., 2009, An Introduction to Multi-Agent Systems. 2nd Edition. Chichester, U.K:
6. John Wiley & Sons, 484 p.
7. Deng C. et all., 2018, An effective grid-based and density-based spatial clustering algorithm to
8. support parallel computing, In: Pattern Recognition Letters, vol. 109. pp.. 81 - 88.
9. Pinedo M.L., 2016, Scheduling. Theory: Algorithms and systems, Springer. Science+Business
10. media, 670 p.
11. Khodr Y.M., 2012, Scheduling Problems and Solutions (Computer Science, Technology and
12. Application), Nova Science Pub Inc., 330 p.
13. Drozdowski M., 2009, Scheduling for Parallel Processing (Computer Communications and
14. Networks), Springer, 386 p.
15. Gawiejnowicz S., 2008, Time-Dependent Scheduling (Monographs in Theoretical Computer
16. Science. An EATCS Series). Springer, 380 p.
17. Ching W.K., Huang X., Ng M.K., Siu T.K., 2013, Markov Chains: Models, Algorithms and
18. Applications, In: International Series in Operations Research & Management Science, vol.
19. , Springer Science + Business Media NY, 241 p.
20. Yang T., Zhang L., Yin X., 2016, Time-varying gain-scheduling-error mean square stabilization
21. of semi-Markov jump linear systems In: IET Control Theory & Applications, vol. 10. Iss. 11,
22. pp. 1215 – 1223.
23. Jiang Q., Xi H.-S., Yin B.-Q., 2012, Event-driven semi-Markov switching state-space control
24. processes, In: IET Control Theory & Applications, vol. 6, Iss. 12, pp. 1861 – 1869.
25. Janssen J., Manca R., 2005, Applied Semi-Markov processes. Springer US, 310 p.
26. Ivutin A.N, Larkin E.V., 2015, Simulation of Concurrent Games In: Bulletin of the South
27. Ural State University. Series: Mathematical Modelling, Programming and Computer Software,
28. Chelyabinsk, vol. 8. no. 2, pp. 43 - 54.
29. Larkin E.V., Ivutin A.N., Kotov V.V., Privalov A.N., 2016, Simulation of Relay-races In:
30. Bulletin of the South Ural State University. Mathematical Modelling, Programming & Computer
31. Software, vol. 9, no. 4, pp. 117 - 128.
32. Larkin E., Bogomolov A., Privalov A., 2019, Discrete model of mobile robot assemble faulttolerance
33. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial
34. Intelligence and Lecture Notes in Bioinformatics), vol. 11659 LNAI, pp. 204-215.
35. Akimenko, T.A., Larkin, E.V., 2019, The temporal characteristics of a wandering along
36. parallel semi-Markov chains In: Communications in Computer and Information Science. 4th
37. International Conference on Data Mining and Big Data, Chiang Mai; Thailand, vol. 1071, pp.
38. -89.
39. Bielecki T.R., Jakubowski J., Niewe˛g lowski M., 2017, Conditional Markov chains: Properties,
40. construction and structured dependence In: Stochastic Processes and their Applications, vol.
41. , no 4, pp. 1125–1170.
42. Deo N., 2016, Graph theory with applications to Engineering and computer science. N.Y.: Dover
43. Publications, 496 p.
44. Oltean M., 2006, A light-based device for solving the Hamiltonian path problem In: Unconventional
45. Computing. Lecture Notes in Computer Science. Unconventional Computing, vol.
46. Springer LNCS, pp. 217–227.
47. Bj¨orklund A., 2010, Determinant sums for undirected Hamiltonicity In: Proc. 51-st IEEE
48. Symposium on Foundations of Computer Science (FOCS ’10), pp. 173–182.
49. Kobayashi H., Marl B.L., Turin W., 2012, Probability, Random Processes and Statistical
50. Analysis, Cambridge University Press, 812 p.
51. Grimmett G.R., Stirzaker D.R., 2001, Probability and Random Processes, Oxford: Clarendon
52. Press, 608 p.
53. Larkin E.V., Ivutin A.N., Troshina A., 2017, Model of interruptions in Swarm unit In: Advances
54. in swarm intelligence. Proceedings of 8-th International conference ICSI 2017, Fukuoka, Japan.
55. part 1, pp. 50 - 59.
Review
For citations:
Larkin E.V., Privalov A.N., Bogatyreva Yu.I. Paired discrete competition with a free route choice. Chebyshevskii Sbornik. 2021;22(2):145-159. (In Russ.) https://doi.org/10.22405/2226-8383-2021-22-2-145-159
Views:
341
Email this article 