Abstract

One of the mysteries of OR/MS teaching is no doubt the AoA vs AoN syndrome. It poses the following dilemma in connection with teaching the Critical path Method: should the popular and well established Activity on Arc (AoA) paradigm or the pedagogically and practically superior Activity on Node (AoN) paradigm be used? In this discussion we argue that it is time to eradicate this affliction and call upon OR/MS courseware developers to once and for all abandon the AoA paradigm in favour of AoN. A simple on line module is provided for experimentation with the Critical Path Method.

1. Introduction

For fifteen years I faced the following dilemma in my undergraduate teaching: should I use the popular Activity on Arc (AoA) or the pedagogically superior Activity on Node (AoN) paradigm in my Critical Path Method (CPM) courseware?

My strategy for dealing with this issue can be described as follows: I explain to my students at the outset that there are two paradigms for the exposition and implementation of the CPM, namely AoA and AoN. I indicate that although personally I regard AoN to be much superior to AoA, I nevertheless use the latter because it is the paradigm deployed in all the introductory textbooks we use as references for the subject. I express my wish that next year I will be able to use the superior AoN paradigm.

I have been going through this 5-6 minutes annual ritual for fifteen years.

This year I changed this strategy. At the beginning of the first CPM lecture I told my students that there were two paradigms for the exposition of the CPM, namely AoA and AoN. I indicated that although AoA was deployed in all the introductory textbooks that we used as references for the subject, I would use the much superior AoN. I added that I had already initiated a campaign to convince the authors of introductory OR/MS textbooks, and OR/MS courseware developers in general, to convert to AoN.

This paper is an important element of this campaign. Its target audience are developers of CPM courseware who, for whatever reasons, still deploy the AoA paradigm. In particular, it is written with authors of introductory OR/MS textbooks - as well lecturers using such textbooks - in mind.

2. CPM in brief

It is assumed that the reader is familiar with how introductory OR/MS textbooks (eg. Markland and Sweigart, 1987, Hillier and Lieberman, 1995, Taha, 1997, Winston, 2004) describe the CPM. For the reader's concenience, a summary of the basic terminology and mathematical idiom of CPM is provided in Appendix A and B.

To motivate the discussion consider the following textbook example:

Example 1 (Winston, 2004, Example 6, p. 433)

Table 1 provides information about a small project. It consists of 6 activities associated with the production of a new product assembled from two standard products, called "product 1" and "product 2".

The table consists of three columns corresponding to the three basic ingredients of a project:

Recall that the main task of the CPM is to determine:

By definition, an activity is said to be critical if any delay in its earliest possible completion time will cause a delay in the completion of the project as a whole, assuming that all other activities are completed as early as possible according to schedule.

The point to observe is that as far as the CPM is concerned a table such as Table 1 completely describes a project and therefore no additional details are required for the method to be applied. We shall call such tables project tables.

One simple way to identify the critical activities and to determine the value of T is to build the Gantt Chart of the project. We place the activities on the (horizontal) time axis as close as possible to the origin while satisfying the precedence constraints. Each activity is represented by a bar whose width corresponds to the duration of the activity.

Here is the Gantt Chart of the project described in Example 1. The critical activities are painted red whereas the non-critical activities are painted blue. The white gaps represent the maximum delays in the activities that will not cause delays in the completion of the project as a whole. The critical activities have no such gaps.

A
B
C
D
E
F
0	T

Gantt Chart for Example 1

Such a chart does an excellent job displaying the project activities in a manner that provides useful information about them individually and about the relationship between them. It falls short, however, of describing the precedence constraints. More seriously, the application of this straightforward graphical method is limited to very small project planning problems and is therefore not very useful for the solution of "real life" problems, as these usually involve many activities. Furthermore, it makes no explicit use of a fundamental project management concept and thus its pedagogical content is minimal. What is needed is a formal procedure that could be easily converted into a computer code and that is based on fundamental concepts and principles of project management and scheduling. The CPM provides a methodological framework for such a procedure (see Appendix A and B).

Table 2 depicts the results obtained for the problem featured in Example 1, where ET(j), LT(j), TF(j), and FF(j) denote the early time, late time, total float and free float of activity j, respectively.

You are invited to use the following simple module to experiment with the CPM. The module provides three pre-set problem instances. You can create problem instances of your own and/or modify the pre-set problems. For your convenience the precedence relations are specified by a boolean matrix. The selected entries in row j of the matrix represent the immediate predecessors of activity j. Thus, if you do not check any box in row j, then activity j will represent a source, and if no element is checked in column j, then activity j will represent terminal activity.

In summary: the CPM is based on the concepts early start times and late start times from which floats can be computed and the critical activities can be identified. Dynamic programming is employed for the computation of the early and late start times of the activities. The basic data required by the CPM is encapsulated by a project table. Gantt charts are commonly deployed to generate graphical displays of the results.

3. What then is the dilemma?

For various reasons, both pedagogical and practical in nature, it is often desirable to describe the CPM not in the framework of a project table, as we did above, but rather in the framework of a project network. The question therefore arises: how can we describe a project table as a project network?

Given that, like graphs, networks consist of two fundamental objects, namely nodes and arcs, it should not come as a surprise that there are two basic ways to describe a project as a network, namely:

• Activity on node (AoN) network.
• Activity on arc (AoA) network.

This means that when we teach the CPM we have to decide which one of these two paradigms we should use. It turns out that this choice is not as simple and straightforward as it should be - hence the dilemma. More specifically, the crux of the dilemma is the conflict or tradeoff between

