Genetic Algorithms versus Critical Path Method

Dr. George Gafencu, DBA, PMP, DTM

A comparison between the critical path implemented via Genetic Algorithms versus Critical Path Method is the topic of the current posting. The conditions of the experiment is a relatively small schedule (17 tasks) developed rigorously based on the Project Management Institute’s guidelines [1]. All tasks have a predecessor and a successor, except for the first and the last task. The network graph used appeared published in a recent article [2], but I introduced the data in Microsoft Project to generate a classic project view of a node network. I developed a proprietary tool to export the data from Microsoft Project in a format usable in Python 3.8.4. Figure 1 shows the schedule used by both methods in a canonic network graph form. Node 1 is the starting task of the MP schedule and 17 is the last task.

Figure 1. The schedule used for testing, as an output of Python 3.8.4

Genetic Algorithms Run

I designed and optimized a genetic algorithm to calculate the critical path of the model schedule, with the end goal of maximizing the start to end path. Figure 2 and Figure 3 show the evolution of fitness over the run, and Figure 3 shows the two critical paths determined by the genetic algorithms used.

Figure 2. Maximum and average fitness over genetic algorithms generations.

Genetic Algorithms versus Critical Path Method

Figure 3. The Python output screen, showing the two critical paths determined.

The data collected showed that the genetic algorithm needed less than ten generations to find the two critical paths associated (length 51), with no task dependency violation involved.

Classical CPM Method

For comparison, in Python, using the same data entry as for the genetic algorithm, I developed code determining all the paths leading from task 1 to task 17 and calculated their durations, using the classic CPM method. The Python output appears in Figure 4.

Genetic Algorithms versus Critical Path Method

Figure 4. The classical CPM method.

Findings

The genetic algorithm determined the right two critical paths for the project analyzed. The algorithm did not need many generations to locate the solutions (less than ten generations), but required 0.5s to run the algorithm (acceptable). The algorithm started with heavy penalties on random population found initially (containing tasks not in succession), but learned quickly and determined in a reasonable amount of time. On the downside, the genetic algorithm identified the optimal solutions but did not retain any of the secondary critical paths in its list. The classical critical path method needed only 2.992 ms to run, using the same system as the genetic algorithm. The software was able to locate fast all the principal and secondary critical paths with all their durations.

The conclusion is that, in similar circumstances (small networks), the genetic algorithms cannot compete with the classical methods of critical path calculation. However, they are an excellent alternative and have an acceptable execution speed for determining critical paths of a small project. Genetic algorithms may prove a better choice for larger projects, and fuzzier critical paths, coming next under my research analysis. My practitioner experience shows that, for medium and large programs, the classic critical path method calculation could take a significant amount of time and produces calculation errors or even halts in case the schedule has structural issues.

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

#projectmanagement #ai #geneticalgorithms #criticalpath #projectschedule #machinelearning

References for Genetic Algorithms versus Critical Path Method

[1]       Project Management Institute, A guide to the project management body of knowledge (sixth edition). Newton Square, PA: Project Management Institute, 2017, retrieved from https://www.pmi.org.

[2]       M. H. Calp and M. A. Akcayol, “Optimization of project scheduling activities in dynamic CPM and PERT networks using genetic algorithms,” arXiv preprint arXiv:1902.00659, 2019.

 

2 thoughts on “Genetic Algorithms versus Critical Path Method

Leave a Reply

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