• P. Kravets Lviv Polytechnic National University, Lviv, Ukraine, Ukraine
  • V. Lytvyn Lviv Polytechnic National University, Lviv, Ukraine, Ukraine
  • V. Vysotska Lviv Polytechnic National University, Lviv, Ukraine, Ukraine



project, agent, ontology, staff assigning, coloring of random graph, stochastic game, Markovian recursive method, adaptation, self-learning


Context. This article describes how to solve the game problem of assigning staff to work on projects based on an ontological approach. The essence of the problem is this. There is a need to create teams to carry out several projects. Each project is defined by a set of necessary ontological knowledge. To implement projects, managers invite qualified specialists (agents), whose abilities are also defined by sets of ontologies. The composition of the teams should be such that the combined ontologies of their agents cover the set of ontologies of the respective projects. Each agent with a certain probability can take part in the implementation of several projects. Simultaneous work of the agent on different projects is not allowed. It is necessary to determine the order of project implementation and the corresponding order of personnel appointment.

Objective of the study is to develop a mathematical model of stochastic game, recurrent Markov methods for its solution, algorithmic and software, computer experiment, analysis of results and development of recommendations for their practical application.

Method. A stochastic game algorithm for coloring an undirected random graph was used to plan project execution. To do this, the number of vertices of the graph is taken equal to the number of projects. The edges of the project graph for which the same agent is invited are connected by edges. Due to the recovery failures of agents, the connections between the vertices of the graph change dynamically. It is necessary to achieve the correct coloring of the random graph. Then projects with the same colored vertices of the graph can be executed in parallel, and projects with different colors of vertices – in series.

Results. The article builds a mathematical model of a stochastic game and a self-learning Markov method for its solution. Each vertex of the graph is controlled by the player. The player’s pure strategies are the elements of the color palette. After selecting the color of their own top, each player calculates the current loss as a relative number of identical colors in the local set of neighboring players. The goal of the players is to minimize the functions of average losses. The Markov recurrent method provides an adaptive choice of colors for the vertices of a random graph based on dynamic vectors of mixed strategies, the values of which depend on the current losses of players. The result of a stochastic game is an asymptotically correctly colored random graph, when each edge of the initial deterministic graph will correspond on average to different colors of vertices.

Conclusions. A computer experiment was performed, which confirmed the convergence of the stochastic game for the problem of coloring a random graph. This made it possible to determine the procedure for appointing staff to implement projects.

Author Biographies

P. Kravets, Lviv Polytechnic National University, Lviv, Ukraine

PhD, Associate Professor of Information Systems and Networks Department

V. Lytvyn, Lviv Polytechnic National University, Lviv, Ukraine

Dr. Sc., Professor, Head of Information Systems and Networks Department

V. Vysotska, Lviv Polytechnic National University, Lviv, Ukraine

PhD, Associate Professor of Information Systems and Networks Department


Virtual Communities: Concepts, Methodologies, Tools and Applications, Information Resources Management Association (USA), Vol. 1–4. Hershey, IGI Global, 2011, 2930 p. DOI: 10.4018/978-1-60960-100-3.

Heagney J. Fundamentals of Project Management. HarperCollins Focus, 2018, 240 p.

Asdre K., Ioannidou K., Nikolopoulos S. D. The harmonius coloring problem is NP-complete for interval and permutation graphs, Discret Applied Mathematics, 2007, Vol. 155, pp. 2377–2382.

Li Z., Zhu E., Shao Z., Xu J. NP-completeness of local colorings of graphs, Information Processing Letters, 2018, Vol. 130, pp. 25–29.

Keet C. M. An Introduction to Ontology Engineeing, v.1.5. University of Cape Town, South Africa, 2020, 306 p. Access mode:

Kravets P., Lytvyn V., Vysotska V. Game model of ontological project support (in ukrainian), Radio Electronics, Computer Science, Control, 2021, Vol. 1, No. 1, pp. 172–183. DOI: 10.15588/1607-3274-2021-1-17.

Chen B.-S. Stochastic Game Strategies and their Applications. CRC Press, 2019, 610 p.

Panik M. J. Linear Programming and Resource Allocation Modeling. Wiley, 2018, 448 p.

Markis S. Allocation of Manufacturing Tasks to Humans and Robots, Cooperating Robots for Flexible Manufacturing. Springer, 2021, pp. 373–380.

Wang Z., Man Y. Machine learning-based intermittent equipment sheduling model for flexible production process, Application of Artificial Intelligence in Process Systems Enineering, 2021, pp. 473–495.

Yang G., Chen S. Resource allocation algorithm and job sheduling of virtual manufacturing workshop, Academic Journal of Manufacturing Engineering, 2020, Vol. 18, No. 2, pp. 155–161.

Yeganeh F. T., Zegordi S. H. A multi-objective optimazation approach to project sheduling with resiliency criteria under uncertain activity duration, Annals of Operations Research, 2020, Vol. 285, No. 1, pp. 161–196.

Liu W. Production sheduling and equipment matching of flexible workshops based on multi-objective and multi-process hybrid optimization algorithm, Academic Journal of Manufacturing Engineering, 2020, Vol. 18, No. 4, pp. 158-163.

Katrenko A.V. Operations research. Manual (in ukrainian). Lviv, Magnolia Plus, 2006, 549 p.

Wang Z., Li S., Wang Y., Li S. The Reseach of Task Assignment Based on Ant Colony Algorithm, International Conference on Mechatronics and Automation, IEEE Publisher, 2009, pp. 2334–2339. DOI: 10.1109/ICMA.2009.5246570.

