The origins of CPM
a personal history
We are indeed fortunate to have this contribution to the literature of project management from Jim Kelley and Morgan Walker, the authors of one of the seminal articles and major techniques for project planning and scheduling. As they state in the article, they were at “the right place at the right time” but they also accomplished the objectives of their project.
They state, also, that it is necessary to understand the environment that existed at Du Pont and at Remington Rand Univac at the time of their efforts. Included in this environment were two men who played significant roles in their respective organizations, Granville Read, Chief Engineer at Du Pont and John Mauchly at Univac. To help describe this environment, we are also fortunate to have an addendum, “Du Pont Engineering Department in the 1950's: An Environment for New Ideas,” from John Sayer, Manager of the Integrated Engineering Control Group, a “think tank” group at Du Pont at that time. This was the group of which Morgan Walker was a member and which nurtured the project which led to the development of CPM.
It has been our pleasure to meet all three of these gentlemen in the past year. They have all expressed their interest in PMI in our conversations and in the profession that has grown with it.
A Personal History
By: James E. Kelley, Jr. and Morgan R. Walker
The Critical Path Method (CPM) is the real, honest-to-goodness, outgrowth of a progressive management's active search for better ways to do things.
The first part of this history covers the development period, a period of 27 months, from December 1956 through February 1959. During this time the CPM development went through the five overlapping phases, priced out in Table 1.
The second part relates the events which followed the successful development efforts and how the concepts were expanded and commercialized.
The last part is, perhaps, a postscript, sharing some feelings and reflections on the impact of the project in a variety of human endeavors.
Follow these progressive investments as the authors relive their personal experiences launching CPM, and reveal the effort it took to develop and introduce the new product.
THE DEVELOPMENT PERIOD
THE RIGHT PLACE AT THE RIGHT TIME
Morgan: It was coming on to Christmas, 1956, when I was asked to join the Engineering Department's Integrated Engineering Control Group (IEC) at E.I. duPont de Nemours, Newark, Delaware. This was really something of a plum job. “See what you can do about scheduling,” is about all John Sayer had to say to me. I must admit to being nervous about being able to do anything at all. It didn't help that several friends advised me that nothing could be done and that I had committed political suicide by accepting the assignment.
Sayer's small study group of senior engineers was the inspiration of the late Granville M. Read, then Chief Engineer and perhaps the most dynamic leader I've ever known personally. For many years Mr. Read operated a very large engineering business at Du Pont over 3,000 permanent people plus a high payroll for construction forces. Annual operating budget -- about $90 million. He was also responsible for an annual investment budget of over $500 million in Du Pont facilities, plus projects for the U.S. Government. That's a lot of money in 1956 dollars.
That fall Mr. Read set up IEC under Sayer, to report directly to him and his staff, with the very specific mission to take a fundamental look at better ways of doing the engineering business. Sayer was particularly admonished not to come up with incremental methods improvements. Since design and construction are the biggest part of Du Pont's engineering business, effort was concentrated on two basic problem areas:
- Information storage and retrieval, and
- Planning, estimating and scheduling.
The objective of the first was to stop redesigning the wheel -- to solve the engineering problem only once. Contributions by Du Pont people were perhaps as significant to this work as they were to the development of CPM . It was a technical information service, and a common language vehicle to communicate cost and technical information among projects. Many Du Pont people who were involved spun off into companies such as 3 Documentor Sciences.
However, it was the second problem that would be our major focus over the next couple of years, and change the lives of a lot of people, particularly Jim Kelley's and mine.
TABLE 1. CPM DEVELOPMENT COST ESTIMATE
|Seek Support & Develop Work Plan|
|Math Model & Algorithm||23||2,500||60||6,500|
|Develop Work Plan||12||1,300||5||600|
|Initial Test of Theory|
|Develop Project Data for Test||40||4,400||--||--|
|Develop Computer Programs||45||5,000||120||13,000|
|Test Analysis & Recommendations||15||1,700||10||1,100|
|First Live Test|
|Analyze & Network Project||280||31,000||--||--|
|Develop 1103A Program||20||1,900||50||11,600|
|Analysis & Recommendations||40||4,400||--||--|
|Additional Tests & Developments|
|Continue updating first project||60||8,600||--||3,000|
|Start two new projects||120||18,400||--||--|
|Extensions of Theory||50||5,500||50||5,400|
* Dollars reflect direct and indirect labor costs and, where relevant, costs for computer usage, all pegged to the 1956 dollar. The actual CPM development costs are not available. This reconstruction was made by re-estimating the work using the authors' records and best recollection of what happened. If anything, the estimates are probably low.
By the time I joined IEC, Philip Hayward and John A. Robinson, two mathematicians from the Engineering Services Division, had already looked at the construction scheduling problem. In their report of December 20, 1956 they proposed that the UNIVAC I computer -- we had one at Newark -- be tied into Du Pont's scheduling process for engineering and construction projects. They indicated a reasonably feasible plan to accomplish the proposal, including some mathematical tools needed. They estimated 20 man months ($40 to $50 thousand in 1956 dollars) would be needed to complete the detailed theory, develop the computer programs, and apply the method to some test projects.
It may seem puzzling that Hayward's and Robinson's work did not become the basis of the CPM development. Jim thinks they were on the right track. They certainly had the capability, and might have given the world a third model of project scheduling, different from PERT's probability model or CPM's parametric model. But their group at Du Pont was “self-supporting.” It seems silly when you think about it today, but under Engineering Department policies they would have had to find support outside the department in order to continue their development work. Hayward and Robinson may have been only one of many groups pondering the same scheduling problem. The fact that PERT was developed independently of CPM, shows not only that the time was ripe for CPM, but given the opportunity, any number of different people might have invented it.
After some consideration I concluded that, in the long run, computers were the only tools that could handle the massive amounts of design and construction planning data, and that any system concept would ultimately depend on the economics of computers. This was somewhat foreign to Engineering Department thinking in 1956. But I was one of the few in the department fortunate enough to have had direct experience not only in design and construction, but with computers too. It was a certainty that we'd have to go outside the department for ideas to make the breakthrough Mr. Read hoped for.
At that time John Mauchly had a group of clever computer applications people at Remington Rand Univac in Philadelphia (currently absorbed into Unisys through several mergers) who might have the capability of picking up where Hayward and Robinson left off. We leased one of their computers, so they were always glad to accommodate reasonable requests for help as a way of keeping competition -- spelled “IBM” -- at bay.
MODELING THE PROBLEM
Jim: You don't often get the opportunity to do significant work on an important problem. My chance came in early January, 1957, when John Mauchly called me into his office to meet Morgan. John had formed our group, the Univac Applications Research Center (UARC) a couple of years earlier. The initial thrust -- develop Generalized Programming, an assembler/compiler for the UNIVAC. Grace Hopper's group was across the hall doing similar things, but focused on business instead of scientific stuff -- her work eventually evolved into COBOL. But, with Mauchly's wider horizons we branched out into information retrieval and operations research. The latter, my bailiwick, fell heir to Morgan's inquiry.
It happened that I was to give a paper on the road-grading problem at a Case Institute operations research conference at the end of January. Road construction had been expanding rapidly since the previous June, when the first interstate highway bill was signed into law. We wanted a piece of the action. The scheduling problem would broaden our potential market for computers if we could but solve it. Morgan gave me a copy of the Hayward-Robinson memo (sans figure and technical appendix), and hinted broadly that he expected to give IBM a chance to solve the problem too.(Really, Morgan, I didn't need that kind of motivation.)
To get additional mileage from the public exposure at Case, a simple linear program formulation of the construction scheduling problem was added to the published version of the paper. This useful exercise suggested alternate ways of looking at the problem. Thanks to Morgan's prodding, my project report of March 5, 1957, could read “A model of the Du Pont construction scheduling problem has been formulated and a method of solution has been proposed. Plans are being made to jointly develop the scheduling system with Du Pont.” No commitment had been made as yet on either side. But the pressure was there to work out the details of the computer algorithm.
This mathematician was a pretty naive ivory tower type who looked at the world through linear programming -- not at all concerned with the practical aspects of construction. It was probably a good thing. Simplifying assumptions could be made without any qualms of conscience. Morgan's quick course in construction left the impression that any construction activity had an “optimal,” or “normal,” way to be performed -- a preferred method of given crew, duration, cost, etc. If one expedited the activity, the “direct” cost would increase -- at least it shouldn't decrease. Each activity was assumed to have a minimum expedited time, its “crash” duration, with a corresponding “direct” cost.
Since changes in the variable direct costs were expected to dominate the indirects, it was argued -- rightly or wrongly -- that the optimal way to do the project was to perform all the activities according to the “normal” method. With this plan there is a shortest project duration which equals the duration of the most time consuming, connected chain of activities in the network. We called this “longest time” chain the “main chain” of the network. The PERT developers gave this concept the beautiful name of “critical path.”
The problem of mathematical interest presents itself when you try to expedite that project time at minimum increase in direct cost. Begin by expediting the particular critical job that raises the project direct cost at the minimum rate. As this job's duration is shortened, other jobs become critical too, and the choices of which ones to expedite -- and by how much -- become more complex. The trick -- treat the problem as a parametric linear program -- the project duration being the parameter -- to generate a series of minimum direct cost project schedules, each with a shorter project duration than the previous one. Figure 1 shows the cost curve for a test run of the George Fisher Works, made September 25, 1957. A detailed job schedule was computed for each dot on the curve. Note how almost a month could be cut from the project at a trivial increase in direct cost over the absolute minimum cost. The small slope at the minimum turned out to be a typical characteristic of projects.
Figure 1. CONSTRUCTION SCHEDULE SUMMARY
Figure 2. THE GEORGE FISHER WORKS, the test network used for the first test of CPM.
It was totally impractical to solve the parametric model by general methods, even on the largest computers of that era. Fortunately the model has special properties, similar to those of the classical transportation problem. The latter had been worked and reworked during the mid-1950's by many people in the linear programming game. Some really neat tabular methods were devised to solve it. The hope was to find a similar method to reduce computer processing to the bare bones.
By April 25 a completed write-up of CPM was available. It provided a statement of assumptions, and a nontrivial, worked example -- but no proofs . Morgan took an earlier draft to Newark and had Curt Berry help him make a work estimate. We, too, made tentative plans to put our programmer, Papken Sassouni, and two others, Les Shaw and Sheila Quinn, from Sales Support, on the job.
…..it is necessary to take a strategic look at the entire job when planning, and to firm up this strategy, in order to establish practical work sequences. Almost everyone agreed this should be the initial planning step, but seldom was before CPM. CPM forced the issue.
The big meeting came in Newark, Delaware, on May 7. We walked out smiling, with a joint project in our hands. But everyone was pretty well pre-sold by Morgan. (Thanks again ole buddy.) RemRand programmers would code the algorithm, coordinated by Du Pont's Mai Demurjian. Du Pont's engineers would formulate a small project to use as the first test case. At the next milestone, September 1, we were to be ready to test the initial system.
THE FIRST PROJECT NETWORK
Morgan: How does one start to draw the first project network? Jim's model made us describe a project in a very precise mathematical way -- at least, with a rigor never before attempted. Initially we thought that even large projects might be described with but a few hundred activities. Contemporary bar charts seldom got much larger. So when Les Shaw told us the capacity of the UNIVAC I program would be about 200 activities we were not particularly concerned.
For a test case we selected a small mixing and packaging plant that IEC had developed the previous year. Design gave us three drawings for analysis -- a plot plan, an arrangement, and an elevation and section. One of our active construction organizations furnished a Project Analysis. We called it the Fisher Works, giving my administrative boss, George Fisher, a lit-tie playful notoriety. Jim Sage and I tackled the job of developing the units of work and their sequence.
We had two major sequence considerations. First, the general approach to the job -- should we erect the tank farm simultaneously with the building? Because the site was small and interference would be a problem if the tank farm was started at the same time, we began the building work first and delayed the tank farm until later.
In addition, the second floor reactor was larger than the second floor opening. Should we leave a construction opening in the wall, or should we drop the reactor through the roof? Design, for quite unrelated reasons, could not provide a better design for construction. We elected to put the roof on after installing the reactor so as to provide a smoother work flow.
These details are of interest because they showed us, right from the beginning, that it is necessary to take a strategic look at the entire job when planning, and to firm this strategy, in order to establish practical work sequences. Almost everyone agreed this should be the initial planning step, but it seldom was before CPM. CPM forced the issue.
Now came the details of developing two descriptions for each work unit -- the normal and crash methods -- specifying crafts, construction materials and equipment, drawings and major installed equipment, and determining delivery restraints. At this point we called on the Estimating Group to extend the costs for each work unit. These first efforts were completed July 24,1957. We had a network of 61 jobs, 8 timing restraints and 16 dummies (required for logical consistency), plus all the related data.
The programmers had made good progress, so, by the end of July, we were able to schedule the Fisher Works on a UNIVAC I -- a good month ahead of schedule. But, because of vacations and other business, we had to wait until October 26 to present the results to Mr. Read, his staff, and the Division Managers. We used the time to make a series of computer runs under various hypothetical conditions, and to fine-tune the computer programs.
It became quite clear from these early runs that the UNIVAC I did not have the speed and capacity to handle the construction scheduling problems at Du Pont. With 50 active projects, even restricting networks to 150–300 arrows, updating computation time would run to 350 hours a month. For each project this effort would involve generating and choosing from among 50 or so schedules of different cost and duration. Something had to be done about improving computational efficiency.
Univac Sales seemed willing to help us by rewriting the programs for the UNIVAC 1103A -- about 20 man months of programming work in Unicode, an assembler/compiler. With this assistance in the wings we went to our meeting with Mr. Read with an optimistic outlook and a proposal to expand the scheduling system. I well remember that session. Construction was interested in the results. Design was fearful that Construction would use CPM as a club against them. Mr. Read settled everybody's hash by authorizing the next step -- an actual project from which practical experience could be gained by involving the Design, Construction and Control divisions. To mollify Design somewhat, he restricted the test to construction activities. We committed to completing and reporting on this live test by March 15, 1958.
TYPES OF PROJECT NETWORKS
Jim: Are you puzzled about the different types of project networks? The network is possibly the most important practical concept to derive from CPM. The idea was obvious to any mathematician of the 1950's. The way project steps are sequenced is similar to graphical structures studied in courses of logic (relations), set theory (partial orderings), modern algebra (lattices), game theory (strategy trees), and, of course, graph theory itself.
However, as obvious as the project network idea might be, there is more than one way to depict one. Which way to adopt often depends on how the project data is organized for computation. Since the different methods are often misunderstood it is worth contrasting them here.
Suppose the planning focus is on the jobs of a project, viewed as essentially stand-alone work elements -- like subcontracts, related, but remote from one another. (Don't subcontractors usually view themselves as pretty independent of everyone else?) Write each job name, its estimated duration, cost, and other resource requirements, on a 3x5 card, and distribute all the cards on a table. Where the results of one subcontract are needed for another, draw an arrow between the two, the arrow pointing in the direction of time flow. The result is known as a precedence or activity-on-node project network. The cards (or boxes drawn around them) are the nodes of the network. The connecting arrows define the successor-follower relations between jobs. The arrows take no (i.e. zero) time to perform, and consume no resources.
In contrast, suppose project tasks are seen in a more integrated and mutually dependent light, less remote in their relationships, say, the way a sub-contractor might view the jobs within his own contract. Instead of using a 3x5 card, draw an arrow for each job and write its name, duration and resources on the convenient line formed by the arrow's shaft. If one job is the direct predecessor of another, connect the head of the first to the tail of the second. The end product of this process is the type of project network generated for CPM.
In the process of drawing a CPM network it is usually necessary to introduce some “dummy” arrows just to define the sequence of work properly. At first we did not recognize the need for dummies. I remember the day clearly (July 3, 1957) when Morgan unveiled the logic problems he was having with the Fisher Works. We solved them then and there at a blackboard using dummies. He wrote up the rules later on.
The CPM network -- you might call it an activity-on-branch network -- is mathematically equivalent to the activity-on-node network. To see that this is true, simply replace each job oval (box) of an activity-on-node network by an arrow, retaining the associated activity description. But erase any redundant connector arrows so that, to the extent possible, job arrows connect directly to job arrows. The connector arrows that remain are the dummies we'd have introduced to solve particular sequencing problems.
These two types of networks really did not come about as intimated. They really derive from the algebra used to define the problems, and from the algorithms used to solve them. The activity-on-node network was implied by the linear programming model in my Case Institute paper mentioned earlier. The algebra of the parametric linear program lead to the CPM-type network. There, a job was denoted by a number pair, (i,j). That is, a job arrow running from network junction numbered “i” to junction numbered “j” had a duration dij, a cost cij, and so on, as is the common subscripting used for indexing two-way tables and matrices. This notation was carried along in much of the CPM literature, and on computer printouts, long afterward, where one speaks of the activity's “I-J”. I'll go to my grave calling these index numbers “I-J's”. The terms “predecessor” or “start event” and “successor” or “finish event” are such mouthsful to say.
The activity-on-node network was proposed later on by Fondahl, Wiest and Levy, and others, as a “superior” form of project network. [Ed. Note: See Fondahl, PMJ, June 1987.] Personally, I find the clutter of connector arrows confusing in large networks of this type. In these networks direct predecessor and successor jobs tend not to be organized to be near to one another.
There's yet a third type of project network, not much in vogue in recent years. The emphasis is put on project events or milestones instead of the project activities. Start by defining certain key progress points to be used for overall management control (e.g. “design release complete,” “approved for captive test,” “arrival of test vehicle at test site”). Now write event descriptions on 3x5 cards, and distribute them on the table. Two events are connected by an arrow if the first must occur before the other. The arrow represents a whole complex of work, perhaps by several contractors, which must be done to progress from the first event to the second.
Although this type network may look like an activity-on-node network, it's really an event-on-node network, very like a CPM- type network. It grew out of the PERT development. The initial focus was on events because of the desire to report on project progress via discernible management milestones. But, just as we ran into sequencing problems and had to invent dummies, the original PERT networking method sometimes leads to ambiguities, often requiring that large scope activity complexes between two events be analyzed into smaller component activities in order to estimate durations consistently.
THE FIRST LIVE TEST
Morgan: After the October, 1957, meeting with Mr. Read, steps were taken to recruit and train six engineers from other Du Pont divisions to use CPM on an on-going project in parallel with the existing planning group. These preparations were completed by early December 1957 when the engineers arrived for an orientation course. Then the real work began.
The project selected for this test was the construction of hydrogen and anhydrous ammonia facilities at the Repauno Works in New Jersey. Ed Hyde from Construction was put in charge of the planning and scheduling effort. Mai Demurjian and I gave them a workshop course to bring them on board. Planning work began in late December, 1957. They were given the construction cost estimate and work sheets, the drawings and specs file, scopes of work and correspondence, M&E list and limiting equipment list with estimated deliveries, the design schedule, anticipated changes in design, and information on contract work involving field labor -- in short, all the available project information. The construction work was divided into activities within work area and then diagrammed in proper construction sequence.
Today it is a little difficult to appreciate the problems these men had. The effort it took to analyze the project, diagram it, and develop data seems ludicrous now. What would take a trained CPM'er two or three weeks today, took these men a good two months. But consider that these pioneers not only had their inexperience to contend with, they were not too popular going around asking so many penetrating questions about the test projects. And any question they asked in the design or construction division was an interference with regular work. In these circumstances it was bound to be slow going.
In the end, an 846 arrow network of construction activity was produced, spread out on the wall of their office. And, believe it or not, there was not a description written on any arrow. Laugh, if you will, but Jim tells me that in 1968 he consulted with Krupp on a steel plant construction project that involved a network of over 15,000 arrows, drawn in ink mind you, on a couple of hundred individual sheets, and not one arrow had a description on it. Apparently the efficacy of placing descriptions on the arrows is not so obvious as one might think, even with all the CPM literature available.
In February, 1958, Mai Demurjian took all our data tapes to Lockheed's large UNIVAC 1103A computer at Palo Alto to work out a whole range of construction schedules using the new program developed by Nathan Knoch of Univac Sales. At the time we had a co-operative venture going with Lockheed Engineering at Burbank. They were on a similar mission for their Chief Engineer. I'll never forget the debugging session.
Poor Nathan's nerves started to go from the high pressure of the situation. We even contacted RemRand's doctor to ensure it would be alright for him to continue on this effort. Dick Castanias (DP Manager at Palo Alto), Mal, Al Fera and I were in daily, multi-hour, phone contact. Mai and Dick had their hands full. Because Mai couldn't be sure just what Nathan was accomplishing, we tried debugging at the desk in Delaware on a “duplicate effort” basis. All ended well. The program worked and Nathan recovered fully.
That winter we also spent tortuous hours on 18° below nights in St. Paul, trying to run on the UNIVAC 1105. The 1103A was fine for the cost curve algorithm. But it lacked tape buffering needed for the level of input and output editing, sorting, etc. that we required. In one sense, the computation went smoothly enough -- so fast we couldn't believe it. In another sense it was a nightmare working on the Serial No. 1 machine (destined for the Census Bureau) while it was still in manufacturing. The real problem was the output from Lyle Langdon's editing routines. It was garbage. Back to the motel we went searching for errors. After a few nights of this, Univac personnel finally identified the problem. The output tape drive had the read/write heads installed backwards. After that was fixed, Lyle's program worked as planned.
Within two months we had to update the project -- this time on the Air Force's 1105 at Rome, N.Y. Enough of half-built equipment. Some 30% of the original design and equipment delivery dates had changed, and a new construction strategy was decided upon. This exercise gave a realistic idea what the maintenance of schedules would require in time, effort and dollars.
It was on this project where we first worked out the form of the output to be given to the different organizational levels concerned. The principal outputs for management were the various cost curves and analyses, in which evaluations of things like the question of “time on site” versus “unit startup to meet market demand” are treated. For supervision, we generated area schedules by pulling the appropriate event times from the printouts. And, of course, detailed job lists, sorted appropriately, were produced for field engineers and area supervisors.
We also worked out the force curves for several schedules -- manually. We could no longer ignore the manpower leveling problem.
On May 19, 1958 we had another major departmental presentation to bring Mr. Read and all the department managers up to speed with our developments and the great success we had with scheduling Repauno. The meeting resulted in authorization to:
- Complete the Repauno evaluation,
- Let the 5-man task force apply the methodology to two additional projects,
- Translate the remaining manual steps to computer,
- Continue the program to reduce computer costs (jointly with Rem-Rand), and
- Begin development of inter-project scheduling techniques using Du Pont's systems engineers and mathematicians.
THE SYNERGY OF IMAGINATIVE DOINGS
Jim: The project network captured the imagination of everyone who saw it, and lots of private experiments were done by many engineers to adapt the networking idea to other applications. Du Pont's Maintenance Engineering had one particularly successful application the winter of 1957–58 in determining the over-all process system reliability of the Houston Herbicide project. The resulting network was more like a flow diagram -- it had loops. But in the hands of the engineers it showed that existing plant equipment slated to be part of the integrated new process were not reliable enough to permit the project to achieve design capacity. Without this little breakthrough in problem definition the plant would probably have gone through with the project and suffered a long and costly startup period.
COMPUTERS IN THE EARLY DAYS
Morgan: In addition to reprogramming the UNIVAC I programs for the UNIVAC 1103A and 1105, the scope of the computations was enlarged to include two more projects in order to determine how to extend CPM to the design and procurement functions. For this, rather involved experimentation was proposed for finding the point at which CPM could or should be introduced into the project planning process. The apparent cost and effort seemed overwhelming. Today, with the low cost, high capacity, and speed of computers -- and enlightened attitudes -- the issue would not even be raised.
The logistics of generating schedules in those early days is especially interesting. Magnetic tape input was prepared on the UNIVAC I in Newark, Delaware, and flown to Palo Alto, St. Paul or Rome, N.Y. for computation on the appropriate available 1103A or 1105. The results were then returned for printing the output on the UNIVAC I. Initially there was some concern about this processing strategy. It required considerable fine tuning to get interchangeability between tape drives within a computer system. We were taking the fine tuning problem two steps further -- not only between two systems, but between systems of entirely different design.
There was also the concern that tapes might be degaussed by rotating aircraft equipment or something else -- this was before airport X-ray security checks. Today, many organizations wrap their tapes and floppies in aluminum foil, which is just what we did then. You have to have lived through the period when there were very few computers around to really appreciate how fantastic it is to have the equivalent power on one's own desk these days.
DID WE SOLVE THE CORRECT PROBLEM?
Jim: I have been asked on occasion if we really solved the correct problem in those early days. It can be argued that developing a whole series of schedules is overkill. It certainly complicated the computer programming requirements. But this parameterizing of the problem was intended to give planners opportunities for time-cost trade-offs. Though the model has a lot of mathematical interest, it may not fit the practical planning and scheduling environment.
What emerged as fundamental were the output edit programs that produced the early and late start and finish times, the total float (slack) for each activity, and the need to sort this output in a variety of ways for different project people to use. If one does no more than intelligently draw the network and calculate the early and late times and float, one has 90% of the value to be gained from using network methods for project planning and scheduling. Often the sophistications beyond this are no more than bells and whistles, or substitutes -- often poor ones -- for in-place accounting systems.
It was Morgan who defined the now classic schedule reports so familiar to CPM'ers. He was the first to recognize the importance of various kinds of float. Among his inventions is “free” float, still seen sometimes on computer printouts, to support some of the early approaches to manpower leveling. In the early days there was some controversy among subcontractors over who “owns” the total float. A concept of “scheduled” float was proposed as a mathematical answer to this problem.
…..by cutting average turnaround downtime by some 25% through CPM, production to sales was increased enough in the first year to more than underwrite the CPM development.
One of the cleverest uses of total float is the “float trend chart,” a device for estimating project completion based on monthly changes in the amount of float in the network. I became sold on this technique in 1974 after using a variant to show that a certain North Sea oil development project was slipping by one third of a month per month. At that rate the project would come in six months late. The projection, and the rationale for it, were not taken seriously. It was no surprise to learn that the project came in one year late.
I have been accused of letting my education get in the way of my perception by not recognizing the simpler concept of CPM that emerged from our output edit programs right from the start. This may well be true -- the calculation of the early and late times and float is trivial mathematically. Certainly if we had restricted our thinking at an early time, the development costs and time period might have been considerably reduced, all other things being equal. In particular, all the needed computer calculations and edit runs could have been done in Newark, Delaware, on the UNIVAC I.
But I am also inclined to believe that our CPM might not have come to be at all without this parametric time/cost model. It added that extra something which heightened interest at the critical moment by setting everyone's sights a little above the attainable. It had the psychological effect of enhancing credibility.
I think the same thing may have happened in the PERT development with its probability-based model. This is also a model with great mathematical interest. But as with the CPM parametric time/cost model, the original PERT model does not completely fit the existing environment. In consequence PERT evolved into something similar to CPM as generally practiced some 10 to 15 years after their conceptions.
I really wonder if the simpler evolved form would have been credible enough at PERT's inception to demand the required development funds and management support.
THERE'S A ROLE FOR THE PARAMETRIC MODEL
Morgan: I tend to agree with Jim on this point. The original CPM parametric time/cost model and the results derived from it served a very useful purpose. In the first “live” tests it showed, but did not convince others, that very significant improvements in time could be obtained at very minor increases in cost -- a variant of Pareto's Law. People like me were brought up in an environment where a suspected slippage was dealt with by “beating the project to death” with manpower. This across-the-board expenditure was commonplace and stupid. Until Jim's parametric model, we could never prove it. The late Harry Goode (University of Michigan) arrived at the same conclusion when he was consulting with us at Du Pont.
TABLE 2. CPM DEVELOPMENT TEAM
|from Du Pont|
|C.A. Baxter||Design Division participant in live tests.|
|W.N. Church||Control Division (Estimating) participant in live tests.|
|M.S. Demurjian||Manager of UNIVAC I installation; Computer program supervision.|
|Geo. J. Fisher †||Engineering supervision.|
|J.W. Greene||Resident Engineer at Louisville; TA test.|
|P. Hayward||Mathematician who worked on the preliminary analysis of the construction scheduling problem.|
|E.R. Hyde||Project leader on live tests (Construction Division).|
|H.B. Mundy||Construction Division participant in live tests.|
|W.G. Ranson||Construction Division participant in live tests.|
|J.A. Robinson||Mathematician who worked on the preliminary analysis of the construction scheduling problem.|
|James E. Sage||Networked “Fisher Works” and developed time and cost data.|
|D.D. Sanford †||Engineer participant in live tests.|
|John S. Sayer||Engineering Manager responsible for the project.|
|H. Silon||Resident Engineer at Lousiville; TA test.|
|M.E. Smith||Initial ideas for manpower leveling; TA test.|
|Morgan R. Walker||Technical coordination/promotion; Networked “Fisher Works” and developed time and cost data; Developed “float” concepts & manpower leveling methods; participated in all phases of the project.|
|E.W. Webb||Construction Division participant in live tests.|
|E.A. Wienman †||Project leader for design work on live tests.|
|from Remington Rand Univac|
|C.F. Berry||Sales Support programmer.|
|Al Fera||Account Representative; promotion.|
|J.E. Kelley, Jr.||Develop math model and computer algorithms; consultant to the project.|
|Nathan Knoch||Univac 1103A/1105 programmer.|
|Lyle Langdon||Univac 1103A/1105 programmer.|
|John W. Mauchly †||Technical supervision.|
|M.S. Quinn||Univac I programmer.|
|P. Sassouni||Univac I programmer.|
|Les Shaw||Univac I programmer.|
Even today, in certain applications, I would recommend its use. In lieu of developing slopes, I would probably arbitrarily assign a value -- a sort of “intuitive sensitivity index.” This would reduce the data preparation work. The same thing could be done to generate “crash” times.
The CPM development was capped with the results of applying it to turnarounds at Du Pont's Louisville plant. This important case is well-known. It suffices to say that by cutting average turnaround downtime by some 25% through CPM, production to sales was increased enough in the first year to more than underwrite the CPM development.
In March 1959, CPM was presented to the public at large.  Since then the few who participated in this important first step have gone on to other things. Table 2 brings them back together again just for a bow.
CPM AND PERT -- CHICKEN AND EGG?
Jim: How did CPM's development relate to PERT's? We surely can't leave this avenue unexplored, considering the major impact PERT's developers have had on the theory and practice of project management. But, there's really nothing to say about a connection between the two developments. Neither Morgan nor I ever heard of PERT, nor of the Special Projects Office, before early 1959 when Tony Astrachan mentioned it while preparing his Business Week article.
A story is circulating that the Special Projects Office had contacts with Du Pont as early as April 1957, and learned about “main chain” scheduling. We have absolutely no knowledge of any such contacts. The earliest meeting we can document is April 2, 1959, when Morgan, Sayer and Fisher visited the Special Projects Office to exchange views. It is possible, I suppose, that earlier contacts might have been made through Haywood and Robinson, or their associates. But there are more reasons to doubt such a contact than to believe it could have been made without our knowledge. If the PERT people built on the Du Pont work, it was outside channels Morgan and I had access to, say through contacts at Lockheed, Palo Alto, where Du Pont had a cooperative venture in scheduling, and where we did some of our calculations. But as far as Morgan and I are concerned, PERT was built independently from whole cloth.
THE COMMERCIALIZATION PERIOD
Given man's built-in resistance to change, there's a good chance CPM and PERT would have been relegated to oblivion had it not been for the Polaris Missile Program, and John W. Mauchly's insistence on bringing CPM to the commercial marketplace. One indicator -- upon Chief Engineer Read's retirement, interest so waned at Du Pont's engineering department that it took until 1968 for them to adopt CPM as standard practice. Here's how CPM's developers overcame this resistance to change in the early days of Mauchly Associates, Inc.
JOHN MAUCHLY AND HIS NEW COMPANY
Jim: For various reasons, Mauchly's group at RemRand was disbanded in early 1959. There was little incentive to stay on. The sudden movement of talent prompted Mauchly to start -- probably prematurely -- a new company “to provide experienced consultation and services covering the entire range of possible EDP applications.” Mauchly's real interests at the time ran “the gamut from educational devices for computer trainees to logical analysis and design of specialized computer systems to solve specific applications problems.” Ultimately, investments in hardware development would destroy the company. But with this charter, we moved into offices above a boutique in Ambler, Pennsylvania, on April 9, 1959. Morgan started in July. Rocky Martino of RemRand, Canada, joined later in the year.
Much has been written of the life and genius of John W. Mauchly. How his interest in weather prediction moved him, in the late 1930's, to invent electronic devices essential to the computers needed to solve the problem. How WWII, the U.S. Government, and the University of Pennsylvania, provided him the opportunity to realize his ideas in the ENIAC, the first electronic computer. How he and J. Presper Eckert, his partner in the ENIAC development, went on to build BINAC and UNIVAC, the first electronic computers built commercially. How, in 1973, in a dispute between RemRand and Honeywell over payment of royalties, a federal court invalidated his and Eckert's computer patents, and raised doubts in the public mind over their priority in inventing the electronic computer. John viewed this as the greatest tragedy to befall him.
What is not so well-known is how John took chances on people he thought had interesting ideas and superior talent, who might compliment his wide range of interests. CPM was but one creation of his intellectual family. Many others were given the opportunity to develop with his encouragement and guidance, from the humble genius who generated large-order magic squares to help John with imaginative ways to design computers, to renowned figures like Grace Murray Hopper, the grandame of high-level programming languages. Incidently, John's ShortCode for the BINAC -- the first compiler for programming in a mathematical shorthand -- was a conceptual forerunner of FORTRAN.
John had a great knack for inventing new and imaginative solutions to pressing real-world problems. My own professional skills matured enormously by watching him do this again and again, and by trying to emulate him. It was the continuation of this type of creative participation that I so looked forward to on joining Mauchly Associates.
ECKERT-MAUCHLY, REMINGTON RAND, AND THE ELECTRONIC COMPUTER
The development of CPM owes much to the computer, its inventors, and the company that nurtured it through the early years. Historically, Remington Rand was an amalgam of many companies, some founded over 100 years ago. Two paths in its evolution are of interest to the story.
The first began in 1873, when Christopher Sholes, editor, printer and inventor, teamed up with E. Remington & Sons to manufacture and market the first commercial typewriter. As the typewriter business flourished, a parallel success story began in 1890 when James H. Rand, Sr., developed the first visible index equipment. Rand's enterprise grew by acquiring other office equipment companies. In 1927, the two companies merged to form Remington Rand, Inc., and continued on the acquisition trail to become an important multi-national. In 1955, Remington Rand merged with Sperry Gyroscope to become the Sperry Rand Corporation, which finally merged with the Burroughs Corporation a few years ago to become UniSys.
The second path begins in 1946 when John W. Mauchly and J. Presper Eckert started the Electronic Control Company (renamed the Eckert-Mauchly Computer Corporation) of Philadelphia. Their goal: commercialize their wartime success with the ENIAC (Electronic Numerical Integrator and Calculator). This first electronic computer, which they designed and built at the University of Pennsylvania under contract with the U.S. Army, filled a room with about 18,000 vacuum tubes. ENIAC was actively used at the Aberdeen Proving Ground until 1955, when it was put on exhibit at the Smithsonian Institution.
In 1949, Remington Rand had completed a magnificent Laboratory for Advanced Research on the shore of Long Island Sound. It was put under the direction of General Leslie R. Groves of atomic bomb fame. They tried, without success, to hire away some of the Eckert-Mauchly engineers, indicating their intention of entering the computer field. Sadly, Eckert- Mauchly's principal benefactor, Henry L. Strauss of American Totalizator, was killed in a light plane crash about the same time, forcing the fledgling company to sell out to Remington Rand the following year. 1950, the year of the sale, saw the company deliver its first commercial computer, the Binac -- to Northrup Aircraft.
The next year, 1951, Eckert-Mauchly delivered the first UNIVAC -- to the Census Bureau. This machine was actually operated at the factory by the Bureau for over a year before being moved to Suitland, Maryland. Serial #2, for the U.S. Air Force, and serial #3, for the U.S. Army Map Service, were undergoing final assembly and test, and were delivered the next year. The Air Force stationed Jim Kelley at the Eckert-Mauchly factory that winter of 1951–52, to learn to program and operate UNIVAC serial #2. He had the opportunity to work on all three UNIVAC machines. It was a machine like those that were used in the development of CPM at Du Pont.
In 1952 Remington Rand acquired another young computer firm, Engineering Research Associates of St. Paul, Minnesota. They had built special purpose digital computers for the U.S. government. Jim Kelley got to work with two of these machines at The George Washington University under an Office of Naval Research contract -- the so-called Logistics Computer, and an old electro-mechanical relay device rumored to have been used by one of the intelligence agencies. Both machines had big drum memories. These machines were the grandad-dies of the UNIVAC 1100 series computers used at St. Paul and elsewhere for generating schedules for the various real-project tests of CPM.
BUILDING THE CPM TRAINING BUSINESS
Morgan: After two years of concentrated effort on the CPM development, more CPM was the last thing Jim and I wanted to do. But after trying to market everything else we had to offer, CPM turned out to be the only product we really had to sell -- at least in the short term. Even so, it was an undeveloped market. The recommendations of a core group of CPM users was going to be essential. Perhaps this core could be developed from a public CPM workshop course.
Preparations for the workshop took the better part of September and October 1959. It was down to the wire compiling a mailing list and distributing course announcements. The mailing was about to go out when a misprint in the date was discovered. With no leadtime there was nought but to hand-correct each announcement.
The 5-day workshop took place at the Franklin Institute, Philadelphia, November 16–20, 1959. All the CPM fundamentals were covered, even the cost curve computational details, and early manpower leveling schemes. By Tuesday afternoon teams of participants were networking small pilot projects. Cost curves and schedules were calculated and printed, and the results of each critiqued by the whole class. RemRand was more than eager to have us use the UNIVAC I programs at the Institute's Data Center.
The week before the course only five people had signed up -- 20 were hoped for. Either cancel or beat the bushes. A good bit of the expected profit went into frantic long distance phone calls to engineering departments of the Fortune 500. By Friday afternoon 15 had signed up and we were in business.
Ironically, we had a man from Du Pont and another from RemRand in the first CPM course. The head of IBM's facilities planning group also came. His application was much debated. At the time we had a proposal outstanding to put IBM into the CPM business -- training, manuals, computer programs -- the whole nine-yards -- a real giveaway. To be sure, IBM's man went home a CPM convert. He became the first, outside government, to make CPM a contract requirement on construction jobs.
You guessed it -- IBM took the longest time to indicate their noninterest. By then their LESS program was well developed. Mathematician Ray Fulkerson of The Rand Corporation was even contracted to crack the cost curve algorithm. Was it bad breath, Eckert-Mauchly selling out to RemRand, or the gag: “IBM” = “Invented By Mauchly”, that turned them off?
….(The) “best” (plan) can only be gauged relative to the planner's ability and experience, and to his view of the project objectives and environment.
…..This example also underscored the bad habit of planning work sequences and scheduling work simultaneously.
The insight of a simple class project -- a pipeline renewal -- underscored the fact that no one can consistently construct the “best” schedule for a project. From a list of 16 jobs and their durations a typical class of 20–30 would produce 9–10 different networks, ranging in duration from 270 to 380 hours. Indeed, “best” can only be gauged relative to the planner's ability and experience, and to his view of the project objectives and environment. This example also underscored the bad habit of planning work sequences and scheduling work simultaneously.
The first workshop was a big success. Most participants went home and tried to apply some level of CPM. Some, like Walter Cosinuke and Herbert Berman of Catalytic, got a lot of mileage from their exposure. Just drawing a network was to improve project planning many-fold. Some called us in to help on specific projects and to train their people. One thing led to another in quick succession and we found ourselves in the project management training and consulting game for keeps. From that workshop on for a couple of years our workshops, both public and private, were generally oversubscribed. By the end of 1962 Mauchly Associates had trained close to 1,000 people, and were in competition with a dozen or more other consulting groups doing much the same thing. Such was the growth of interest in CPM and PERT!
The workshops introduced us to Montreal's postwar rebuilding cycle, among other things. We helped Anglin-Norcross with CIL House, Perini, Ltd. with the Bank of Commerce Building, Webb & Knapp with Place de la Concorde, and Perini Pacific with the Frazier River Bridge piers and bents. A bit later the Montreal Expo was planned and scheduled using CPM. They would never have made opening day without it. Materials and debris had to be scheduled by the minute on two access bridges to the island, using a dedicated computer.
I'll always remember the Tidewater Refinery cat cracker shutdown. It was notable as the first major third party maintenance contract. We did only the calculations. The network was drawn on a sheet of paper 150'x4', rolled up like a Torah on two cranks mounted at either side of a drawing table -- an exaggerated piping drawing. Fortunately we had a loft where we could stretch the drawing up one side and down the other while half a dozen people, on hands and knees, made takeoffs on data sheets for the keypunch operators. Lots of sore backs, knees and elbows that weekend.
THE EASTERN JOINT COMPUTER CONFERENCE
Jim: In addition to the the first CPM workshop, we tried other ways to focus public attention on our capabilities. With a heavy computer orientation, what could be more natural than to announce our wares at the 1959 Eastern Joint Computer Conference (EJCC) in Boston, December 1–3.
By the time the idea dawned the deadline for papers had passed. A little politicking put us on the program. The conference planners offered an award for the best paper -- an attempt to improve the usual “careless or obtuse” presentations. A well-prepared slide show could win the award and focus attention on CPM. We went too far in perfecting our act, were classed as professionals, and were disqualified for the award. But, at least we had reprints to distribute.
Jim: The EJCC did lead to an important consulting contract with Dow Chemical, during which the basis for our manpower leveling algorithms were conceived. This was perhaps the key unsolved technical problem when we started up Mauchly Associates. By “manpower leveling problem” people referred to the objective of operating with a fairly stable force over the mid-die 50% to 75% of the project's life. However, the numbers of variables that can be involved is extremely high. Their interrelations are complex. And the criteria for a “good” or “optimal” solution are often incompatible. Every mathematical formulation of this problem that I have ever seen is a mess, and totally intractable. One must resort to heuristic methods, using a computer, to get useful results.
Perhaps the simplest, most successful and long-lived approach to this problem was devised in February/March I960 by Morgan, Charles W. Bachman and Jack Westley of the Dow Chemical Company. The early time schedule for Dow's project peaked near 150 boilermakers -- there were only about 50 in the area. An ad hoc IBM 650 computer code was written just to take care of this problem. We called the algorithm the “J-priority” method -- project activities were processed in “successor” or “J-event” order. We made proposals to Du Pont and the U.S. Navy Bureau of Ships to expand on these ideas. At Du Pont we lost the competition to CEIR, who proceeded to develop RAMPS (Resources Allocation and Multi Project Scheduling).
But starting in August, I960, we did extensive experimenting with our method under a BuShips contract.[33l Figure 3 shows the results of one of the early experiments. This project involved the rehabilitation and maintenance of a WWII submarine. The total force requirements peaked at 259 men during the period the vessel was scheduled in drydock. Because of space restrictions and other considerations, such a peak was impractical. The experiment involved determining the sensitivity of the project end date to reductions in peak force. In fact, a 25% reduction in peak was possible with virtually no delay. As Figure 3 shows, a 34% reduction would cause a 7% delay; 42% reduction, a 14% delay; 50% redution, a 19% delay.
By studying the details of the computation it was seen that better results could be obtained by artifically delaying the start time of pivotal jobs with large total float to their late start -- essentially scheduling them after the peak. The result was that a reduction in peak of some 40% was possible with under a 4% delay in the project.
The most important thing to come out of these experiments was the philsophical conviction that there is no objectively “best” schedule. There are so many competing factors involved (e.g. the project duration, force levels, both total and by craft, craft work continuity considerations, facility and heavy equipment availability, etc.) that it is essential to be able to select from a variety of explicit possibilities one which can be lived with.
To provide a simple, effective tool for testing the sensitivity of these factors and for producing schedules, we generalized the J-priority method to permit the user to vary many of the factors involved, particularly the order in which jobs were processed. The so-called late start sort priority order became basic to the method. It generalizes the idea of delaying floaters around peaks, but does it in a more flexible way than can be done with restraints. The resulting algorithm was named RPSM (Resources Planning and Scheduling Method). We used it for years, especially on overhaul work. We even expanded it to multi-project scheduling and workload forecasting on a subsequent contract with BuShips.
There seem to be essentially two algorithmic approaches to the manpower problem:
- The “serial” approach (schedule the activities individually in precedence or serial order), and
- The “parallel” approach (schedule all active jobs as a group on a time unit basis, i.e. in parallel with each other).
RPSM is a serial method. The parallel method seems, a priori, to offer much greater flexibility. This is probably the reason most early scheduling systems were based on parallel methods. They generally run slower than serial algorithms. They are also more complex, making it difficult for the user to interpret why he gets the results produced. And if one is not careful, jobs with lots of float may be rescheduled excessively earlier or later than in the previous schedule. This effect is quite upsetting to field planners.
Figure 3. RESOURCE LEVELING EXPERIMENTS Fleet Submarine Overhaul
THE SKEDUFLO COMPUTER
Jim: Mauchly always had an active interest in education, particularly in techniques and devices for teaching people about computers or their applications. Morgan worked with him on a game or computer model which used marbles for bits. A.C. Gilbert (erector sets, American Flyer trains, etc.) was interested. They were being clobbered by competitors like Ideal, and wanted to change their image by introducing “scientific” toys. Morgan spent considerable time completing the missing circuits (gates) and making engineering drawings from which A.C. Gilbert could prototype. Ownership differences squelched the deal.
One day John and I were talking about electric-analog methods, exploring for more efficient algorithms and devices for capturing the imaginations of potential CPM clients. Some step function problems halted the discussion. But next morning, Mauchly was back with a circuit and a voltmeter to show me his new invention -- the electric analog of a job with its normal and crash times and costs, programmed using potentiometers. We were now developers of computer hardware, with special interests in hybrid computers, i.e., combined analog-digital computers.
Before long we moved into larger quarters, geared up to do electrical engineering, and hoped to develop another UNIVAC. Fortunately the CPM business was booming enough to underwrite some of this expansion. But the only product to emerge was the SkeduFlo Computer, a transportable device -- the network portion alone was suitcase sized and weighed 75 pounds -- that could solve a 30-arrow network. The connections between arrows were programmed in a patchboard. The cost curve and job durations were plotted on an analog plotter. Much larger devices, with digital input and output, were planned, but, to my knowledge, never designed.
Charles Clark, of PERT fame, addressed a problem similar to the parametric cost model with a mechanical analog similar to one Mauchly showed me before his SkeduFlo design. But these analog models don't seem very well adapted to digital computation. I don't think we ever sold a single unit.
GROWTH OF THE CPM/PERT BUSINESS
Morgan: The promotion of PERT by the Navy and its imposition on Polaris contractors was the principal cause of a phenomenal short-term growth in the use of network methods. Of course, the parallel and competitive promotion of CPM contributed. This interest can be seen in Figure 4, where annual counts of articles in periodicals, technical papers and manuals, and books about CPM and PERT are plotted over time. As is often the case with new fashions, more was promised than could be delivered. Predictably, a sharp peak of interest was reached early on, which gradually fell off. By the late 1960's interest reached a low ebb, in part because of the depression in the aerospace business just after the middle of the decade. The downward trend had already set in! However, interest quickened again in the early 1970's, especially in Europe.
TAKE A BOW
Jim: It is one thing to have an idea, quite another to make it work. It is yet a third thing to persuade anyone else to use your workable idea. As in many other endeavors, the success of CPM in all three of these phases has resulted from the work of many people. The basic ideas for CPM, and the techniques for dealing with it preceded our efforts in the works of many other people.
Making CPM work was a team effort of considerable magnitude that needed the foresight and approval of a Granville Read (see Table 2). Although Morgan Walker once told Read he was “interlocutor, dictator, huckster, teacher and other equally useless functions", the team could not have functioned and CPM would never have been made to work without his efforts.
Credit for much of what CPM has become belongs to John W. Mauchly, who not only provided the environment in which CPM originally developed, but had the foresight to see its potential, and had interest in promoting it.
Figure 4. CPM/PERT: The First Decade Patterns of Interest as Indicated by Total Articles and Books
OUT OF THE MAIN STREAM
Morgan: The proliferation of CPM has been a great wonder to Jim and me. There's a sense of pride to find one's children studying it in the university -- and in a diatetics course, too? And it seems to pop up in rather unlikely places. How about Richard Schweickert of Purdue's Department of Psychological Sciences applying CPM to mental processes. And several medical procedures have been given serious CPM treatment -- the spoof by Loren J. Saindon of a hernia operation is not one of those. Saindon went on to compile numerous culinary recipes in the form of arrow diagrams, each arrow a quantity of a food component, or a cooking action (dice, simmer, boil, etc.)and duration, the whole showing the order in whichtodothings. lt seems easier to follow his recipes than those in the wife's cookbooks. She may have a different opinion.
CPM is also worth a laugh or two. Read Mike Berger's “If Noah Built the Ark Today” (Management Review, July 1969, pp. 2–8), a spoof of network planning, computers, and other technology spinoffs. [Ed. Note: See the September issue of the PM NETwork.] Sometimes the virtues of thriller heros includes expertise in CPM (e.g. in The Quiller Memorandum). Many people have been inspired to draw networks of rather outlandish projects, like the faculty of Nederlandse Economische Hogeschool's analysis of England's “Great Train Robbery.” It is alledged that the robbers used CPM to plan the heist, and that Scotland Yard used it, in turn, to solve the case. This robbery has been made into a movie.
Sometimes artistry is the objective, as with the clever network to plan Christmas preparations shaped in the form of a Christmas tree. But by far the most artful, and incomprehensible, network we've ever seen is a winding Japanese creation that looks like a “connect the dots” puzzle of a kabuki mask, with job descriptions in kanji.
1. Also see Willard Fazar. “The Origin of PERT.” The Controller, Dec. 1962. pp.598–621.
2. Granville Read headed up Du Pont's contribution to the Manhattan Project, and most of his staff at this time were on that project, too.
3. Hayward, P. and J.A. Robinson. 1956. “E.S.D. - Business computations - 300001. Preliminary Analysis of the Construction Scheduling Problem.” Memo to T.L. Leininger, December 20, 1956. Engineering Department. E.I. du Pont de Nemours & Company, Wilmington, Delaware.
4. Kelley, J.E., Jr. 1957. Computers and Operations Research in Road Building. Proceedings of the Conference on Operations Research, Computers, and Management Decisions, 58–63. Cleveland: Case Institute of Technology.
5. The “direct” costs were primarily the resources applied to the activity, the variable components of which were labor and equipment. Supervision and other overheads were the “indirects.”
6. We adopted this term for marketing purposes about May 1959, christening our product the Critical-Path Method (CPM).
7. Kelley (1957) op. cit. Also see Kelley, J.E., Jr. “Critical-Path Planning and Scheduling: Mathematical Basis,” Operations Research, 3(1961)296–320.
8. Kelley, James E., Jr. “The Construction Scheduling Problem (A Progress Report).” UNIVAC Applications Research Center, Remington Rand Univac, Philadelphia, Penna. April 25, 1957. 21p.
9. Berry, C.F., “Computer Scheduling (Job List & Sequence),” program module flow sheet, dated April 24, 1957.
10. Coding was done using the Generalized Programming compiler. It allowed the programmer to use symbolic addresses, subroutines, and other programming facilities within the UNIVAC C-10 machine code, which was mnemonic and easy to use compared to other computers of the time. Fortran was not made public until 1957, and was certainly not available for the Univac for our project.
11. We still have the computer output for “IEC Test No. 3 - Project Scheduling,” dated September 25, 1957.
12. Computer programming was tougher in those early days when high-level languages like Fortran, Cobol, Pascal, etc. were either in the future or only just getting off the drawing boards.
13. The type network implied by the Haywood and Robinson proposal is not at all clear to me since their ditto report came without figures and technical appendix. The only hint -- they refer to the immediate predecessors of a job as its “roots” and to its immediate successors as its “branches.”
14. Walker, Morgan R. “Project Scheduling Rules for Sequencing,” Engineering Department, E.I. du Pont de Nemours & Co. August 28, 1957. 5p.
15. In one sample of 15 CPM networks I once calculated there were (25 10)% dummy activities. There were also (1.6 1 0.2)% activities per event. These statistics seem to have held up over the years.
16. Fondahl, John W. 1961. “A Non-Computer Approach to the Critical-Path Method for the Construction Industry,” Department of Civil Engineering, Stanford University. Nov. 1961. Also: Wiest, J.D. and F.K. Levy. 1969. A Management Guide to PERT/CPM. Prentice Hall, Inc. Some (if not all) commercial packages which support activity-on-node networks convert the project network to the CPM format, i.e. the activity-on-branch form, before proceeding with the calculations.
17. Hyde, E.R. “Integrated Engineering Control Study of Engineering Department Project Scheduling,” E.I. du Pont de Nemours & Co., Engineering Department, Wilmington Delaware, January, 1959.
18. J.E. Kelley, Jr. and Morgan R. Walker. “Critical-Path Planning and Scheduling,” Proceedings of the Eastern Joint Computer Conference, Boston, Dec. 1–3, 1959. pp.160–173.
19. Kelley, J.E., Jr. 1961. Planning and Scheduling Overhaul Shipwork in Naval Shipyards. Final Report, Bu-Ships Contract NObs78951, April 1961. 65p. + 16 figs.
20. Kilpatrick, D.C. 1972. “Float Trend Charts.” Congress Book 1:191199. Third International Congress on Project Planning by Network Techniques. Stockholm, Sweden: Internet 72.21. Kelley and Walker (1959) op. cit.
22. Astrachan, A. 1959. “Better Plans Come From Study of Anatomy of an Engineering Job.” Business Week, March 21, 1959. pp.60–66. One of the finest presentations of early CPM is: Walker, Morgan R., “Project Planning and Scheduling,” Engineering Department, E.I. du Pont de Nemours & Co., Wilmington, Del., 123p.
23. Charles E. Clark was the principal author of PERT. It is to my sorrow that I never had the opportunity to meet him. The early key documents are:
- PERT Summary Report Phase 1, Bureau of Naval Weapons, Department of the Navy, Washington, July 1958;
- PERT Summary Report Phase 2, Bureau of Naval Weapons, Department of the Navy, Washington, September 1958.
Fazar (op. cit. 1962) reports that he gave the technique its name, and that formal work on it began February 6, 1958. Within a week Clark presented the outlines of the method.
24. Fisher, George. “Trip Report - Navy Department - PERT System.” Memo to E.O. Dean, E.I. du Pont de Nemours & Company, Wilmington, Delaware. April 6, 1959Â· Fisher writes, “Arrangements have been made to follow up on this first contact….”, further indicating no earlier contact with Special Projects had been made by IEC.
25. Curiously, some of the basic concepts of PERT are to be found in Haywood and Robinson's report. Terminology: “immediate predecessor,” “immediate successor.” Recognition of the possibility that job durations may not be known with practical certainty: “If, as is true in practice, the [job] completion times have probability distributions about their mean values, the question of what is the best course of action to take in meeting a delay becomes considerably more complicated, leading into the realm of game theory.”
26. The first ENIAC calculations were a mathematical simulation of the hydrogen bomb. Its prime mission, for which it was used for many years, was to calculate firing tables for new weapon systems.
27. Assigned to RemRand when they bought out Eckert-Mauchly years earlier.
28. In actuality, the court decision states that Eckert and Mauchly were the only inventors of ENIAC, but that their patent was invalid because they delayed too long in making application, and this contrary to the decisions of two earlier courts which upheld the validity of the patent.
Much has been made of a red herring introduced at the trial to discredit Eckert and Mauchly -- the experiments with computational equipment of Dr. John V. Atanasoff, of Iowa, in the late 1930's. The court ruled that Mauchly had learned about electronic digital computing from Atanasoff, despite clear evidence that Mauchly had been building electronic computing devices for at least four years before he met Atanasoff, and despite the fact that electronic ENIAC was in no way related to Atanasoff's electro-mechanical device.
Since billions of dollars are at stake, it is a forgone conclusion that Eckert and Mauchly, like Columbus, will never get their due. Had the Spanish crown not welshed on its deal with Columbus, he and his descendents would have owned a good part of the New World, and America, instead of being named for a self-serving Florentian, might be named Columbia instead.
29. Fulkerson, D.R. A Network Flow Computation for Project Cost Curves, Rand Paper P-1947, The Rand Corporation, SantaMonica, California, March 18, I960. (Also published in Management Science.) To our knowledge, only Ford Motor Company programmed Fulkerson's algorithm in those early days -- GM programmed ours.
30. Berman attended our second workshop.
31. Theoretically, integer programming formulations of the problem can be solved “exactly.” But I suspect they are still impractical for large applications.
32. In the early days events were numbered so that the tail-event was numerically less than the head-event, which made it so no activity preceded a successor activity in the sorted input list. This event numbering limitation was quickly eliminated by better algorithms.
33. Kelley (1961) op. cit.
34. The details and this and other early resource scheduling methods are described in Kelley, J.E., Jr. 1963. “The Critical Path Method: Resources Planning and Scheduling,” Chapter 21 in Industrial Scheduling. Eds. J.F. Muth and G.L. Thompson. Englewood Cliffs: Prentice Hall.
35. I have been told that the original RPSM method forms the basis for the manpower programs in the PREMIS system, being an evolutionary outgrowth of the IBM 1620 programs we developed at Mauchly Associates in the early 1960's. I have heard it was even being marketed as the “Kelley Algorithm,” though the real credits go to Walker, Bachman and Westley.
36. For more on SkeduFlo see: John W. Mauchly. “Critical-Path Scheduling.” Chemical Engineering, April 16, 1962; and, Plotting time-cost schedule. Business Week, February 17, 1962.37. Clark, C.E. “The Optimum Allocation of Resources Among the Activities of a Network,” System Development Corporation, I960. Others have probably had similar ideas. We may cite K. Shankar and K.P.K. Nair, “On Electrical Analogy of Critical Path Method”, Indian Institute of Technology, Bombay, 1968.
JAMES E. KELLEY, JR.
Jim Kelley hails from New Haven, Connecticut, where he attended the local public and parochial schools. He took degrees in mathematics from Providence College and The American University. In the early 1950's the U.S. Air Force trained him in the emerging fields of computers and management science, fields in which he has spent most of his professional life. For some eight years he worked for John W. Mauchly, co-inventor of the electronic computer, first at Remington Rand, then at Mauchly Associates.
Following 10 years of work in military logistics and operations research, Jim embarked on a 20-year career as an engineering and project management consultant, including partnerships in CPM Engineers and Kelley Schwartz.
Throughout his career, Jim has published numerous articles on computers, mathematics and project management. More recently he has taken up writing, and has published five books for users of personal computers.
Jim's best known achievement is his work with Morgan Walker to develop CPM. For this pioneering effort he received honorary mention for the Lanchester Prize in Operations Research, the American Association of Cost Engineers' 1965 National Award of Merit, and elevation to Honorary Membership in the Society for the Advancement of Management.
Over the past 25 years Jim has used much of his free time while traveling on assignment to poke in museums and libraries studying the technology of late medieval cartography and navigation. He is a frequent speaker on topics ranging from manuscript marine charts, to the astronomy and weather lore of 15th century mariners, to late medieval weights and measures, much of which he has published. He has done significant computer studies of Columbus's navigation and of early marine charts of the New World, and has recently published (jointly with Oliver Dunn) a new Spanish transcription, English translation, and concordance of Columbus' Journal of his first voyage to America.
Jim lives in Melrose Park, Pennsylvania, with his wife, Peg, where he writes, plays the piano, and enjoys the visits of their nine children and seven grandchildren.
MORGAN R. WALKER
Morgan Walker grew up in Montclair, New Jersey. His studies in aeronautical engineering were interrupted by WWII, during which he served with the U.S. Army in the Philippines. On his return to the University of Michigan, with technology outpacing the curricula, and a surplus of unemployed aero engineers, Morgan augmented his education with courses in Business Administration and Industrial Engineering before taking his B.S.E. in Aeronautical Engineering. He went on to graduate work in applied statistics at Carnegie-Mellon, and to positions in industrial and management engineering, first with U.S. Steel's National Tube Division, and then with the Engineering Department of E.I. du-Pont.
It is at Du Pont where Morgan was introduced to project management and computers, participating in AEC plant design and construction, and in the installation of the company's first computer system, and the study of where it might be used. This experience prepared him well for his role as co-developer, with Jim Kelley, of CPM. Subsequently, he joined Mauchly and Kelley to establish Mauchly Associates as a major purveyor of CPM educational and consulting services. He was honored with the American Association of Cost Engineers' 1965 National Award of Merit for his work on CPM.
After Mauchly Associates, Morgan went on to a career of marketing and sales of computer peripherals, mostly of rigid disk files and printers. In this field he held top management positions, principally with new venture start-ups. More recently Morgan has been in engineering, administrative and financial planning at a computer aided engineering software firm. Currently he is is Product Marketing Manager for Microscience International, a Winchester disk drive manufacturer.
Morgan is a former member of ASQC, SAM and ACM. He and his lovely wife, Vivian, a well-known portrait artist and teacher, reside in San Mateo, California. Between them they track five grownup children.
February 1989 pm network