• The obvious superiority of AoN as a modelling paradigm.
• The obvious popularity of AoA among authors of introductory OR/MS textbooks.

This description of the dilemma raises the following obvious question: if AoN is indeed superior to AoA as a modelling paradigm, why does AoA dominate the scene as far as introductory OR/MS textbooks are concerned?

This is indeed an interesting question and we shall address it in due course. But first let us quickly examine the essential features of the two competing paradigms.

4. Activity on node (AoN) networks

The construction of AoN networks is straightforward. All we have to do is

1. Create a node for each activity.
2. Connect nodes by arcs as dictated by the precedence relations.

In fact, this process is so simple and straightforward that it can be easily automated.

The AoN network for the project defined by Table 1 is given in Figure 1. (Note the definitive article: the AoN is uniquely determined by the project table and vice versa). All the familiar CPM formulas (see Appendix A) are applicable in this framework.

In summary then, within the AoN paradigm there is a crystal clear distinction between the role played by the nodes and the role played by the arcs in the project network:

• Nodes represent activities.
• Arcs represent precedence relations.

More details concerning this approach can be found in Fondahl (1961), Weist and Levy (1977), Shogan (1988), Seal (2001), Demeulemeester and Herroelen (2002), Gray and Larson (2002), Ragsdale (2003). In view of the nature of our discussion it should be pointed out that none of these references is a general introductory OR/MS textbook. We shall say more on this matter in Section 7. At this stage suffice it to say that a number of recent general introductory OR/MS textbook do adopt the AoN paradigm (eg. Ragsdale, 2004, Hillier and Lieberman, 2004).

With this in mind, let us examine AoN's arch rival.

5. Activity on arc (AoA) networks

This framework, also known as arrow-diagram, deploys arcs for two distinct purposes. That is, the arcs of the project network represent both the activities and the precedence relations between activities. This immediately raises three important questions:

1. Is the mission possible?
2. Is the network representation unique?
3. What is the "physical" meaning of the nodes of the project network?

We shall not attempt to address these questions here. For the purposes of our discussion suffice it to say that to cope with the modelling issues raised by these questions we instruct our students to obey Traditional Modelling Rules (Kelley, 1961). For example, in the context of our discussion the rules used by Winston (2004) can be rephrased as follows:

Then we advise our students:

• Bad news: Subject to these rules it is often impossible to convert a project table into an equivalent project network.
• Good news: This difficulty can be resolved if dummy activities are allowed.

For example, the AoA network depicted in Figure 2 represents the project described in Example 1. Observe that X is a dummy activity introduced in order to avoid violating Rule 5.

Figure 1. AoN representation of Example 1

Figure 2. AoA representation of Example 1

Once the project network has been constructed, we can identify the critical activities by computing the total floats of the activities and selecting those activities whose total floats are equal to zero.

In this framework an activity can be defined, or referred to, in two different ways: by its 'title', eg A, B and so on, or by the two nodes defining it. For example, in Figure 2 activity A is defined by node 1 and node 3, namely by arc(1,3). In this framework we let S(j) denote the set of nodes that are immediate successors of node j and P(j) the set of nodes that are immediate predecessors of node j. For example, in the case of Figure 2 we have S(1)={1,3}, S(2)={3}, S(3)={4,5}, S(4)={5} and S(6)={}. We also let d(i,j) denote the duration of the activity represented by arc(i,j) and assume that the nodes are represented by the labels {1,2,...,n}. Since we assume that the nodes are arranged in increasing order, this means then that node 1 is the (unique) start node and node n is the (unique) terminal node.

It is important to stress that the nodes of the network are not explicitly defined by the project table nor do they represent any 'real' constructs other than 'events' representing the completion of groups of activities. For example, in Figure 2 node 5 represents the event "activity C and activity E have been completed". It is not clear at all, however, what is the significance of this particular event. Why are we interested in this event, but not say in the event "activity C and activity D have been completed"? The point is that there is no explicit reference to these events in the project table representing the project. In any case, we refer to the nodes of the AoA network as events.

The CPM formalism based on AoA networks is described in Appendix B.

6. What is wrong then with AoA?

There is nothing fundamentally wrong with the AoA paradigm itself. This is not the issue. The issue is that the traditional implementation of the AoA paradigm - the one deployed in many introductory OR/MS textbooks and the one we outlined in Appendix B - is afflicted with a number of weaknesses, some more serious than others. So before we discuss some of these weaknesses let us first clarify the distinction we make here between the AoA paradigm itself and its traditional implementation in the OR/MS literature.

The basic feature of the AoA paradigm is the deployment of project networks whose arcs represent both the activities and the precedence relations between them. It is important to observe that this basic idea can be implemented in various ways and that the implementation universally adopted in the OR/MS literature is based on the Traditional Modelling Rules (Kelley, 1961) that we discussed above.

In view of this it is important to distinguish between weaknesses of the basic AoA paradigm itself and weaknesses of the Traditional Modelling Rules adopted in the OR/MS literature for the implementation of the AoA paradigm. Furthermore, it is also important to note that in our discussion the AoA paradigm is assessed in its role as a framework for teaching the CPM.

With this in mind let us now briefly examine four weaknesses afflicting the traditional implementation of AoA in the OR/MS literature.

