Difference between revisions of "Project management and scheduling, mathematical theory of"
Ulf Rehmann (talk | contribs) m (tex encoded by computer) |
Ulf Rehmann (talk | contribs) m (Undo revision 48310 by Ulf Rehmann (talk)) Tag: Undo |
||
Line 1: | Line 1: | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
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. | 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. | ||
Line 16: | Line 4: | ||
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. | 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 | + | 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" />. |
− | be a given set of events of the project, and | ||
− | the (unknown) time at which the event | ||
− | |||
− | occurs. The NOT BEFORE relations denote that a certain operation can be started (and/or can be finished) not before than in | ||
− | the given amount of time units, after some other operation has started (and/or finished): | ||
− | |||
− | The NOT LATER relations denote that some operation is to be started (or, equally possible, to be finished) not later than the given time | + | 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" />. |
− | before some other operation will start (finish): | ||
− | |||
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. | 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 | + | 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]]]. |
− | having node set | ||
− | and arc set | ||
− | is called a PERT (for Project Evaluation and Review Technique), or CPM (Critical Path Method) network [[#References|[a1]]], [[#References|[a2]]]. | ||
==Problem statement.== | ==Problem statement.== | ||
Line 39: | Line 16: | ||
===Problem 1=== | ===Problem 1=== | ||
− | (the critical path problem in acyclic networks). Let | + | (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. |
− | be a PERT network, with node set | ||
− | and arc set | ||
− | representing a project. For some arcs | ||
− | let there be given | ||
− | their non-negative lengths, corresponding to the directions of project operations. Given two fixed nodes, the start | ||
− | and the finish | ||
− | the problem is to find the longest directed path from | ||
− | to | ||
− | called the "critical path" ). The critical path determines the shortest possible time in which the entire project portrayed by | ||
− | 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]]]. | 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]]]. | ||
Line 56: | Line 23: | ||
(PERT-TIME problem in general networks). | (PERT-TIME problem in general networks). | ||
− | Let | + | 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" />: |
− | be a project with event set | ||
− | and operation set | ||
− | precedence relations of two types, NOT BEFORE and NOT LATER, are imposed on the operations of | ||
− | + | <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 | + | 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 |
− | corresponding to the project | ||
− | is constructed as follows: its node set is identified with the event set of | ||
− | its arc set | ||
− | is defined as | ||
− | 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 | + | with the arc lengths <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075120/p07512035.png" /> being defined as follows: |
− | 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 | + | 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]]]. |
− | and the finish | ||
− | the problem is to find the shortest possible time in which the project | ||
− | can be completed (the latter being equal to the length of the longest path from | ||
− | to | ||
− | More sophisticated formulations of project management and scheduling problems take into consideration costs of operations [[#References|[a5]]], [[#References|[a6]]]. | ||
===Problem 3=== | ===Problem 3=== | ||
(PERT-COST problem in acyclic networks). | (PERT-COST problem in acyclic networks). | ||
− | Let | + | 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. |
− | be a project with event set | ||
− | and operation set | ||
− | 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 | + | 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" />. |
− | are its "normal" completion time | ||
− | its "crash" completion time | ||
− | and the cost | ||
− | of shortening the operation by one time unit. Denoting by | ||
− | the actual (unknown) duration of the operation | ||
− | the latter quantity is to be between | ||
− | and | ||
− | |||
− | and the cost of the operation | ||
− | is | ||
− | The problem is to find the minimal cost of shortening the project to a given duration | ||
===Problem 4=== | ===Problem 4=== | ||
Line 116: | Line 48: | ||
===Problem 5=== | ===Problem 5=== | ||
− | (just-in-time PERT-COST in general networks) [[#References|[a7]]]. This is an extension of Problem 3. Let | + | (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. |
− | 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). | 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 | + | 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. |
− | be | ||
− | Assume the problem's objective | ||
− | to be the sum of piecewise-linear convex non-monotone functions | ||
− | |||
− | of time shifts | ||
− | representing penalties incurred for the project operations being started/finished too early as well as too late. | ||
− | The problem is to minimize | + | 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). |
− | 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 | + | 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. |
− | 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=== | ===Problem 6=== | ||
− | (resource-constrained PERT-TIME) [[#References|[a9]]]. Let | + | (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)? |
− | be a PERT project as considered in Problems 1, 3. Suppose | ||
− | 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=== | ===Problem 7=== | ||
− | (resource-constrained PERT-COST) [[#References|[a12]]]. Let | + | (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. |
− | be a PERT project as described in Problems 2, 5. Suppose | ||
− | types of resources are required to perform operations and, for each operation | ||
− | 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 | ||
− | Two operations demanding the same type of resources are not permitted to occur simultaneously. | ||
− | For each operation | + | 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. |
− | 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 | + | 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? |
− | 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.== | ==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 | + | 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]]]. |
− | time, and Problem 2 in | ||
− | time, | ||
− | being the number of nodes and | ||
− | 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 | + | 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. |
− | hard project management and scheduling problems (like Problems 6, 7), they have defied solution in polynomial time. Numerous computational methods suggested for solving | ||
− | 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 | + | 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]]]. |
− | 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==== | ====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 & 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> | <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 & 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> |
Revision as of 14:52, 7 June 2020
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 be a given set of events of the project, and
the (unknown) time at which the event
,
, occurs. The NOT BEFORE relations denote that a certain operation can be started (and/or can be finished) not before than in
, the given amount of time units, after some other operation has started (and/or finished):
,
.
The NOT LATER relations denote that some operation is to be started (or, equally possible, to be finished) not later than the given time before some other operation will start (finish):
,
.
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 having node set
and arc set
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 be a PERT network, with node set
and arc set
, representing a project. For some arcs
, let there be given
, their non-negative lengths, corresponding to the directions of project operations. Given two fixed nodes, the start
and the finish
, the problem is to find the longest directed path from
to
(called the "critical path" ). The critical path determines the shortest possible time in which the entire project portrayed by
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 be a project with event set
and operation set
; precedence relations of two types, NOT BEFORE and NOT LATER, are imposed on the operations of
:
![]() | (a1) |
The PERT network , corresponding to the project
, is constructed as follows: its node set is identified with the event set of
; its arc set
is defined as
, where
![]() |
with the arc lengths being defined as follows:
![]() |
Given two fixed nodes, the start and the finish
, the problem is to find the shortest possible time in which the project
can be completed (the latter being equal to the length of the longest path from
to
). 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 be a project with event set
and operation set
. 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 are its "normal" completion time
, its "crash" completion time
and the cost
of shortening the operation by one time unit. Denoting by
the actual (unknown) duration of the operation
, the latter quantity is to be between
and
,
, and the cost of the operation
is
. The problem is to find the minimal cost of shortening the project to a given duration
.
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 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 be
. Assume the problem's objective
to be the sum of piecewise-linear convex non-monotone functions
,
, of time shifts
, representing penalties incurred for the project operations being started/finished too early as well as too late.
The problem is to minimize 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 -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 be a PERT project as considered in Problems 1, 3. Suppose
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 be a PERT project as described in Problems 2, 5. Suppose
types of resources are required to perform operations and, for each operation
, 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
. Two operations demanding the same type of resources are not permitted to occur simultaneously.
For each operation 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 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 time, and Problem 2 in
time,
being the number of nodes and
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 -hard project management and scheduling problems (like Problems 6, 7), they have defied solution in polynomial time. Numerous computational methods suggested for solving
-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 -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) |
Project management and scheduling, mathematical theory of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Project_management_and_scheduling,_mathematical_theory_of&oldid=49378