View source for Project management and scheduling, mathematical theory of

The mathematical description and methods for solving a special class of [[Mathematical programming|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p0751201.png" /> be a given set of events of the project, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p0751202.png" /> the (unknown) time at which the event <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p0751203.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p0751204.png" />, occurs. The NOT BEFORE relations denote that a certain operation can be started (and/or can be finished) not before than in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p0751205.png" />, the given amount of time units, after some other operation has started (and/or finished): <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p0751206.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p0751207.png" />.

The NOT LATER relations denote that some operation is to be started (or, equally possible, to be finished) not later than the given time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p0751208.png" /> before some other operation will start (finish): <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p0751209.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512010.png" />.

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|Network model]]). The graph contains, also, additional arcs in order to properly represent the precedence relations between operations.

The resulting graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512011.png" /> having node set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512012.png" /> and arc set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512013.png" /> is called a PERT (for Project Evaluation and Review Technique), or CPM (Critical Path Method) network [[#References|[a1]]], [[#References|[a2]]].

==Problem statement.==
The mathematical theory of project management and scheduling seems to have begun with the solution of the following problem [[#References|[a2]]].

===Problem 1===
(the critical path problem in acyclic networks). Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512014.png" /> be a PERT network, with node set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512015.png" /> and arc set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512016.png" />, representing a project. For some arcs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512017.png" />, let there be given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512018.png" />, their non-negative lengths, corresponding to the directions of project operations. Given two fixed nodes, the start <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512019.png" /> and the finish <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512020.png" />, the problem is to find the longest directed path from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512021.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512022.png" /> (called the  "critical path" ). The critical path determines the shortest possible time in which the entire project portrayed by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512023.png" /> can be completed.

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

===Problem 2===
(PERT-TIME problem in general networks).

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512024.png" /> be a project with event set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512025.png" /> and operation set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512026.png" />; precedence relations of two types, NOT BEFORE and NOT LATER, are imposed on the operations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512027.png" />:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512028.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>

The PERT network <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512029.png" />, corresponding to the project <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512030.png" />, is constructed as follows: its node set is identified with the event set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512031.png" />; its arc set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512032.png" /> is defined as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512033.png" />, where

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512034.png" /></td> </tr></table>

with the arc lengths <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512035.png" /> being defined as follows:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512036.png" /></td> </tr></table>

Given two fixed nodes, the start <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512037.png" /> and the finish <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512038.png" />, the problem is to find the shortest possible time in which the project <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512039.png" /> can be completed (the latter being equal to the length of the longest path from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512040.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512041.png" />). More sophisticated formulations of project management and scheduling problems take into consideration costs of operations [[#References|[a5]]], [[#References|[a6]]].

===Problem 3===
(PERT-COST problem in acyclic networks).

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512042.png" /> be a project with event set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512043.png" /> and operation set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512044.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512045.png" /> are its  "normal"  completion time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512046.png" />, its  "crash"  completion time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512047.png" /> and the cost <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512048.png" /> of shortening the operation by one time unit. Denoting by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512049.png" /> the actual (unknown) duration of the operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512050.png" />, the latter quantity is to be between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512051.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512052.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512053.png" />, and the cost of the operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512054.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512055.png" />. The problem is to find the minimal cost of shortening the project to a given duration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512056.png" />.

===Problem 4===
(parametric PERT-COST) [[#References|[a5]]], [[#References|[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) [[#References|[a7]]]. This is an extension of Problem 3. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512057.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512058.png" /> be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512059.png" />. Assume the problem's objective <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512060.png" /> to be the sum of piecewise-linear convex non-monotone functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512061.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512062.png" />, of time shifts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512063.png" />, representing penalties incurred for the project operations being started/finished too early as well as too late.

The problem is to minimize <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512064.png" /> 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., [[#References|[a1]]]–[[#References|[a10]]]), many other project management and scheduling problems have been proved to belong to the notorious class of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512065.png" />-hard problems, which are most difficult among all the combinatorial optimization problems [[#References|[a11]]]. Consider two typical project management and scheduling problems of the latter class.

===Problem 6===
(resource-constrained PERT-TIME) [[#References|[a9]]]. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512066.png" /> be a PERT project as considered in Problems 1, 3. Suppose <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512067.png" /> 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) [[#References|[a12]]]. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512068.png" /> be a PERT project as described in Problems 2, 5. Suppose <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512069.png" /> types of resources are required to perform operations and, for each operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512070.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512071.png" />. Two operations demanding the same type of resources are not permitted to occur simultaneously.

For each operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512072.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512073.png" /> 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|dynamic programming]]. When its modification, the Bellman–Ford method of successive approximations [[#References|[a10]]], is applied to project management and scheduling, Problem 1 is solved in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512074.png" /> time, and Problem 2 in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512075.png" /> time, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512076.png" /> being the number of nodes and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512077.png" /> 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 [[#References|[a5]]] and J.E. Kelley [[#References|[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 [[#References|[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 [[#References|[a7]]].

As for the numerical solution of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512078.png" />-hard project management and scheduling problems (like Problems 6, 7), they have defied solution in polynomial time. Numerous computational methods suggested for solving <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512079.png" />-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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512080.png" />-hard project management and scheduling problems is in  "imbedding"  sophisticated optimization procedures into the shell of a decision support system or expert system [[#References|[a12]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J.E. Kelley, jr.,   M.R. Walker,   "Critical path planning and scheduling" , ''Proc. Eastern Joint Computer Conference, Boston, 1959''</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  B. Roy,   "Cheminement et connexité dans les graphes. Application aux problèmes d'ordonnancement" , Dunod  (1962)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  D.R. Fulkerson,   "A network flow computation for project cost curves"  ''Manag. Sci.'' , '''7'''  (1961)  pp. 161–178</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  J.E. Kelley Jr.,   "Critical path planning and scheduling. Mathematical basis"  ''Operations Research'' , '''9'''  (1961)  pp. 296–320</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  E.V. Levner,   A.S. Nemirovsky,   "A network flow algorithm for just-in-time project scheduling" , ''Proc. Sem. Project Management and Scheduling'' , Compiegne  (1990)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  L.R. Ford jr.,   "Flows in networks" , Princeton Univ. Press  (1962)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  J.J. Moder,   C.R. Phillips,   "Project management with CPM and PERT" , v. Nostrand-Reinhold  (1970)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  E.L. Lawler,   "Combinatorial optimization: networks and matroids" , Holt, Rinehart &amp; Winston  (1976)</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  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)</TD></TR></table>