• Need to draw a network:
  For some strange reason the OR/MS literature gives the impression that drawing a project network is an essential ingredient of the CPM. This is very unfortunate. As we showed above (Module 1), the CPM can be applied directly to the data provided by a project table.

  Of course, drawing a project network can be a very useful thing to do in OR/MS courseware. But it is also very important to inform the users of such courseware that this is not an essential ingredient of the method itself.

  It should be noted that since the same project can often be represented by more than one AoA network, the question arises: which AoA representation is best? This is a difficult question. If we simplify it and assume that the less dummy activities we have the better is the representation, then the question becomes: how do we build an AoA network with the minimum number of dummy activities?

  This has been the subject of an extensive research effort. Unfortunately, this problem is an NP-hard problem (Demeulemeester and Herroelen, 2002). What this tells us is that in general the construction of good AoA networks might not be an easy task. In fact, just the construction of a good AoA network might be computationally more demanding than solving a project problem via the AoN paradigm.

  Observe that the need to draw a network (or more specifically identify the nodes of the AoA network) is a weakness of the basic AoA paradigm itself. As we shall see below, the difficulties caused by dummy activities are due to the Traditional Rules.

• Need to introduce an exogenous construct:
  To apply the AoA paradigm it is necessary to introduce (out of nowhere) the notion "event" and this exogenous construct plays a central role in the exposition of the method under the AoA paradigm. Since this notion is not an essential ingredient of the CPM itself, its inclusion as a central ingredient of AoA should be regarded as a serious weakness of the AoA framework itself, not merely its implementation. We note in passing that within this framework textbooks normally compute the early and late times of the "events", rather than the early and late start times of the activities of the project.

• Need to deal with dummy activities:
  My extensive experience in this area indicates in no uncertain terms that many students experience great difficulties coping with dummy activities. Since these objects are not essential for understanding the CPM itself, it is not clear what is gained, if anything, by subjecting students to this modelling hurdle. It is not surprising therefore that in some textbooks (eg Markland and Sweigart, 1987) the discussion on dummy activities is very limited, amounting to no more than "... a dummy activity is used to ensure that the proper activity relationships are depicted by the network. Dummy activities have no duration or cost ...".

  Unfortunately, it seems that many courseware developers underestimate the difficulties caused by the introduction of dummy activities. Indeed, as the next point indicates, dummy activities are unfriendly objects and should be treated as such by courseware developers, students, and the general public alike. It may even be argued that, pedagogically speaking, it is not a good idea to refer to these activities as dummy within the AoA paradigm.

  For this reason it is important to note that the need for dummy activities is not dictated by the AoA paradigm itself, but rather by the Traditional Rules associated with it. As shown in Appendix D, it is easy to implement the AoA paradigm without deploying dummy activities simply by using a different set of modelling rules.

• Wrong formula:
  It has been known for a long time (eg. White et al, 1969, Elmaghraby and Kamburowski, 1990, Demeulemeester and Herroelen, 2002, Zhao and Tseng, 2003) that the common formula (22) used in many OR/MS textbooks to compute free floats is faulty in that under certain conditions it yields wrong values for the free floats of some activities. Yet, most general introductory OR/MS textbooks dealing with the CPM still use it and do not warn the readers about the bug afflicting it.

The following simple example illustrates the bug in the formula.

Example 2

Consider the project specified in Table 3. Using two dummy activities (X and Y) we draw the project network depicted in Figure 3(a). The AoN network for this project is depicted in Figure 3(b).

Figure 3(a)

Table 3 Activity Immediate Predecessors Duration (days) A --- 8 B --- 6 C --- 9 D A,B 2 E B,C 1

Figure 3(b)

Table 4 displays the values of ET(j), LT(j), TF(j) and FF(j) computed according to the traditional AoA based formulas:

Observe that the free floats of the two dummy activities X and Y are both strictly positive. It is also clear, by inspection, that the free float of activity B is equal to 2. But if we use (22) to compute the free float of activity B we obtain FF(B) = FF(1,2) = 0. This does not make sense - in fact for all practical purposes it is plainly wrong.

For the benefit of readers interested in this aspect of the AoA vs AoN dilemma, we provide in Appendix C an educationally oriented treatment of this bug.

In summary then, the traditional AoA paradigm that has been dominating OR/MS textbooks for decades is not very student friendly and the rationale for its deployment in OR/MS courseware should therefore be re-examined. Needless to say, this may take some time, but the sooner we start the re-evaluation process the better. The bug in the AoA free float should of course be fixed immediately and this would hopefully encourage courseware developers to re-consider their commitment to and support of the traditional implementation of AoA, and AoA itself.

7. Discussion

The CPM is an important practical OR/MS tool and this is naturally reflected in its coverage by many introductory OR/MS textbooks (eg. Daellenbach et. al., 1983, Markland and Sweigart, 1987, Shogan, 1988, Hillier and Lieberman, 1995, Taha, 1997, Winston, 2004). However, for obvious reasons this coverage is limited in both scope and depth compared to the treatment given to the topic in textbooks dedicated to project planning and scheduling (eg. Weist and Levy, 1977, Elmaghraby, 1977, Parker, 1995, Gray and Larson, 2002).

Given this fact of life, it is important to provide student-friendly CPM courseware for introductory OR/MS courses. The choice between AoA and AoN is definitely an issue that the developers and users of such courseware should consider. Hence the AoA vs AoN dilemma is real and important.

The advantages of AoN over AoA are well known in the OR/MS folklore. For example, Shogan (1988) notes the following in justification for the use of the AoN format in his texbook:

Similarly, in the Encyclopedia of Operations Research and Management Science, Rand (1996) notes the following :

The feature summary of a project management book (Gray and Larson, 2002) states that:

