The Optimization Mechanisms Based on a Three- Dimensional Assignment Problem in IT Projects

Abstract

The article is concerned with optimization mechanisms based on a three-dimensional assignment problem in the context of IT projects management. A mathematic model is proposed for enabling efficient allocation of resources, tasks and time intervals with account taken of restrictions and optimality criteria. The researchers have analyzed existing approaches to solution of the problem and substantiated their selection of optimization methods. The obtained results show the possibilities of improving the IT projects planning, minimizing the cost and increasing the team efficiency. The authors have arrived at the conclusion about practical implementation of the proposed mechanisms in real conditions of projects IT management.

Keywords

• optimization
• three-dimensional assignment problem
• project management
• IT project
• resources allocation
• mathematic modeling
• heuristic algorithms

1. Introduction

increasing the teamwork efficiency, and ensuring the flexibility of management solutions in IT projects

2. Problem statement

The known formalized approach to solving this optimization problem assumes that each executor can only be involved at one project stage and the number of executors is equal to the number of project stages –

= . Should the i th executor be assigned for implementation of the j th stage of the project, the variable takes on value = 1, and vice versa, = 0. In this case, the optimization problem on allocation of participants by the general project stages or the assignment problem, when m = n , shall look like: ( 1 ) = 0 ∨ 1,

X =  21 where - the number of the general project stages, - the number of executors ( = ), - the costs on assignment of the th executor for execution of the th stage of the project.

The matrix of feasible plans for this optimization problem shall look like and include one unit in each row and in each column. The analysis of this approach to assignment of executors for project implementation shows that the optimum result essentially depends on the number of project stages vs the

3. The problem research status

Optimization problems in IT projects management are actively researched in various areas of science including discrete mathematics, operation analysis and intellectual management systems. One of important approaches to solving the problem of efficient allocation of resources consists in using the assignment problem, particularly its three-dimensional generalization. The classic assignment problem was proposed by Kohn [1,2] and is solved by the Hungarian algorithm method. Further researches [3,4] were concerned with its generalized variants including multidimensional models. A 3D assignment problem is NP-hard and requires using special methods for its solution. The scientific literature provides a wide range of methods for solving a 3D assignment problem. The papers of Gavish & Graves [5] proposed combinatory approaches, whereas the contemporary works [6,7] are concerned with utilization of linear ( 3 ) programming and such metaheuristic algorithms as genetic algorithms and particle swarm algorithms. The project management provides for effective allocation of resources, which is studied in the papers of Shen & Wang [8] presenting adaptive models based on the mathematic programming. Other works [9] analyze distribution of tasks under real conditions with dynamic restrictions.

The contemporary researches [10] are indicative of the possibility of using the machine learning and deep neural networks for improving the results of optimization in complicated projects. The integration of a 3D assignment problem and digital project management platforms provide and advanced area of development. The real life is associated with problems where it is required to depart from the prerequisites of a classic assignment problem – one executor per one project stage and vice versa. Such a problem is given by the known combinatory problem on a system of different representatives [11]. In this type of problems, several executors have already to be assigned to one vacant position. A set of problems on assignment of executors with additional requirement or property (sex, age, experience, etc.) is of the same extent of importance. In addition to the conventional two properties (i,j), the candidate possesses a third one –(k). The assignment matrix = ‖ ‖n× × already becomes three-dimensional.

The analysis of scientific publications shows a big attention that is paid to the problem of optimum allocation of resources in the project management. The 3D assignment problem is an important tool in solving such problems and its improvement is possible due to a combination of mathematic and intellectual methods. In view of this, it is reasonable to develop a model of a 3D classic and generalized assignment problem and to provide their solution algorithms. Utilization of this model in the project management will facilitate the formation of the optimum network diagram and distribution of functions in the project team. Similar project management problems are considered in articles [12-14].

4. The research objective and tasks

