Algorithms of constructing resource work schedules in project planning

Abstract

The paper considers the problem of constructing work schedules for the resources involved in a project execution. The solution of this task is necessary to organize a workflow at the level of specific performers. The proposed approach uses existing general project schedule and is based on minimizing individual risks determined by the characteristics of the distribution of work. At the same time, the approach tries to avoid the need for additional estimates beyond those that are traditionally obtained at earlier stages of planning. This makes it easy to implement in practice. The paper considers two possible formulations of the problem: with homogeneous completely interchangeable resources and with fuzzy estimates of the complexity of the jobs performed. An approach is proposed for representing constraints on intersecting jobs in the form of a graph to reformulate the original problem. This allows one to get all possible options for work schedules as independent sets of vertices in the constraint graph. An algorithm based on the branch and bound method is proposed as a solution method. Its main components are described, including lower bound estimation, constraint checking, and some tricks to improve efficiency. Finally, the application of the proposed methods and algorithms to specific input data is demonstrated.