In a technical report on project management software by Leisham and Smith (2000) for the USA Air Force we find the following comparison:

Indeed, Microsoft Project - apparently the currently most popular project management software - deploys the AoN format, and so are other commercial project management software packages (see details in Leisham and Smith (2000) and the web site of Project Management Institute).

So one cannot help asking why on earth introductory OR/MS textbooks are still so strongly dominated by the AoA paradigm!?

It looks like this state of affairs is the result of two things, namely the conventions adopted in the early days of the development of the CPM and reluctance to change. Since the latter is a common, universal human trait, we shall not dwell on it. Regarding the early days, suffice it to say that there was a natural tendency then (early 1960s) to develop paradigms similar to those used at the time for the modelling and analysis of network flow problems in general and shortest path problems in particular. As we all know, in the context of these kinds of problems arcs usually represent "activities". So it is not at all surprising that at the very early days of the CPM it was very tempting to deploy the AoA paradigm.

Indeed, Kelley (1961) notes the following:

The interesting thing is that the founders of the CPM were well aware of the fact that from a purely graph theoretic point of view the choice of the AoA paradigm was not natural. For example, Kelley (1961) advises us the following:

The Founders were also aware of the complications caused by the need to deal with dummy activities. In fact, one of the roles of the Traditional Modelling Rules was precisely to assist analysts manage the number of dummy variables required by the AoA network (Kelley, 1961).

Given this, it is rather surprising and somewhat disappointing that Kelley's (1961) exposition does not provide even one single argument in support of AoA over AoN, or at least an explanation why - given the complications caused by dummy activities - it is nevertheless worthwhile to use AoA networks rather than AoN networks.

The fact that over forty years later the traditional AoA paradigm still dominates introductory OR/MS textbooks should not be misinterpreted as a sign of satisfaction on the part of lecturers and students. Rather, as was already been pointed out above, it seems to reflect a reluctance to change.

So how do authors justify the use of AOA in their books?

This is an interesting question. Most authors do not bother to justify their choice. In fact, the author of this paper found only one instance where the choice of AOA is discussed and justified in some length. Here it is (Parker, 1995):

So at this stage we are advised that the AON format is much easier - to the point of being trivial - and in contrast the AOA format is more interesting. The argument proceed as follows (Parker, 1995):

In view of this, we are not at all surprised to read later on (Parker, 1995) that " ... Throughout the remainder of this chapter, and as a matter of convenience, we will consider all project networks to exist in AOA format ...". The formula given for the free float (Parker, 1995) is afflicted by the common FF-bug discussed in this paper.

In short, in this particular instance the choice of AoA is based on the fact that the construction of AoA networks is more difficult - indeed trickier - hence should be more interesting to students - than the construction of AoN networks. Some readers (including this author) might disagree with this rationale, but at least students are advised that AoA is trickier than AoN and that the latter is easy, if not plainly trivial.

So perhaps it might be appropriate to employ a mixed strategy for the AoA/AoN dilemma: use AoN in class and encourage motivated students who seek tricky adventures to deal with AoA, including the FF-bug, on their own.

Last but not least, it should be noted that irrespective of the pardigm used, drawing visually appealing project networks - for that matter graphs in general - is not a simple task (Di Battista et al, 1998). This is one of the technical issues that project management software developers have to deal with

8. Scope

Throughout the discussion we alluded to the fact that AoA dominates the scene as far as introductory OR/MS textbooks are concerned. But how wide spread is the use of AoA in this environment?

The following list consists of all the introductory OR/MS textbooks at the various libraries on the campus of the University of Melbourne that are currently (August 10, 2004) accessible to the author of this paper.

As can be seen, most of the books indeed deploy the AoA paradigm. In view of the mission of our discussion, it is encouraging to observe that the authors of two books switched from AoA to AoN!

Be it as it may, one bright light on the horizon is a new breed of OR/MS oriented CPM courseware, especially those providing user-friendly computational modules or even modelling environments (eg spreadsheets). Since it is much easier to develop user-friendly software for the AoN paradigm, it is not surprising that these coursewares (eg. Seal, 2001, Ragsdale, 2003) adopt AoN rather than the traditional and well established AoA . This point is eloquently explained by Edwards and Finaly (1997):

So hopefully the fact that the new wave of spreadsheet-based OR/MS textbooks (eg Edwards and Finaly, 1997, Ragsdale, 2004) is dominated by AoN will inspire authors of "conventional" OR/MS textbooks to switch to this format. Indeed, it may well be that for this reason the percentage of AoN-based books in the reader's libraries is much higher than the rather low percentage exhibited in List 1.

It is somewhat ironic though that we begin to experience this new trend more than forty years after the publication of the first paper on AoN whose title, by the way, is A noncomputer approach to the critical path method for the construction industry (Fondahl, 1961).

Lecturers who are actively involved in teaching the CPM and are still deploying the AoA paradigm should re-examine their choice and in any case should inform their students on the obvious advantages of AoN. Needless to say, they should immediately fix the common FF bug in their courseware. And those of us who prefer AoN on AoA should put pressure on CPM courseware developers to join the club.

Remark
CPM courseware developers should also be encouraged to make explicit the dynamic programming content of their courseware. Indeed, it is amazing that so many OR/MS textbooks do not advise their readers that the traditional CPM formulas for the early and late times (eg.(16)-(18)) are in fact typical dynamic programming functional equations, hence the core of the CPM as a whole is an application of dynamic programming. This is particularly odd in the case of textbooks covering both dynamic programming and CPM where cross references between the dynamic programming and CPM discussions seem to be highly desirable.