The objective of the paper consists in development and substantiation of optimization mechanisms based on a 3D assignment problem and improvement of the IT project resources management efficiency. The research provides for analysis of the existing approaches to solving an assignment problem, construction of a mathematic model for the optimum allocation of resources, tasks and time intervals, as well as development of algorithmic solutions with use of linear programming methods and heuristic algorithms. The expected result is given by improvement of the project teams efficiency and minimization of costs by means of implementing the proposed mechanisms in the projects planning and management process.

For achieving the specified objective, the following tasks are to be realized: • Develop a mathematic model of a 3D problem on assignment of an IT project executors with account taken of restrictions attributable to the project management. • Propose optimization mechanisms for efficient allocation of resources, tasks and time intervals within the project processes. • Develop and test an algorithmic solution based on the proposed model for evaluation of its efficiency in real scenarios of IT projects management. 4. A 3D classic and generalized assignment problem and its solution algorithm It is known that a two-index or a classic two-dimensional assignment problem is provided by a problem looking as follows:

‖ × × - a matrix of assignment efficiency values, = ‖ ‖ × × The following problem can be called a classic 3D assignment problem:

=1 =1 =1

, ∑ = 1, = 1, … , , = 1, … , , ∑ = 1, = 1, … , , = 1, … , , ∑ = 1, = 1, … , , = 1, … , , ∑ = 1, = 1, … , , = 1, … , , ∑ = 1, = 1, … , , = 1, … , , ∑ = 1, = 1, … , , = 1, … , , = 0 ∨ 1, , , = 1, … , , ( 6 ) ( 7 ) where – ( − the assignment plan.

Let us theoretically substantiate the solution of a 3D assignment problem ( 3 ) from the planar decomposition point of view. This means that a 3D matrix ( − ) = ‖ ‖ × × is to be decompose into a set of 2D problems. Each simplified 2D problem is a result of planar section of a 3D matrix by rows and columns. The number of such sets depends on n and is equal to 3n of decomposed problems. Each such problem can already be solved by the Hungarian ) = ‖ ‖ × × . the matrix of assignment values, = ‖ ‖ × × method. The analysis of the pooled solutions obtained enables receiving a solution of the 3D assignment problem in general.

Theoretic substantiation to the solution of a generalized assignment problem can be interpreted from the dynamic optimization problem point of view. As per the dynamic optimization concept, the whole problem solution chain can be divided into separate elementary stages. A simplified problem of the same type is solved at each of these stages. At the same time, this algorithm is constructed subject to the known R. Bellman principle. The R. Bellman principle is based on the statement that whatever the initial status of the system at an arbitrary current optimization stage, the next stage is chosen from the optimality condition relative to the previous status. This approach provides in solution chains not a locally optimal but the globally optimal solution for the process in general.

The following problem can be called a 3D generalized (to depth h) assignment problem ( 4 ). In our case, the solution of a generalized assignment problem provides for fixing the previous optimal status by substitution of limiting values (big or small ones) depending on the problem meaning into the matrix C(k-const)=||cijk||n⨯ n⨯n. The next problem is solved by the canonic (Hungarian) method. Then the optimal positions of the already changed matrix C(k-const)=||cijk||n⨯ n⨯n are substituted again by limiting values and the problem is so solved. The number of iterations is equal to the maximum depth of the assignment problem generalization. Finally, the optimum plan is to be chosen. We proceed to apply the proposed approach to solving model problems. 5. The algorithmic solution testing based on the proposed model 5.1. Let us consider finding the optimum representation among three sets M (Managers / Directors), T (Tasks / Projects), W (Executors / Resources) with using a classic 3D assignment problem. The task consists in matching the couples (M, T, W) so that a certain target criterion (expenses, efficiency, execution time, etc.) is minimized or maximized ( 5 ).

= ∑3=1 ∑3=1 ∑3=1 → , ( 8 ) At an IT company implementing several projects at the same time, and it is required to assign managers (M) to projects, teams of executors - to projects (T), executors (W) – to particular tasks within these projects. Solution of this problem enables the optimum allocation of responsibility and resources with account taken of the competences, work load, deadlines and other constraints.

