Dijkstra’s Method and CPM Evaluation

Dr. George Gafencu, DBA, PMP, DTM

Dijkstra’s method and the Critical Path Method (CPM) evaluation is the topic of the current posting. The condition of the experiment is a relatively small schedule (17 tasks) developed rigorously based on the Project Management Institute’s guidelines [1]. Meanwhile, Strategy & Innovation, LLC needed a safe and fast method of calculating a critical path to use in other project management tools in design. I implemented in Python and optimized two classical methods of path calculation, CPM and modified Dijskra [2, 3], albeit the modified Dijkstra method of the critical path is newer and not widely researched or used. Here are the findings after implementing these methods:

  1. Both ways need three passes to determine a critical path (forward calculation, backward calculation, and slack calculation), taking a relatively long time to execute.
  2. Both methods return only one critical path (or multiple critical paths, if all have the same duration), and both would need additional modifications to return secondary critical paths, making the algorithms long to execute.
  3. While the Dijkstra algorithm is insensitive to linear schedule programming (the nodes by number are generally successors to nodes having a lower number, the CPM method is not. Practical scheduling implementation shows, for example, a set of activities leading to a node with a higher number, which in turn precedes a node with a lower number. This situation required special handling, and I did not find a solution for it so far in any material I read. The issue can disappear by implementing a recursive CPM algorithm, not found in the literature.

During implementation and optimization, I realized that none of these methods are native to newer technologies or programming languages, leaving room for faster and better critical path algorithms to implement. Strategy & Innovation developed in Python a proprietary critical path algorithm and will present the evaluation against classical CPM and modified Dijkstra methods implemented in Python too. The project used is the project utilized in my previous posting. Figure 1 shows the graph used for simulation, and the graph is not linear, in the sense that node 7 precedes node 6, unlike the examples presented in [2, 3], which are linear graphs.

Equivalent Network Graph of the Real Project Schedule Used
Figure 1. The schedule used for testing, as an output of Python 3.8.4

Dijkstra, CPM, and Newer Critical Path Algorithms Evaluation

The results of running the schedule network with the Python implementations of the three methods appear in Figure 2. While the modified Dijkstra algorithm is sensibly faster than the CPM method (needing 1.995 ms to find the two critical paths against 2.992 ms used to run the CPM method), the proprietary algorithm required only 0.995 ms to run. The memory and CPU usage were similar between the three methods. The current research includes the conclusion that newer technologies are vital to finding faster and better algorithms for critical path calculation than CPM and modified Dijkstra. Strategy & Innovation, LLC retains the proprietary critical path calculation for future applications.

The execution times for a proprietary critical path calculation method, CPM, and modified Dijkstra algorithm.
Figure 2. Comparison of execution times for critical path calculations using a proprietary algorithm, CPM, and modified Dijkstra method.

 

Do you have any engineering or business data you cannot understand? Strategy and Innovation, LLC can help with your data needs!

#projectmanagement #criticalpath #projectschedule #cpm #dijkstra

References

[1]       Project Management Institute, A guide to the project management body of knowledge (sixth edition). Newton Square, PA: Project Management Institute, 2017.

 

[2]       S. Kadry, A. Abdallah, and C. Joumaa, “On the optimization of Dijkstra’s algorithm,” in Informatics in control, Automation and Robotics: Springer, 2011, 393-397.

 

[3]       R. S. Nowpada and V. S. Veeramachaneni, “Using modified Dijkstra’s algorithm for Critical Path Method in a project network,” International Journal of Computational and Applied Mathematics, 2011, vol. 5. 217–225 https://www.researchgate.net/publication/268011501_Using_Modified_Dijkstra’s_Algorithm_for_Critical_Path_Method_in_a_Project_Network.

Leave a Reply

Your email address will not be published. Required fields are marked *