Моделювання Ігрової задачі призначення персоналу для виконання ІТ-проектів на основі онтологій

Abstract

UK: Актуальність. У цій статті описано розв’язування ігрової задачі призначення персоналу для роботи над проектами на основі онтологічного підходу. Суть задачі полягає у такому. Існує потреба у створенні команд для виконання декількох проектів. Кожен проект задається набором необхідних онтологічних знань. Для виконання проектів менеджери залучають кваліфікованих спеціалістів (агентів), здібності яких також задаються наборами онтологій. Склад команд повинен бути таким, щоб об’єднані онтології їх агентів покривали множини онтологій відповідних проектів. Кожен агент з певними імовірностями може прийняти послідовну участь у виконанні декількох проектів. Одночасна робота агента над різними проектами не допускається. Необхідно визначити порядок виконання проектів і відповідний йому порядок призначення персоналу. Метою дослідження є розроблення математичної моделі стохастичної гри, рекурентних марковських методів для її розв’язування, алгоритмічного та програмного забезпечення, проведення комп’ютерного експерименту, аналіз результатів та виробленням рекомендацій щодо їх практичного застосування. Метод. Для планування виконання проектів використано стохастичний ігровий алгоритм розфарбовування неорієнтованого випадкового графа. Для цього кількість вершин графа прийнята рівною кількості проектів. Ребрами з’єднано ті вершини графа проектів, для виконання яких залучено одного і того ж агента. З урахуванням відновлювальних відмов агентів зв’язки між вершинами графа динамічно змінюються. Необхідно досягнути правильного розфарбування випадкового графа. Тоді проекти з однаково зафарбованими вершинами графа можуть бути виконані паралельно, а проекти з різними кольорами вершин – послідовно. Результати. У статті побудовано математичну модель стохастичної гри та самонавчальний марковський метод для її розв’язування. Кожна вершина графа контролюється гравцем. Чистими стратегіями гравця є елементи палітри кольорів. Після вибору кольору власної вершини кожен гравець обчислює поточний програш як відносну кількість однакових кольорів у локальній множині сусідніх гравців. Мета гравців полягає у мінімізації функцій середніх програшів. Марковський рекурентний метод забезпечує адаптивний вибір кольорів вершин випадкового графа на основі динамічних векторів змішаних стратегій, значення яких залежать від поточних програшів гравців. Результатом стохастичної гри є асимптотично правильно розфарбований випадковий граф, коли кожному ребру початкового детермінованого графа будуть відповідати у середньому різні кольори вершин. Висновки. Проведено комп’ютерний експеримент, який підтвердив збіжність стохастичної гри для задачі розфарбовування випадкового графа. Це дало можливість визначити порядок призначення персоналу для виконання проектів. EN: 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.