The company shall distribute IT projects among managers and executors. At the same time, the managers have a different level of experience and competence, the projects have a different level of complexity and budget, the executors have different skills and efficiency. The optimum assignment (M, T, W) is to be found so that the managers supervise respective projects, the executors receive tasks in accordance with their competences, and the expenses and projects implementation time are to be minimized. = 0 ∨ 1, , , = 1, … ,3, :Application of a 3D assignment problem enables development of a compliance matrix among the managers, projects and executors where each combination has its value or efficiency. After solving, we obtain the optimum set of assignments.

According to the formula ( 5 ) where C = cijk 333

7 4 1 2 = C(k =1)  C(k =2)  C (k =3) = 6 6 8  2 2 5 5 4 8 2 1 3 8  6 9 9 7 7 5 3 3 .( 10 ) 3 8 The chains for all modifications as per the procedure proposed are given below: 7 4 1 6 6 6 8 ⎯c⎯iji−−mc⎯oinn(sct⎯ij)→ 0 2 5 5 0 3 0 6 3 0 2 → 0 0 3 3 3 0 0 1 2 , 6 3 7 7 5 0 6 3 3 ⎯c⎯iji−−mc⎯oinn(sct⎯ij)→ 3 0 3 8 4 0 5 0 ,( 11 ) 5 2 8 2   2 3 8 4 9 9

0 6 0 ⎯c⎯iji−−mc⎯oinn(sct⎯ij)→ 0 1 6 0 5 5

0 5 0 ⎯c⎯ijj−−m⎯cionn(sc⎯tij)→ 0 0 6 .( 12 ) 0 4 5

Red zeros indicate positions of the optimum solutions. The last conversion chains provide us with the optimum solutions by respective planar sections ( =1), ( =2), ( =3) 6 C(k =1) : 0  0 3 0 0 0 2 → X o(pkt=1) = 0 3 3 1 1 0 5 0 0 0 1 0 , C(k =2) : 0 0 6 → X o(pkt=2) = 0 1 0 ,( 13 ) 0 0 4 5 1 0 0

A classic 3D assignment problem is a powerful tool for resources allocation in the project management. Its solution enables the optimum assignment of managers, projects and executors with account taken of constraints and business metrics to improve the project management efficiency.

5.2. With application of a 3D generalized assignment problem, we model a situation when it is required to provide the optimum allocation of three types of resources among each other. For depth h = 2, we can consider the assignment in the form of interrelated levels: - Level 1 (Managers → Tasks): each manager is assigned a certain set of tasks. - Level 2 (Tasks → Executors): each task is allocated among the executors as per their competences.

Therefore, the recourses allocation process has a two-level structure as it is necessary to assign managers for certain groups of tasks, as well as to assign separate executors for certain tasks within these groups. Solution of the problem facilitates the optimum allocation of resources in IT projects with minimization of expenses or time of execution.

To a company supervising several simultaneous IT projects, each manager (M) can manage a restricted quantity, each project has a set of tasks (T) to be fulfilled, for each task, there are available executors (W) having different level of qualification and efficiency. It is required to find such an allocation (M → T → W) where the general expenses (time, budget) are minimized or the project team efficiency is maximized.

Let us find a solution to a generalized 3D assignment problem (of depth h=2) ( 6 ) 3 3 3 ( 14 ) = ∑ ∑ ∑ → =1 =1 =1 , (16) where C = c ijk 333

3 8 1 1 9 4 5 1 5 = C(k=1)  C(k=2)  C(k=3) = 9 7 5  1 9 9  5 2 8 .(17)

3 9 9 3 9 2 8 9 2

Solution: The calculation for the generalized problem shall look as follows: 5 1 5 4 0 4 1 0 4 5 2 8 ⎯c⎯iji−−mc⎯oinn(sct⎯ij)→ 3 0 6 ⎯c⎯ijj−−m⎯cionn(sc⎯tij)→ 0 0 6 8 9 2 6 7 0 3 7 0 (18)

