The origins of PERT and CPM – What came before the computers!

The development of PERT and CPM as Mainframe software systems starting in 1957 is well documented with contemporary accounts from the key people involved readily available.  What is less clear is how two systems developed contemporaneously, but in isolation, as well as a number of less well documented similar systems developed in the same timeframe in the UK and Europe came to have so many similar features.  These early tools used the ‘activity-on-arrow’ (AoA or ADM) notation which is a far from obvious model.  Later iterations of the concept of CPM used the ‘precedence’ notation which evolved from the way flow-charts were and are drawn.

stockpile

One obvious connection between the early developments was the community of interest around Operation (or Operational) Research (OR) a concept developed by the British at the beginning of WW2.  OR had developed to include the concept of linear programming by the mid-1950s which is the mathematical underpinning of CPM, but while this link explains some of the cross pollination of ideas and the mathematics it does not explain terms such as ‘float’ and the AoA notation (for more on the development of CPM as a computer based tool see http://www.mosaicprojects.com.au/PDF_Papers/P042_History%20of%20Scheduing.pdf).

A recent email from Chris Fostel, an Engineering Planning Analyst with Northrop Grumman Corporation (CFostel@rcn.com) appears to offer a rational explanation.  I’ve reproduced Chris’ email pretty much verbatim below – the challenge posed to you is to see if the oral history laid out below can be corroborated or validated.  I look forward to the responses.

Chris’ Oral History

quartermaster_corpsI was told this story in 1978 by a retired quartermaster who founded his own company after the War to utilize his global contacts and planning skills.  Unfortunately the individual who told me this story passed away quite a few years ago and I’m not sure any of his compatriots are still alive either.  Regardless, I thought I should pass this along before I join them in the next life.  I do not wish to minimize the work of Kelly and Walker. They introduced critical path scheduling to the world and formalized the algorithms.  They did not develop or invent the technique.

The origin of critical path scheduling was the planning of the US Pacific Island hopping campaign during World War II.  The Quartermaster Corps coordinated orders to dozens if not hundreds of warships, troop ships and supply ships for each assault on a new island.  If any ships arrived early it would alert the Japanese of an imminent attack.  Surprise was critical to the success of the island hopping campaign.  The US did not have enough warships to fight off the much larger Japanese fleet until late in the war. Alerting the Japanese high command would allow the Japanese fleet to intercept and destroy the slow moving US troop ships before they had a chance to launch an attack. 

Initially the quartermasters drew up their plans on maps of the pacific islands, including current location and travel times of each ship involved.  The travel times were drawn as arrows on the map.  Significant events, personnel or supplies that traveled by air were shown as dashed lines hopping over the ship’s arrows.  The quartermasters would then calculate shortest and longest travel times to the destination for all ships involved in the assault. The plans became very complicated.  Many ships made intermediate stops at various islands to refuel or transfer cargo and personnel.  The goal was to have all ships arrive at the same time.  It didn’t take the quartermasters long to realize that a photograph of the planning maps would be a devastating intelligence lapse.  They started drawing the islands as identical bubbles with identification codes and no particular geographical order on the bubble and arrow charts. These were the first activity on arrow critical path charts; circa 1942. 

The only validation I can offer you is that by now you should realize that activity on arrow diagrams were intuitive as was the term ‘float.’  Float was the amount of time a particular ship could float at anchor before getting underway for the rendezvous.  Later when the US quartermasters introduced the technique to the British for planning the D-Day invasion the British changed float to “Slack”, to broaden the term to include air force and army units which did not float, but could ‘slack off’ for the designated period of time. 

You will not find a written, dated, account of this story by a quartermaster corps veteran.  Critical path scheduling was a military secret until declassification in 1956.  In typical fashion, the veterans of WWII did not write about their experiences during the War.  No one broke the military secrecy.  After 1956 they were free to pass the method on to corporate planners such as Kelly and Walker.  A living WWII Quartermaster veteran, should be able to provide more than my intuitive confirmation.

This narrative makes sense to me from a historical perspective (military planning has involved drawing arrows on maps for at least 200 years) and a timing perspective.  Can we find any additional evidence to back this up??  Over to you!

Advertisements

9 responses to “The origins of PERT and CPM – What came before the computers!

  1. WOW Pat this is pretty awesome stuff and as a fellow historian buff, I appreciate you sharing it as this knowledge is fast dying out. The only part I can contribute that MIGHT help to corroborate this story is the work of John Fondahl https://babel.hathitrust.org/cgi/pt?id=mdp.39015000453970;view=1up;seq=18 who explained that the reason the early dates (subtrahend) are put on top of the PDM boxes and the late dates (minuend) are put on the bottom of the PDM boxes, which contravenes standard mathematical practices, is because that is how the US Navy did it in the pacific.

    Other than that, anyone who actually did or used this process must be well into their 90’s now.

    Keep up the good work and I will spread the word of your research efforts thoughout my network. Also when we update the Guild’s CAR, I hope you will allow us to include this as well?

    Merry Christmas, Happy Hanukkah, Happy Holidays, Joyous Kwanza….

    Dr. PDG, Jakarta, Indonesia

  2. I would not be surprised if CPM has roots in Dynamic Programming (Bellman’s Principle of Optimality). For example, Dijkstra developed an algorithm in 1956 for finding the shortest path in a directed network using Dynamic Programming. The same algorithm can be used with a minor change for finding the longest path in a network.

    • Dynamc programming, Linear programming and OR in more general terms definately underpin the development of CPM as a Mainframe applicaton (as noted in the referenced ‘history paper’) – what we are looking for in answer to this question relates to the 1940s.

  3. This narrative makes sense to me from a historical perspective and a timing perspective. Can we find any additional evidence to back this up?? Over to you!

    I don’t know how the coordination of movement of several ships from different locations for simultaneous arrival at a specific location is equivalent to critical path scheduling in project management. I would not however convey that such coordination is simple and easy.

    I don’t know how the determination of floats / slacks for ships at the initial and intermediate ports for the purpose of simultaneous arrival of ships is equivalent to project scheduling by CPM.

  4. Rather then opinion what we are looking for is the origins of the AoA notation for drwing ADM disgams and scheduling resources to accomplish tasks. The principles described in the article are precisely the same as the rules used in calculating an ADM schedule (PDM calculations are quite different)…

  5. Working as Project consultant, many times i felt the same. These PERT and CPM helps the planners to schedule the projects before these modern computer era. I done scheduling using CPM many times. Thanks for the nice article.
    Karthik

  6. Following my participation in this thread about 3 months ago, I wrote a LinkedIn blog, “Some Similarity between Critical Path Method and Dynamic Programming” at https://www.linkedin.com/pulse/some-similarity-between-critical-path-method-dynamic-prasad-velaga

    As I argued in the blog, It is highly likely that the concept of CPM came from Dynamic Programming which precedes CPM. I view CPM as a nice and simple application of Dynamic Programming.

    • I agree Prasad, the linked post is consistent with my research that suggests the root of much of the mathematics used in CPM is to be found in operations research (and Kelley was a mathematician working in OR before getting involved in CPM development). The similarities in computation between CPM, PERT, and MPM in Europe suggests a common root. Thank you for the input to the discussion!!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s