Ambivalence in the Assignment of Project Executors

Abstract

This paper considers the assignment of project executors to a set of interdependent tasks. The relationships between these tasks are described using weighted directed graphs without loops and contours, the elements of which correspond to certain project characteristics. At the same time, events (the completion or commencement of work) are represented by the vertices of the graph, while tasks are represented by arcs, with their orientation corresponding to the technology of this process. Project management aims to optimally distribute project executors according to project assignments, with the efficiency criterion of minimizing the time required for project completion. Literature review has shown that this task is an essential component of most complex project management models. The authors proposed a method for solving this problem using the duality apparatus. It is shown that the classical assignment problem should be solved at each step to calculate the corresponding dual function. The price matrix of this problem is determined by multiplying the elements of the price matrix of the original problem by the corresponding Lagrange multipliers. When solving the test problems, it was found that H. Uzawa’s classical non-smooth optimization algorithm generates a zigzag search trajectory, similar to the optimization trajectory of “ravine” functions. It was proposed to use the approach developed by V.F. Demyanov and V.L. Malozemov to solve nonlinear minimax problems. The paper provides a detailed example of using the proposed algorithm. Test calculations have confirmed the effectiveness of this method for moderate-dimensional problems. It has been shown that, in general, there is a duality gap for this problem, but an acceptable approximate solution can still be found.