9.Conclusions

There are strong evidence that the AoN paradigm is much superior to AoA, yet the OR/MS literature (especially general introductory textbooks), is still dominated by AoA. The only rational explanation for this state of affairs is momentum and vested interest. These are serious considerations that should not be dismissed lightly.

However, it will be a mistake to let them dictate our choice in the long run. It is time to change and the sooner the better.

This educationally oriented discussion will hopefully set things in motion in that it will convince AoA aficionados in the OR/MS academic community that from a pedagogical point of view their favourite CPM paradigm is afflicted with a number of weaknesses. This in turn should go along way towards recognizing the obvious advantages of AoN on AoA.

As was indicated at the outset, this paper is an important element in the campaign that the author launched to encourage the development of AoA-free CPM courseware. He now takes the liberty of inviting you, dear reader, to become actively involved in this initiative!

Finally, what is obviously implied by the discussion as a whole, namely that there seems to be no OR/MS textbooks where the advantages of AoA over AoN are discussed or just merely alluded to, should be made explicit. If there are such advantages, then they should be spelled out clearly and not be hidden from the public. Indeed, in view of what emerges from this discussion, it is the responsibility of CPM courseware developers using the AoA paradigm to justify their choice.

10. Acknowledgment

I wish to thank the Editor, an Associate Editor and two referees for their constructive comments and suggestions.

References

Anderson, D.R., Sweeney, D.J. and T.A. Williams, (2003), An Introduction to Management Science: a quantitative approach to decision making, 10th Edition, South-Western, OH.

Bellman, R. (1957), Dynamic Programming, Princeton University Press, NJ.

Daellenbach, H.G., George, J.A. and D.C. McNickle, (1983), Introduction to Operations Research Techniques, 2nd Edition, Allyn and Bacon, Boston.

Demeulemeester, E.L. and W.S. Herroelen, (2002), Project Scheduling A research Handbook, p. 21, 47, Kluwer, Boston.

Di Battista, G., Eades, P., Tamassia R. and I. Tollis (1998), Graph drawing: algorithms for the visualization of graphs, Prentice Hall, Englewood Cliffs, NJ.

Edwards, J.S. and P.N. Finlay, (1997), Decision making with Computers: the spreadsheet and beyond, p. 226, Pitman, London.

Elmaghraby S.E. (1977), Activity Networks: Project Planning and Control by Network Models, Wiley, NY.

Elmaghraby S.E. (1995), "Activity Nets: A Guided Tour through Some Recent Developments," European Journal of Operational Research, Vol. 82, pp. 383-408.

Elmaghraby S.E. and J. Kamburowski, (1990), "On project representation and activity floats," Arabian Journal for Science and Engineering, Vol. 15, pp. 627-637.

Evans, J.R. and E. Minieka, (1992), Optimization Algorithms for Networks and Graphs, Marcel Dekker, NY.

Feature Summary:

Fondahl, J.W. (1961), "A noncomputer approach to the critical path method for the construction industry," Department of Civil Engineering, Stanford University, Stanford, CA.

Gray C.L. and E.W. Larson, (2002), Project Management: The Managerial Process, 2nd Edition, McGraw-Hill, NY.

Hillier, F.S. and G.J. Lieberman, (1995), Introduction to Operations Research, 6th Edition, McGraw-Hill, NY.

Hillier, F.S. and G.J. Lieberman, (2004), Introduction to Operations Research, 8th Edition, McGraw-Hill, NY.

Kelley, J.E. (1961), "Critical path planning and scheduling: mathematical basis," Operations Research, Vol. 9, pp. 296-320.

Leishman, T.R. and L. Smith, (2000), "Software Project Management Technology Report," STSC, p. 32, USA Air Force.

Markland, R.E. and J.R. Sweigart, (1987), Quantitative Methods: Applications to Managerial Decision Making, p. 439, John Wiley, NY.

Microsoft Project: (last accessed on March 13, 2005).

Parker, R.G. (1995), Deterministic Scheduling Theory, pp. 204-211, Chapman & Hall, London.

Project Management Institute: (last accessed on March 13, 2005).

Ragsdale, C.T. (2003), "A New Approach to Implementing Project Networks in Spreadsheets," INFORMS Transactions on Education, Vol. 3, No 3, (last accessed on March 13, 2005).

Ragsdale, C.T. (2004), Spreadsheet Modeling and Decision Analysis, 4th Edition, South-Western, OH.

Rand, G. (1996), "Network planning", pp. 437-441 in Encyclopedia of Operations Research and Management Science, edited by Gass, S.I. and Harris, C.M., Kluwer, Boston, Mass.

Seal, K.C. (2001), "A Generalized PERT/CPM Implementation in A Spreadsheet," INFORMS Transactions on Education, Vol. 2, No. 1, (last accessed on March 13, 2005).

Shogan, A.W. (1988), Management Science, Prentice hall, Englewood Cliffs, pp. 475-6, NJ.

Taha, A.H. (1997), Operations Research, 6th Edition, Prentice Hall, NJ.

Thomas, W. (1969), "Four float measures for critical path scheduling," Journal of Industrial Engineering, Vol. 10, pp. 19-23.

Weist, J. and F. Levy, (1977), A management science guide to PERT/CPM, 2nd Edition, Prentice Hall, Englewood Cliffs, NJ.

White, D., Donaldson, W. and N. Lawrie, (1969), Operational Research Techniques, Vol. 1, p. 98, Business Books Limited, London.

