Tag Archives: Critical Path

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

What is the critical path?

One of the most common misconceptions in planning and scheduling is that float somehow determines the ‘critical path’. For the PMI-SP exam and any serious consideration of the definition of the ‘critical path’, float is not the right answer.

Associating zero float with the critical path is correct if, and only if, there are no constraints placed on the schedule.  As soon as you introduce a contract completion date the critical path may finish before the contract requirement and have positive float or after the contracted completion date and have negative float (and knowing by how much is important to managing both the schedule and the work).

Then add in the common contractual issues of delayed access to areas of work (available on or after a specified date), and mandated interim handovers of part of the deliverables and float goes all over the place. These issues were considered at length when we were writing of the Guide to Good Practice in the Management of Time in Complex Projects.

The description of the critical path developed for The Guide is:

Critical Path = the longest sequence of activities from commencement to completion of a key date, section, or completion of the works as a whole. In relation to each, it is that sequence of activities, which will take the longest to complete or, put another way, the sequence of activities, which will determine the earliest possible finish date. Hence, it is timely commencement and completion of those activities on that path, which will secure completion of the key date, section, or the works as a whole on time.

This description was condensed to a definition in ISO 21500 Guide to Project Management (2012), as:

Critical Path: sequence of activities that determine the earliest possible completion date for the project or phase.

This ‘Standard Definition’ does not preclude the possibility of several ‘completions’ within the one project to account for interim handovers required under a contract. It allows for the possibility of the critical path starting at the beginning of the schedule or at some interim point where an external dependency allows the ‘critical’ work to start. Additionally, the sequence of activities may be determined logically (through links or dependencies) or through the sequential movement of resources. The definition is both concise and unambiguous. For more see: http://www.mosaicprojects.com.au/WhitePapers/WP1043_Critical_Path.pdf

You need to get with the game – people who want to ignore the current international standard definition will become increasingly marginalised as the various national standards move into alignment with ISO.

Schedule Compression

Mosaic’s White Paper WP1059 takes a simple look at the integrated nature of schedule compression linking What-If, Fast Tracking and Crashing into a single process. To download the white Paper see: www.mosaicprojects.com.au/WhitePapers/WP1059_Schedule_Compression.pdf

Time Analysis Schedule Calculations

There are a range of options for the calculation of dates and float in a CPM network.

I’ve just finished a White Paper focusing on the basic calculations and would appreciate comments on the correctness of the calculations and the methodology adopted.  The aim is to produce a definitive document that is generally agreed. 

You can download the paper from http://www.mosaicprojects.com.au/PDF/Schedule_Calculations.pdf   All comments gratefully appreciated.

Cause of Delay

Late last year the British High Court delivered a very interesting judgement on the assessment of delay, disruption and prolongation claims.

A delay to an activity may disrupt the work and it may delay the completion of the project. The two factors are independent (this is the fundamental principle in the UK Delay and Disruption Protocol).

In Costain Ltd v Charles Haswell & Partners Ltd [2009] EWHC B25 (TCC) (24 September 2009), the High Court has determined that for prolongation to occur, the actual delay has to flow through to a delay in the completion of the works. The mere fact the delayed activity was on the then critical path when it occurred is not of itself evidence the delay flowed through to the completion of the works. At paragraph 200(ii) the Justice Richard Fernyhough QC stated I find that it has not been shown by Costain that the critical delay caused to the project by the late provision of piled foundations to the RGF and IW buildings necessarily pushed out the contract completion date by that period or at all.

The fundamental issues relate to the definition of the critical path were canvassed inin my 2006  paper ‘Float is it real’.

At page 7 I argued:

Despite the CPM requirement for a single duration estimate, durations are variable; changing the estimate of a planned (future) duration or differences between the actual duration and planned duration on completed activities may change the critical path.

In the example above, at the ‘Initial Claim’ the critical path was running through the top chain of activities and ‘delay x’ was encountered. As no one can predict the future, at the time of the dealay it would be reasonable for everyone involved in the project to assume this is a critical delay and administer the contract accordingly.

Later, changes in the duration of the activities cause the critical path to move (either reduction in the time needed to complete some activities in the top chain or increases in duration in the lower chain, or both). When ‘delay y’ occurs as a ‘Later Claim’, this is also a critical delay based on the schedule at the time of the delay.

However, given the definition of the ‘Critical Path’ is: Generally, it is the longest path through the project. …that determines the duration of the project. The difficult question to answer is what happens to ‘delay x’, it appeared to be critical based on the best information available at the time the delay occurred. But changes over time (and after the time of the initial delay) have shown ‘delay x’ to actually be non-critical.

Certainly based on the Constain’s case, scheduling experts will need to define far more than simply a delay to an activity on the current critical path. As a minimum it will be necessary to show the delay impacted the overall completion and the extent of the impact. It will also be necessary to show the delay caused a general increase in costs for a prolongation claim to be sustained.