Dynamic programming is a useful mathematical technique for making a sequence of inter-related decisions. It provides a systematic procedure for determining the optimal combination of decisions, given the constraints at hand. In contrast to linear programming, there is no standard formulation for the mathematical problem. Hence each problem requires analysis and modelling for itself. A large number of algorithms are also available for this field of problems.(1)
The example above, taken from Hillier & Lieberman’s “Introduction to Operational Research”, describe the Program Evaluation and Review Technique (2) the interdependent tasks A, B, C, D, and E. Each task has an estimated time of completion -3, 4, 5, 3, and 4 respectively-. Unless process C finishes, task E cannot begin to execute.
This process is commonly used in project management scenarios, when inter-related events need to have their predecessors completed before taking up a certain task.
The purpose of this scenario is to find the expected time of completion for this project. The uncertainty comes from the fact that each of the times of completion are estimations. Therefore the scenario needs to be run multiple times and then the expected completion time to be calculated. The distribution of the completion times will be outputted as the result.
There are three milestones to this project:
- Parse an ASCII data file and construct a Graph to represent the problem.
- Find the critical path through the graph.
- Calculate the experimental distribution of the total project duration, given distributions for the completion time of each sub-task.
Read the rest of this entry »
55.958832
-3.215253
