Парное дискретное соревнование со свободным выбором маршрута
https://doi.org/10.22405/2226-8383-2021-22-2-145-159
Аннотация
В работе рассмотрена проблема оптимизации расписания функционирования многопроцессорных систем. Решение данной проблемы предполагает формирование жесткого
графика работы, который определяет ритм процессов, но на практике на функционирование систем оказывает влияние множество побочных факторов, которые делают интервалы
времени выполнения работ случайными. В работе построена полумарковская модель формирования стохастического расписания в условиях парного соревнования. Показано, что
если при функционировании системы возможно исполнение пунктов расписания в произвольном порядке, то эволюция полумарковского процесса проходит по гамильтонову пути.
Доказано, что все возможные реализации гамильтоновых путей образуют полную группу несовместных событий. Отмечается, что вследствие наложения ограничений по характеру эволюции, процесс эволюции не является строго полумарковским, и поэтому предложен метод формирования из первичной модели, строго полумарковского процесса с древовидной структурой. Получены зависимости для расчета плотностей распределения и вероятностей переключения из состояний полумарковского процесса в сопряженные состояния, а также времени блуждания от стартового до поглощающих состояний. С использованием
понятия парного дискретного соревнования и распределенного штрафа оценивается эффективность выбора гамильтонова пути одним из субъектов с учетом того, что алгоритм поведения его оппонента известен с точностью до построения полумарковской модели.
Об авторах
Евгений Васильевич Ларкин
Тульский государственный университет
Россия
Россия
доктор технических наук
Александр Николаевич Привалов
Тульский государственный педагогический университет им. Л. Н. Толстого
Россия
Россия
доктор технических наук, профессор
Юлия Игоревна Богатырева
Тульский государственный педагогический университет им. Л. Н. Толстого
Россия
Россия
доктор педагогических наук
Список литературы
1. Haefner J. W. Parallel computers and individual-based models: an overview // Individual-based models and approaches in ecology, Chapman and Hall/CRC, 2018, pp. 126 - 164.
2. Gupta C.B., Optimization techniques in operation research, 2-nd Kindle edition. U.K. International Publishing House, 2012, 386 p.
3. Wooldridge M., An Introduction to Multi-Agent Systems. 2nd Edition. Chichester, U.K: John Wiley & Sons, 2009, 484 p.
4. Deng C. et all., An effective grid-based and density-based spatial clustering algorithm to support parallel computing // Pattern Recognition Letters, 2018, vol. 109. pp.. 81 - 88.
5. Pinedo M.L., Scheduling. Theory: Algorithms and systems // Springer. Science+Business media, 2016, 670 p.
6. Khodr Y.M., Scheduling Problems and Solutions (Computer Science, Technology and Application) // Nova Science Pub Inc., 2012, 330 p.
7. Drozdowski M., Scheduling for Parallel Processing (Computer Communications and Networks) // Springer, 2009, 386 p.
8. Gawiejnowicz S., Time-Dependent Scheduling (Monographs in Theoretical Computer Science. An EATCS Series). Springer, 2008, 380 p.
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, 2013, vol. 189, Springer Science + Business Media NY, 241 p.
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, 2016, vol. 10. Iss. 11, pp. 1215 – 1223.
11. Jiang Q., Xi H.-S., Yin B.-Q., Event-driven semi-Markov switching state-space control processes // IET Control Theory & Applications vol. 6, Iss. 12, 2012, pp. 1861 – 1869.
12. Janssen J., Manca R., Applied Semi-Markov processes // Springer US, 2005, 310 p.
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, 2015, vol. 8. no. 2, pp. 43 - 54.
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, 2016, vol. 9, no. 4, pp. 117 - 128.
15. Larkin E., Bogomolov A., Privalov A., Discrete model of mobile robot assemble faulttolerance // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2019, vol. 11659 LNAI, pp. 204-215.
16. Akimenko, T.A., Larkin, E.V., The temporal characteristics of a wandering along parallel semi- Markov chains // Communications in Computer and Information Science. 4th International Conference on Data Mining and Big Data, Chiang Mai; Thailand, 2019, vol. 1071, pp. 80-89.
17. Bielecki T.R., Jakubowski J., Niewe˛g lowski M., Conditional Markov chains: Properties, construction and structured dependence // Stochastic Processes and their Applications, 2017, vol. 127, no 4, pp. 1125–1170.
18. Deo N., Graph theory with applications to Engineering and computer science // N.Y.: Dover Publications, 2016, 496 p.
19. Oltean M., A light-based device for solving the Hamiltonian path problem // Unconventional Computing. Lecture Notes in Computer Science. Unconventional Computing, 2006, vol. 4135 Springer LNCS, pp. 217–227.
20. Bj¨orklund A., Determinant sums for undirected Hamiltonicity // Proc. 51-st IEEE Symposium on Foundations of Computer Science (FOCS ’10), 2010, pp. 173–182.
21. Kobayashi H., Marl B.L., Turin W., Probability, Random Processes and Statistical Analysis // Cambridge University Press, 2012, 812 p.
22. Grimmett G.R., Stirzaker D.R., Probability and Random Processes // Oxford: Clarendon Press, 2001, 608 p.
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, part 1, pp. 50 - 59.
Рецензия
Для цитирования:
Ларкин Е.В., Привалов А.Н., Богатырева Ю.И. Парное дискретное соревнование со свободным выбором маршрута. Чебышевский сборник. 2021;22(2):145-159. https://doi.org/10.22405/2226-8383-2021-22-2-145-159
For citation:
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
Просмотров:
330
Послать статью по эл. почте 