Winston, W.L. (2004), Operations Research : Applications and Algorithms, 4th Edition, Example 6, p. 433, Brooks/Coles, CA.

Zhao, T. and C-L. Tseng, (2003), "A note on activity floats in activity-on-arrow networks," Journal of the Operational Research Society, Vol. 54, pp. 1296-1299.

To reference this paper, please use:  Sniedovich, M. (2005), "Towards an AoA-Free Courseware for the Critical Path Method," INFORMS Transactions on Education, Vol. 5, No 2,  http://ite.pubs.informs.org/Vol5No2/Sniedovich/

Terminology and Basic Mathematical
Idiom of CPM

The mathematical framework commonly deployed in OR/MS textbooks to describe the basic ideas of CPM involves the following constructs:

The method commonly used to identify the critical path of a project is dynamic programming (Bellman, 1957). The details are as follows

With each activity we associate the following two fundamental properties:

Definition 1

The following is an immediate consequence of the definitions of EST, LST and T:

Lemma 1

It is convenient to assume that the elements of J are ordered lexicographically so that the immediate successors of activity j are lexicographically greater than j. Note that the activities in Table 1 satisfy this condition. This is a minor technicality because precedence relations of a project cannot be cyclic, hence it is always possible to arrange the activities in a lexicographic order that is consistent with the postulated precedence relations. It is also convenient to assume that the time origin is equal to zero, namely that the starting time of the activity to be implemented first is equal to zero.

It is now not difficult to show that EST and LST satisfy the following dynamic programming functional equations:

Lemma 2

The computational procedure is then as follows:

1. Set EST[j] = 0 for all j in Sources.
2. Compute the EST[j] values for the other activities using (6) lexicographically.
3. Compute T according to (3).
4. Set LST[j] = T -d(j) for all j in Terminals.
5. Compute the LST[j] values for the other activities using (7) lexicographically (in reverse order).

In this context a variety of floats can be defined (Thomas, 1969, Rand, 1996, Demeulemeester and Herroelen, 2002). We shall consider only the two most popular ones:

Definition 2

The reference to the 'project as a whole' in (9) is required so that this definition will also apply to terminal activities, that is activities that do not have immediate successors.

This obviously leads to

Definition 3

A critical activity is an activity whose total float is equal to zero. That is, j in J is a critical activity if and only if TF(j) = LST(j) - EST(j) = 0, or equivalently if LST(j) = EST(j).

Once the early and late start times are know for all the activities, the computation of the floats - hence the identification of the critical activities - is a straightforward matter:

Lemma 3

Table 2 depicts the results generated by the above recipe for the project described in Example 1.

AoA formalism of CPM

The two basic concepts characterising the events of AoA networks:

Definition 4

Lemma 4

In short, we compute E(j) for j=1,...,n (in this order) and then LT(j) for j=n,...,1 (in this order) according to (15)-(18).

Next, we consider the floats:

Definition 5

Lemma 5

Once we compute the total floats it is easy to identify the critical activities: by definition the critical activities are those activities whose total floats are equal to zero

Fixing the common Free-Float Bug in AoA
(An Educationally Oriented Treatment)

The objective of this appendix is to explain the flaw in the common formula for the free floats associated with the AoA framework and to explain how the bug can be fixed. The discussion is educationally oriented.

The following simple example illustrates the basic issue on the agenda:

Example 3

Consider the project represented by Table 5. The precedence relations are described in Figure 4. Since Rule 5 is violated, a dummy activity - called X - is introduced. This dummy activity can be incorporated in the network in two different ways, as shown in Figure 5 and Figure 6. The respective floats, computed in accordance with (21)-(22) are given in Table 6 and Table 7, respectively.

Figure 4 Table 5   a     P(a)     d(a)   A -- 9 B -- 8 C A,B 3 (project table)

Figure 5 Table 6   a     TF(a)     FF(a)   A 0 0 B 1 1 C 0 0 X 0 0

Figure 6 Table 7   a     TF(a)     FF(a)   A 0 0 B 1 0 C 0 0 X 1 1

Clearly, something fishy is going on here: we obtain two different values for the free float of activity B. How can this happen? After all, the two networks describe the same project and therefore the free float of activity B should not depend on the network representation ?!?!?

We have two objectives then. The first is to clearly identify the source of the apparent bug afflicting the traditional AoA recipe for the free float. The second is to fix this bug. We shall refer to these two aspects of our analysis as cause and remedies.

C.1 Cause

We should not rush to blame (22) for yielding incorrect values for AoA free floats. In fact, it is not difficult at all to prove formally that (22) itself is perfectly correct. We leave this as a exercise for the interest reader. To identify the real cause of the bug we have to look deeper into AoA.

A close examination of the AoA framework leading to (22) reveals that the source of the bug is hidden in the definition of free float, namely in (20). More specifically, the culprit in this affair is the clause 'any subsequent activity' in (20) that does not clearly and explicitly exclude delays in dummy activities. In other words, if in the context of (20) we understand 'any subsequent activity' to mean 'any subsequent activity (real or dummy)' then (20) is a proper definition of free float and (22) is perfectly correct, though some time senseless. For example, it is crystal clear that if (20) does not allow delays in dummy activities, then the free float of activity B in Figure 3 is equal to zero - as computed by (22): indeed, any delay in the completion of activity B will clearly delay the commencement of both X and Y. The same is true about Figure 6: if (20) does not permit delays is dummy activities then clearly the free float of activity B is equal to 0.

