Mathematical formalization of project scheduling problems

Abstract

Theory of scheduling and project planning is widely applied in diverse scientific and industrial areas. To effectively solve application-specific problems it is necessary to take into account a lot of factors such as task execution models, precedence relationship between tasks, resource limitations, directive deadlines, working calendars, conditions for financial and logistics support of project tasks, specific spatio-temporal requirements et al. Therefore, in practice there is a need to generalize the project scheduling problems and to consider their extended formulations. The paper provides a classical mathematical statement of RCPSP problems (Resource-Constrained Project Scheduling Problem) and a short description of the serial dispatching algorithm for their approximate solution. Shortcomings and limitations of the RCPSP statement are discussed and systemized in more details. The paper presents a mathematical formalization of project scheduling problems in extended definitioins taking into account numerous features of practical problems. The proposed statement of GCPSP problems (Generally Constrained Project Scheduling Problem) can be considered as an evolution of RCPSP problems. This statement implies a mathematically neutral specification of the optimization problem under algebraic constraints of the predefined sorts and priorities. Essentially, that the constraints are interpreted in terms of the local consistency that allows some violations in the case of overloaded algebraic systems. An effective algorithm for the approximate solution of GCPSP problems is also presented and explained by following to the classical serial algorithm. Moreover, the equivalence of the algorithms is proved for the cases when a solved GCPSP problem is reduced to the RCPSP. It is expected that the obtained results will allow developing a general-purpose software library for solving of diverse project scheduling problems.