MODELLING GAME TASK OF ASSIGNING STAFF TO PERFORM IT-PROJECTS BASED ON ONTOLOG IES
DOI:
https://doi.org/10.15588/1607-3274-2022-1-14Keywords:
project, agent, ontology, staff assigning, coloring of random graph, stochastic game, Markovian recursive method, adaptation, self-learningAbstract
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.
References
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: https://people.cs.uct.ac.za/~mkeet/0Ebook/.
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.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 П. О. Кравець, В. В. Литвин, В. А. Висоцька
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