However, since practically speaking we cannot care less about delays in dummy activities (as long as these delays do not cause delays in subsequent real activities), it is apparent that we have to modify the definition of free float to make it consistent with the special role that dummy activities play in the AoA model. Hence,

Definition 6

To define these floats more formally, let S'(i,j) denote the set of all nodes that are successors (not necessarily immediate successors) of the activity represented by arc(i,j), let NAD denote the set of all nodes whose out-arcs are not all dummy, and let AD denote the set of all nodes whose out-arcs are all dummy. It is convenient to let NAD include the terminal node, n. Thus, for example, in the case of Figure 3 we have NAD = {1,2,4,5}, AD = {3}, S'(1,2)={2,3,4,5}, S'(1,3) = S'(1,4)={5}, S'(2,3)={3,5}, S'(2,4) = {4,5}, S'(3,5)=S'(4,5)={5}.

Then the definition of FFD(i,j) can be restated as follows:

Note that in (24) the variable x represents a delay in the commencement of activity (i,j) that will not delay the commencement of any subsequent real activity. This is why events in AD are excluded on the right hand side of (24).

The following is an immediate consequence of this new definition:

Lemma 6

where

Observe that by definition k(i,j) denotes the node that is a successor of node j whose out-arcs are not all dummy and whose early start time is the smallest among all the successors of node j whose out-arcs are not all dummy. In Figure 5, Figure 6 and Figure 3 we have k(1,2) = 3. So in Figure 3 we have FFD(1,2) = ET(3) - ET(1) - d(1,2) = 8 - 0 - 6 = 2, and in Figure 6 we have FFD(1,2) = ET(3) - ET(1) - d(1,2) = 9 - 0 - 8 = 1.

Two questions naturally arise:

1. What is the relationship between FF(i,j) and FFD(i,j)?
2. How can we compute the value of k(i,j) in (25)? Or more generally, how do we efficiently compute the values of the correct free floats {FFD(i,j)}?

In connection with the latter, observe that node k(i,j) in (24) is a successor of activity (i,j), but not necessarily an immediate successor (which is node j). Thus, the recipe for computing FFD(i,j) should be expected to be much more involved than the recipe for computing FF(i,j).

The good news is that the bug afflicts only activities whose immediate successors are all dummy.

Lemma 7

This means that if the AoA project network is such that every non-terminal activity possesses at least one immediate successor that is a real activity, then clearly NAD includes all the nodes of the networks. In this case FFD(i,j) = FF(i,j) for all activities (i,j), hence the bug does not afflict this network.

Differently put: the bug afflicts only networks where at least one of the nodes has the property that all its out-arcs are dummy.

It is instructive to relate the values of FFD(i,j) and FF(i,j) for activities (i,j) such that j is in AD.

Lemma 8

where

recalling that S(j) denotes the set of nodes that are immediate successors of node j.

In words, the correct value of the free float of a problematic activity (FFD(i,j)) is equal to the 'incorrect' value of the free float (FF(i,j)) plus the smallest correct free float (r(j)) among the immediate successors of the activity. Recall that if (i,j) is a problematic activity (j is in AD), then by definition all the immediate successors of activity (i,j) are dummy. Clearly then, FFD(i,j) >= FF(i,j) for all activities. One of the implication of this is that the bug does not afflict the critical activities, observing that FFD(i,j) = FF(i,j) = TF(i,j) = 0 for all critical activities.

C.2 Remedies

There are various ways to fix the Free-Float Bug in the traditional AoA paradigm. Before we briefly discuss some of them, it is instructive to distinguish between two types of dummy activities, namely those associated with Rule 4 and those associated with Rule 5.

The reason for this is that it is very easy to disarm the dummy activities induced by Rule 5 at the outset, that is when the AoA network is drawn. For example, suppose that we insist that if more than one arc connects a given pair of nodes then the arc connecting these two nodes should represent the longest activity associated with this pair of nodes. According to this convention, we would draw the network represented by Figure 5 rather than the network represented by Figure 6. It is not difficult to show that this convention completely disarm the dummy activities induced by Rule 5.

Alternatively, we can apply the remedy proposed by White et al (1969): "... no activity should, if possible, be followed by dummies only ...". In the case of Rule 5 this means that dummy activities should precede the real activities inducing them. Thus, for example, in Figure 6 we should let the dummy activity (X) be presented by arc(1,2) and activity B by arc(2,3). It is not difficult to show that this convention completely disarm the dummy activities induced by Rule 5. Interestingly, most textbooks are doing it the other way around: real activities precede their dummies!

So the real challenge is to disarm the dummy activities induced by Rule 4, namely the dummy activities that are introduced to prevent replication of real activities. We now briefly discuss five remedies that can be used for this purpose. They also take care of the dummy activities induced by Rule 5.

Remedy # 1: Denial. As we explained above, there is nothing wrong with (22) itself. The traditional definition of free floats (20) does not make any distinction between real activities and dummy activities. Hence, we can interpret it to mean that the computation of the free float should insure that no subsequent activity - real or dummy - is delayed. If this is the case, then (22) is correct. So what is the fuss all about?

This argument is of course perfectly valid. However, it should be rejected on the spot because although legally speaking (22) is perfectly OK within the framework of (20), the definition of free float itself would then be fundamentally flawed in that it will be inconsistent with the notion "dummy". That is, subject to this interpretation, dummy activities are not dummy at all and it will be our responsibility to find out which one of the possible configurations of the dummy activities is valid for the project under consideration. This means that we have to develop a method for identifying the valid dummy configuration. Needless to say, this is not an attractive proposition.

