An Algebraic Approach to Scheduling Problems in Project Management

The problem of scheduling a large-scale set of activities presents a key issue in project management. At present there are a variety of project-scheduling techniques developed to deal with different aspects of the problem, including the Critical Path Method and the Program Evaluation and Review Technique marked the beginning of the active research in the area in 1950s.

We propose a new approach to schedule development based on implementation of models and methods of idempotent algebra. The approach allows one to represent different types of precedence relationships among activities as linear vector equations written in terms of an idempotent semiring with maximization and addition as its two scalar operations. Many issues in schedule development can then be reduced to solving problems in the idempotent algebra settings, including linear equations and the eigenvalue-eigenvector problem.

Two types of the precedence constraints that are normally referred to as Start-to-Start and Start-to-Finish are examined, and their related linear equations with respect to the unknown vector of initiation time of the activities are derived. The general solutions to the equations and to the eigenvalue-eigenvector problem are given in a compact closed form. It is shown how to interpret the solutions of the algebraic problems in a project management sense. As an illustration, examples of scheduling problems and their solutions are discussed.