Sahu A., Tapadar R. Solving the Assignment Problem using Genetic Algorithm and Simulated Annealing, IAENG International Journal of Applied Mathematics, IJAM_36_1_7, 2007, Vol. 36:1, pp. 1–4.

Zais M., Laguna M. A graph coloring approach to the deployment shedaling and unit assignment problem, Journal of Sheduling, 2016, Vol. 19, pp. 73–90.

Zhu A., Yang S. X. A neural network approach to dynamic task assignment of multirobots, IEEE transactions on neural networks, 2006, Vol. 17, No. 5, pp. 1278–1287.

Wu S. S., Sweeting D. Heuristic algorithm for task assignment and sheduling in a processor network, Parallel Computting, 1994, Vol. 20, Issue 1, pp. 1–14.

Chartrand G., Zhang P. Chromatic Graph Theory. Chapman and Hall/CRC, 2019, 525 p.

Saoub K. R. Graph Theory. An Introduction to Proofs, Algorithms, and Applications. Chapman and Hall/CRC, 2021, 437 p.

Monasson R. On the Analysis of Backtrack Procedures for the Colouring of Random Graphs, Lect. Notes Phys, 2004, Vol. 650, pp. 235–254.

Christofides N. Graph theory: an algorithmic approach / N. Christofides. New York, Academic Press, 1975, 400 p.

Bincy A. K., Presitha B. J. Graph Coloring and its Real Time Applications an Overview, International Journal of Mathematics And its Applications, 2017, Vol. 5, Issue 4-F, pp. 845–849.

Denysenko O. Overview of graph coloring methods and algorithms, International Multidisciplinary Science Journal « ' Λ ΟΓΟΣ. The art of scientific thought», 2019, No. 7, pp. 27–32.

Lima A. M., Carmo R. Exact Algorithms for the Graph Coloring Problem, Revista de Informatica Teórica e Aplicada, RITA, 2018, Vol. 25, No. 04, pp. 57–73.

Gupta S., Singh D. P. Greedy Graph Coloring Algorithm Based on Depth First Search, International Journal on Emerging Technologies, 2020, Vol. 11, No. 2, pp. 854–862.

Dey A., Agarwal A., Dixit P., Long H. V., Werner F., Pal T., Son L. H. A genetic algorithm for total graph coloring, Journal of Intelligent & Fuzzy Systems, 2019, Vol. 37, No. 6, pp. 7831– 7838.

Philipsen W. J. M., Stok L. Graph coloring using neural networks, IEEE International Symposium on Circuits and Systems, 1991, pp. 1597–1600.

Meraihi Y., Ramdane-Cherif A., Mahseur M., Achelia D. A chaotic binary salp swarm algorithm for solving the graph coloring problem, International Symposium on Modelling and Implementation of Complex Systems, 2018, pp. 106–118.

Dowsland K. A., Thompson J. M. An improved ant colony optimization heuristic for graph colouring, Discrete Applied Mathematics, 2008, Vol. 156, No. 3, pp. 313–324.

Blum A., Rosenschein J. S. Multiagent Graph Coloring: Pareto Efficiency, Fairness and Individual Rationality, Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, 2008, pp. 24–29.

Panagopoulou P. N., Spirakis P. G. A Game Theoretic Approach for Efficient Graph Coloring, In: Hong S.H., Nagamochi H., Fukunada T. (eds). Algorithm and Computation. ISAAC 2008. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, 2008, Vol. 5369, DOI: 10.1007/978-3-54092182-0_19.

Kravets P. O. Game model of chromatic coloring of graphs (in ukrainian), Computer Design Systems. Theory and Practice: Bulletin of the National University of Lviv Polytechnic, 2008, No. 626, pp. 63–74.

Raigorodskii A. M. Models of random graphs (in russian). Moscow, Moscow Center for Continuous Mathematical Education (MCCME), 2011, 136 p.

Frieze A., Karoński M. Introduction to random graphs. Cambridge University Press, 2016, 478 p.

Ungureanu V. Pareto-Nash-Stackelberg Game and Control Theory: Intelligent Paradigms and Applications. Springer, 2018, 343 p.

Nazin A. V., Poznyak A. S. Adaptive Choice of Variants: Recurrence Algorithms (in russian). Moscow, Science, 1986, 288 p.

Kushner H., Yin G. G. Stochastic Approximation and Recursive Algorithms and Applications. Springer Science & Business Media, 2013, 417 p.

Benveniste A., Metivier M., Priouret P. Adaptive Algorithms and Stochastic Approximations. Springer Science & Business Media, 2012, 365 p.

Neogy S. K., Bapat R. B., Dubey D. Mathematical Programming and Game Theory. Springer, 2018, 226 p.

Kravets P. A. Game self-organization of agents system with individual estimation of strategies (in ukrainian), Computer systems and networks: Bulletin of the National University of Lviv Polytechnic, 2005, No. 546, pp. 75–85.

Bilova T. G., Pobezhenko I. A. Method of estimation the degree of structural proximity of bound non-oriented graphs (in ukrainian), Processing of information in complex technical systems, 2017, Issue 1, No. 47, pp. 9–12. DOI: 10.30748/soi.2017.147.02.



How to Cite

Kravets, P., Lytvyn, V., & Vysotska, V. (2022). MODELLING GAME TASK OF ASSIGNING STAFF TO PERFORM IT-PROJECTS BASED ON ONTOLOG IES . Radio Electronics, Computer Science, Control, (1), 130.



Progressive information technologies