Project management and scheduling, mathematical theory of

The mathematical description and methods for solving a special class of mathematical programming problems, formulated in terms of optimal resource allocation on graphs and networks.

Basic terminology.

A project is a set of interrelated tasks, or operations, that must be performed in a certain order so as to reach some goal. Events are starting and finishing points of various operations of the project.

The operations of the project are interrelated through precedence relations of two types, NOT BEFORE and NOT LATER. Let $ E = \{ 1 \dots n \} $ be a given set of events of the project, and $ t _ {i} $ the (unknown) time at which the event $ i $, $ i \in E $, occurs. The NOT BEFORE relations denote that a certain operation can be started (and/or can be finished) not before than in $ a ( i , j ) $, the given amount of time units, after some other operation has started (and/or finished): $ t _ {j} - t _ {i} \geq a( i, j) $, $ ( i, j) \in V \subset E \times E $.

The NOT LATER relations denote that some operation is to be started (or, equally possible, to be finished) not later than the given time $ b( i, j) $ before some other operation will start (finish): $ t _ {j} - t _ {i} \leq b( i , j) $, $ ( i , j) \in V \subset E \times E $.

One of the traditional graphical forms of project representation is a directed graph, or a network, in which arcs are identified with project operations and nodes with events (cf. Network model). The graph contains, also, additional arcs in order to properly represent the precedence relations between operations.

The resulting graph $ G = ( E , {\mathcal A} ) $ having node set $ E $ and arc set $ {\mathcal A} $ is called a PERT (for Project Evaluation and Review Technique), or CPM (Critical Path Method) network [a1], [a2].

Problem statement.

The mathematical theory of project management and scheduling seems to have begun with the solution of the following problem [a2].

Problem 1

(the critical path problem in acyclic networks). Let $ G = ( E, {\mathcal A} ) $ be a PERT network, with node set $ E $ and arc set $ {\mathcal A} $, representing a project. For some arcs $ ( i , j) \in {\mathcal A} $, let there be given $ d( i, j) $, their non-negative lengths, corresponding to the directions of project operations. Given two fixed nodes, the start $ s $ and the finish $ f $, the problem is to find the longest directed path from $ s $ to $ f $( called the "critical path" ). The critical path determines the shortest possible time in which the entire project portrayed by $ G $ can be completed.

It is not necessary for a PERT network to be acyclic. The dynamic programming technique that solves efficiently Problem 1, also solves successfully the following problem in networks with cycles [a3], [a4].

Problem 2

(PERT-TIME problem in general networks).

Let $ P = ( E, V) $ be a project with event set $ E $ and operation set $ V $; precedence relations of two types, NOT BEFORE and NOT LATER, are imposed on the operations of $ P $:

$$ \tag{a1 } a( i, j) \leq t _ {j} - t _ {i} \leq b( i, j) ,\ ( i, j) \in V \subset E \times E . $$

The PERT network $ G $, corresponding to the project $ P $, is constructed as follows: its node set is identified with the event set of $ P $; its arc set $ {\mathcal A} $ is defined as $ V \cup V ^ \prime $, where

$$ V ^ \prime = \{ {( j, i ) } : {( i, j ) \in V } \} , $$

with the arc lengths $ l( i , j ) $ being defined as follows:

