The origins of CPM

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.[1] 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.[2] 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

* 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.[3]

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.[4] 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.[5]

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.”[6]

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[7] -- 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 .[8] Morgan took an earlier draft to Newark and had Curt Berry help him make a work estimate.[9] 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.

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,[10] 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.[11]

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.[12] 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.[13]

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.[14]

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.[15]

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 d_ij, a cost c_ij, 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.[16] [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.[17] 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.[18] 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.[19]

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.[20] 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

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.[21] 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. [22] 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.[23]

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.[24] 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.[25] 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.[26] 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,[27] and raised doubts in the public mind over their priority in inventing the electronic computer.[28] 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.

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.[29] Was it bad breath, Eckert-Mauchly selling out to RemRand, or the gag: “IBM” = “Invented By Mauchly”, that turned them off?

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[30] 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.

MANPOWER LEVELING

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.[31]

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.[32] 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.[34] 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.[35]

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.[36]

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.[37] 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.

A POSTSCRIPT

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.