Red zeros indicate positions of the optimum solutions by respective planar sections С( =1) , ( =2), ( =3). Another step of modification is related to the problem generalization. Each row and each column of the optimum assignment matrix require to have not just one but two units. The respective conversions are given below:

 2 4 M   0 2 M   0 2 M  C(k =1) :  4 M 0  ⎯c⎯iji−−mc⎯oinn(sct⎯ij)→  4 M 0  ⎯c⎯ijj−−m⎯cionn(sc⎯tij)→  4 M 0  , (19) 3 0 0 M 3 

M 1 9 4 0 8 3 0 1 3 1 9 9 ⎯c⎯iji−−mc⎯oinn(sct⎯ij)→ 0 8 8 ⎯c⎯ijj−−m⎯cionn(sc⎯tij)→ 0 1 8 → 3 9 2 1 7 0 1 0 0

0 1 3 0 0 2 → 0 1 8 → 0 0 7 ,

1 0 0 2 0 0 M

6   0 C(k=2) : M   2

Declaration on Generative AI

The author(s) have not employed any Generative AI tools.

References

[1] Kuhn , H. W. ( 1955 ). The Hungarian Method for the Assignment Problem . Naval Research Logistics Quarterly , 2 ( 1-2 ), 83 - 97 .

[2] Kuhn H. V. ( 1956 ) Variants of the Hungarian method for the assignment problems . Naval. Res. Logist. Quart . 253 - 258

[3] Burkard , R. E. , Dell'Amico , M. , & Martello , S. ( 2009 ). Assignment Problems . SIAM.

[4] Dell'Amico , M. , & Toth , P. ( 2017 ). Algorithms for the Generalized Assignment Problem . Mathematical Programming , 112 ( 1 ), 183 - 212 .

[5] Gavish , B. , & Graves , S. C. ( 1978 ). The Multi-Resource Multi-Task Assignment Problem . Management Science , 24 ( 7 ), 773 - 781 .

[6] Çela , E. ( 2013 ). The Quadratic Assignment Problem: Theory and Algorithms . Springer.

[7] Pentico , D. W. ( 2020 ). Assignment Problems: A Golden Anniversary Survey . European Journal of Operational Research , 176 ( 2 ), 774 - 793 .

[8] Shen , C. , & Wang , L. ( 2013 ). Adaptive Resource Allocation Models in Project Management . Journal of Project Management Science , 12 ( 3 ), 215 - 228 .

[9] Brucker , P. , Knust , S. , & Thiele , O. ( 2019 ). Scheduling and Task Allocation under Uncertainty . Computers & Operations Research , 56 , 23 - 38 .

[10] Zhang , Y. , Li , H. , & Wang , J. ( 2021 ). Machine Learning-Based Approaches for Project Optimization. Artificial Intelligence in Project Management , 5 ( 1 ), 1 - 15 .

[11] Hall , P. ( 1935 ). On Representatives of Subsets . Journal of the London Mathematical Society , 10 ( 1 ), 26 - 30 .

[12] D. Kobylkin , O. Zachko , N. Korogod , and D. Tymchenko ( 2020 ), Development of models for segregation of elements of infrastructure projects management Eastern- European Journal of Enterprise Technologies , 6 ( 3 ), ( 108 ), pp. 42 - 49 .

[13] S. Bushuyev , D. Bushuiev , V. Interaction ( 2020 ) Multilayer model of Emotional Infection with the Earn Value Method in the Project Management Process Computer Sciences and Information Technologies, 2 , pp. 146 - 150 , 9321949

[14] V. Pіterska , S. Rudenko , A. Shakhov, ( 2018 ), Development of the Method of Forming of the Architecture of the Innovation Program in the System "University-State-Business" , International Journal of Engineering & Technology (UAE) , 7 ( 4 .3), pp. 232 - 239 . DOI: https://doi.org/ 10.14419/ijet. v7i4.3.19793