$$ l ( i , j ) = \left \{ \begin{array}{ll} a( i, j) & \textrm{ if } ( i, j ) \in V , \\ - b( j, i) & \textrm{ if } ( i , j ) \in V ^ \prime . \\ \end{array} \right .$$

Given two fixed nodes, the start $ s $ and the finish $ f $, the problem is to find the shortest possible time in which the project $ P $ can be completed (the latter being equal to the length of the longest path from $ s $ to $ f $). More sophisticated formulations of project management and scheduling problems take into consideration costs of operations [a5], [a6].

Problem 3

(PERT-COST problem in acyclic networks).

Let $ P $ be a project with event set $ E $ and operation set $ V $. Only one type of precedence relation, NOT BEFORE, is presumed to be imposed on operations in this model. The corresponding PERT network is assumed to be acyclic.

Associated with each operation $ ( i, j) \in V $ are its "normal" completion time $ p( i, j) $, its "crash" completion time $ q( i, j) $ and the cost $ c( i, j) $ of shortening the operation by one time unit. Denoting by $ t( i, j) $ the actual (unknown) duration of the operation $ ( i, j) $, the latter quantity is to be between $ q ( i, j) $ and $ p( i, j) $, $ ( i, j ) \in V $, and the cost of the operation $ ( i, j) $ is $ c( i, j) ( p( i, j)- t ( i, j)) $. The problem is to find the minimal cost of shortening the project to a given duration $ T $.

Problem 4

(parametric PERT-COST) [a5], [a6]. This is the same as Problem 3, except that the minimal cost of the entire project is to be determined for each feasible project duration time.

Problem 5

(just-in-time PERT-COST in general networks) [a7]. This is an extension of Problem 3. Let $ P = ( E, V) $ be a project with two types of imposed precedence relations, NOT BEFORE and NOT LATER, the same as described by (a1) in Problem 2. In particular, the constraints (a1) may include the requirement that certain crucial events of the project occur just in time.

The corresponding PERT network may have arc lengths of arbitrary sign and may contain cycles (necessarily, of non-positive total length).

Let the event set $ E $ be $ \{ 1 \dots n \} $. Assume the problem's objective $ \phi ( t _ {1} \dots t _ {n} ) $ to be the sum of piecewise-linear convex non-monotone functions $ \Phi _ {ij} $, $ ( i , j ) \in V $, of time shifts $ t _ {j} - t _ {i} $, representing penalties incurred for the project operations being started/finished too early as well as too late.

The problem is to minimize $ \Phi ( t _ {1} \dots t _ {n} ) = \sum _ {( i, j) \in V } \Phi _ {ij} ( t _ {j} - t _ {i} ) $ subject to the network constraints (a1).

While Problems 1–5, like a number of other project management and scheduling problems, can be solved efficiently, in a polynomial number of computational steps (see, e.g., [a1]–[a10]), many other project management and scheduling problems have been proved to belong to the notorious class of $ {\mathcal N} {\mathcal P} $- hard problems, which are most difficult among all the combinatorial optimization problems [a11]. Consider two typical project management and scheduling problems of the latter class.

Problem 6

(resource-constrained PERT-TIME) [a9]. Let $ P = ( E, V) $ be a PERT project as considered in Problems 1, 3. Suppose $ k $ types of resources are required to perform operations, each operation requiring only one type of resources, while the intensity of its consuming, in time units, being known. The durations of the operations are also known. How should the given supply of resources be assigned to the operations so that the completion time for the entire project is minimized (with the given precedence relations being taken into account)?

Problem 7

(resource-constrained PERT-COST) [a12]. Let $ P = ( E, V) $ be a PERT project as described in Problems 2, 5. Suppose $ k $ types of resources are required to perform operations and, for each operation $ ( i, j) \in V $, one knows a finite set of "feasible variants" of its performing, each of the variants being presented by its own set of required resources and operation duration value $ d ( i, j) $. Two operations demanding the same type of resources are not permitted to occur simultaneously.

For each operation $ ( i, j) \in V $ one is given: its earliest start time, latest finish time and penalties incurred if the start (the finish) of the operation takes place too early/too late.

How should the variant of performing each of the operations $ ( i, j) \in V $ and their start/finish times be chosen so that the total cost of the project, equal to the sum of penalties incurred, is minimized?

Mathematical methods of project management and scheduling.

One of the most celebrated methods in project management and scheduling is dynamic programming. When its modification, the Bellman–Ford method of successive approximations [a10], is applied to project management and scheduling, Problem 1 is solved in $ O( n ^ {2} ) $ time, and Problem 2 in $ O( nm) $ time, $ n $ being the number of nodes and $ m $ the number of arcs of the corresponding PERT network. Another important method for solving project management and scheduling problems is the network flow method. D.R. Fulkerson [a5] and J.E. Kelley [a6] employed the linear programming structure of Problem 3 and found that Problem 3 is dual to the problem of finding the minimal cost flow in a network. It is known that the Edmonds–Karp–Dinic algorithm solves the last problem in a polynomial-bounded number of computational steps [a10]. The latter fact implies the existence of polynomial procedures for solving Problems 3 and 4. Extension of the Fulkerson–Kelley approach as applied to Problem 5 is possible, leading to its polynomial-bounded solution [a7].

As for the numerical solution of the $ {\mathcal N} {\mathcal P} $- hard project management and scheduling problems (like Problems 6, 7), they have defied solution in polynomial time. Numerous computational methods suggested for solving $ {\mathcal N} {\mathcal P} $- hard project management and scheduling problems during the last three decades (relaxation, branch-and-bound, local optimization, heuristics, etc.) at best attempted to avoid full (exponential) enumeration in practical computations, but not in the worst case. The central theoretical question here, as in integer programming in general, is whether there exist polynomial-bounded (exact) algorithms for their solution. Until now (1991) this question is still open.

The most perspective contemporary approach to practically solving $ {\mathcal N} {\mathcal P} $- hard project management and scheduling problems is in "imbedding" sophisticated optimization procedures into the shell of a decision support system or expert system [a12].

References

[a1]	D.G. Malcolm, J.H. Rosenboom, C.E. Clark, W. Fazar, "Applications of a technique for research and development program evaluation" Operations Research , 7 : 5 (1959) pp. 646–669
[a2]	J.E. Kelley, jr., M.R. Walker, "Critical path planning and scheduling" , Proc. Eastern Joint Computer Conference, Boston, 1959
[a3]	B. Roy, "Cheminement et connexité dans les graphes. Application aux problèmes d'ordonnancement" , Dunod (1962)
[a4]	G.M. Adel'son, "On some aspects of project management" A.A. Fridman (ed.) , Studies in Discrete Mathematics , Moscow (1973) pp. 105–134 (In Russian)
[a5]	D.R. Fulkerson, "A network flow computation for project cost curves" Manag. Sci. , 7 (1961) pp. 161–178
[a6]	J.E. Kelley Jr., "Critical path planning and scheduling. Mathematical basis" Operations Research , 9 (1961) pp. 296–320
[a7]	E.V. Levner, A.S. Nemirovsky, "A network flow algorithm for just-in-time project scheduling" , Proc. Sem. Project Management and Scheduling , Compiegne (1990)
[a8]	L.R. Ford jr., "Flows in networks" , Princeton Univ. Press (1962)
[a9]	J.J. Moder, C.R. Phillips, "Project management with CPM and PERT" , v. Nostrand-Reinhold (1970)
[a10]	E.L. Lawler, "Combinatorial optimization: networks and matroids" , Holt, Rinehart & Winston (1976)
[a11]	E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, "Sequencing and scheduling: algorithms and complexity" , Report BS-R8909 , CWI (1989)
[a12]	J.M. Antonisse, K.M. van Hee, J.K. Lenstra, "Exercise-constrained project scheduling: an international exercise in DSS development" A. Lewandowski (ed.) , Internat. Comparative Study in DSS , IIASA, Laxenburg (1988)