In short, this remedy does not resolve the difficulty, it merely points out that (22) is consistent (20). Unfortunately, if we accept (20), we have a much more serious difficulty to deal with. We thus cannot accept this remedy.

Courseware developers who adopt this remedy should at least inform their customers about the implication of using (20) rather than (23) as the formal definition of free float (eg. see friendly advice at White at al, 1969).

Remedy # 2: Change the definitions of event times. In particular, change the definition of Early Event Time to account for the distinction between real and dummy activities. Using this approach Elmaghraby and Kamburowski (1990) developed a valid AoA model in the context of which (22) generates correct values for the free floats.

Pedagogically this is a very unattractive remedy, as it requires a major complication in the definition of early event times.

Remedy # 3: Change the formula for the free float. Keep the traditional definitions of Event Times intact, but change (22) so that it generates the correct values of the free float. This approach, proposed by Zhao and Tseng (2003), has the advantage of keeping the traditional AoA model, including the basic definitions of Event Times, intact. The proposed formula for the free float is

where

The computation is carried out in a 'backward' manner and can be incorporated in the computation of the late event times of the activities.

Note that this recipe is similar to (27)-(29) except that there we draw an explicit distinction between problematic and non-problematic activities and explicitly relate FFD(i,j) to FF(i,j).

Remedy # 4: Disallow the deployment of dummy activities. It should be stressed that dummy activities are not essential for the construction of AoA project networks. They have been traditionally used for this purpose due to the imposition of the Traditional Modelling Rules.

In view of the difficulties introduced by incorporating dummy activities into the AoA model it might be better to change the rules and disallow dummy activities. This will cause only slight changes in the traditional formulas for the event times and floats but will greatly simplified the construction of project networks from project tables.

As shown in Appendix D it is not difficult at all to implement such a Dummy-Free AoA paradigm.

Pedagogically (and perhaps practically) speaking, this approach has the disadvantage that it allows an arc to represent more than one activity. Actually, in some respects this can be regarded an advantage rather than a disadvantage!

Remedy # 5: Disallow the use of AoA. Use AoN instead. This seems to be the best fix!

Dummy-Free AoA Networks for the Critical Path Method
(Disclaimer)

The basic characteristic of the AoA paradigm is that the project's activities are represented as arcs on the project network. In view of the state of the literature, it should be stressed that this essential requirement does not imply that dummy activities are necessary for the construction of AoA networks. Indeed, as we show in this appendix, in the context of the critical path method it is a straightforward matter to construct AOA networks without the aid of dummy activities.

For this reason it is important to note that in the context of the CPM the need for dummy activities arises not due to the basic AoA methodology, but rather due to the Traditional Modelling Rules imposed on the construction of AoA networks. In particular, the two culprits are:

Rule 4: Each activity should be represented by exactly one arc.
Rule 5: Any two nodes can be connected by at most one arc.

So all we have to do to get rid of the need for dummy activities is abolish these two rules. Naturally, doing this will require some changes in the way we compute early and late times and floats. As we shall see below, these changes are not substantive in nature so for all practical purposes the removal of these two rules does not complicate the computational aspects of the CPM.

So suppose that we ignore these two traditional rules. This means that now you are welcome to replicate any activity as many times you wish and you are also allowed to connect a given pair of nodes with as many arcs you wish. Naturally, the precedence relations are still in effect so whatever you do is still subject to the precedence constraints implied by these relations.

To cope with this new modelling environment resulting from the abolition of the two traditional rules we have to make sure that we are able to cope with the ambiguities that these two rules were designed to prevent. This suggests the introduction of the following two obvious conventions:

• Every activity must have a distinct label.
• All replicates of the same activity must emanate from the same node.

Since in this new modelling framework activities can be replicated, to distinguish between an original activity and its copies it is advisable not to use the label of the original activity as a label for any of its copies, but rather to generate labels that are all distinct from the label of the original activity. Thus, for example, if we wish to replicate activity A three times, we shall label the copies A1, A2, A3 and reserve the label A to represent the original activity.

This is good practice, because it serves as a reminder that after we complete the analysis of the replicates we still have to compute the floats of the original activities.

Example 4

Consider the project described in Table 8. Using the traditional AoA rules, we have to introduce three dummy activities as shown in Figure 7. Note that X and Y are used because we are not allowed to replicate activity B and Z is used because we are not allowed to have more than one arc between a pair of nodes. Figure 8 represents the same project, but according to the proposed new conventions. Note that since activity B is replicated twice, we label its copies B1 and B2.

Table 8 Activity Immediate Predecessors Duration (days) A --- 8 B --- 6 C --- 9 D A,B 1 E A,B 3 F B,C 1

Figure 7

So as we can clearly see, project networks generated by the proposed new conventions will typically have multiple arcs connecting some of the nodes. We can no longer therefore represent activities by pairs of nodes, as this representation is ambiguous. For example, in Figure 8 arc(1,2) represents two activities, namely A and B1. To overcome this minor obstacle, let AA(i,j) denote the set of all the activities represented by arc(i,j). Thus, in the case of Figure 8 we have AA(1,2)={A,B1}, AA(1,3)={B2,C}, AA(2,4)={D,E}, AA(3,4)={F}. Thus, the set of all the activities associated with the project under consideration is J = {A,B1,B2,C,D,E,F}. Note that activity B is not included in this set.

The recipes for the event times are as follows:

Lemma 9