13. Network Models – Operations Research, 2nd Edition

13

Network Models

13.1 INTRODUCTION

Critical Path Method (CPM) was developed by Morgan R. Walker for the E.I. DuPont de Nemours Company to solve project scheduling problems. It was later extended and enhanced by Mauchly Associates. During the same time, a team of engineers working on the Polar’s Missile programme of the US Navy developed PERT.

A project is defined as a combination of interrelated activities all of which must be executed in a certain order to achieve a set goal. In a large and complex project involving a number of interrelated activities requiring men, machines and material, it is impossible for the management to make and execute an optimum schedule just by intution, based on organisational capabilities and work experience. A systematic scientific has become a necessity. So, a number of methods applying network scheduling techniques have been developed. PERT and CPM are two of the many network techniques which are widely used for planning, scheduling and controlling large, complex projects.

These two methods are essentially network-oriented techniques using the same principle. PERT and CPM are basically time-oriented methods in the sense that they both lead to the determination of a time schedule of a project. The significant difference between two approaches is that the time estimates for the different activities in CPM are assumed to be deterministic while in PERT these are described probabilistically. Nowadays, PERT and CPM comprise one technique and the differences, if any, are only historical. Hence, these techniques are referred to as Project Scheduling techniques.

13.1.1 Phases of Project Management

The three main managerial functions for any project are:

  1. Planning
  2. Scheduling
  3. Control.

Planning: This phase involves listing of tasks or jobs (work breakdown structure or (WBS)) that must be performed to complete a project under consideration. In this phase, men, machines and material required for the project in addition to the estimates of costs and duration of various activities of the project are also determined.

Scheduling: This phase involves the laying out of actual activities of the projects in a logical sequence of time in which they have to be performed. Also, start and finish times for each activity, critical path on which activities require special attention and slack (or) float for the non-critical paths are determined. Control: This consists of reviewing the progress of the project and whether the actual performance is according to the planned schedule and finding the reasons for the difference, if any, between the schedule and the performance. The basic aspect of control is to analyse and correct this difference by taking remedial action wherever possible.

PERT and CPM are useful for these functions.

13.1.2 Differences Between PERT and CPM

PERT

  1. Since PERT was developed in connection with an R&D work, therefore, it had to cope with the uncertainties which are associated with such activities. In PERT, the total project is regarded as a random variable, and therefore, associated probabilities are calculated so as to characterise it.
  2. It is an event-oriented network because in the analysis of network, emphasis is given to important stages of completion of task rather than to the activities required to be performed to reach a particular event or task.
  3. PERT is normally used for projects involving activities of non-repetitive nature in which time estimates are uncertain.
  4. It helps in pinpointing critical areas in a project so that necessary adjustments can be made to meet the scheduled completion date of the project.

CPM

  1. Since CPM was developed in connection with a construction project which consisted of routine tasks whose resource requirements and duration were known with certainty, it is basically deterministic.
  2. CPM is suitable for establishing a trade-off for optimum balancing between schedule time and cost of the project.
  3. CPM is used for projects involving activities of a repetitive nature.
13.2 NETWORK CONSTRUCTION

13.2.1 Some Basic Definitions

Activity: An activity is a task or an item of work to be done in a project. It consumes resources like time, money and labour.

An activity is represented by an arrow with a node at the beginning and a node at the end indicating the start and termination (finish) of the activity. Nodes are denoted by circles. Since this is a logical diagram, length or shape has no meaning. The direction indicates the progress of the activity. Initial and terminal nodes are denoted by ij(j > i), respectively. For example, if A is the activity whose initial node is i and the terminal node is j, then it is denoted by

FIGURE 13.1

The diagram in which arrow represents an activity is called an arrow diagram.

Predecessor activity: Activities that must be completed immediately prior to the start of another activity are called predecessor activities.

FIGURE 13.2

Here, A and B are predecessors of C and these are denoted by A < C; B < C.

Successor activity: Activities that cannot be started until one or more of other activities are completed, but immediately succeed them are called successor activities. In Fig. 13.2, C is a successor of A and B. This denoted by C > A and C > B.

Concurrent or parallel activities: Activities which can be accomplished concurrently are known as concurrent activities. It may be noted that an activity can be predecessor or a successor to an event or it may be concurrent with one or more of the other activities.

FIGURE 13.3

In Fig. 13.3, A and B are parallel activities; C and D are parallel activities.

Dummy activity: An activity which does not consume any kind of resource but merely serves the purpose of indicating the predecessor or successor relationship clearly in network is called as a dummy activity.

Let A and B be the predecessors of C and B is the predecessor of D. This will be denoted by

FIGURE 13.4

Activities which have no predecessors are called start activities of the project. All the start activities can be made to the same initial node. Activities which have no successors are called terminal activities of the project. These can be made to have the same terminal node (end node) of the project.

Events: Events of a network represent project milestones, such as the start or the completion of an activity (task) or activities, They occur at particular instants of time at which some specific part of the project has been or is to be achieved. Events are usually represents by a circle O in a network, also called a node or connector.

Events can be further classified into the following three categories:

Merge event: When more than one activity joins an event, is known as it merge event.

Example

FIGURE 13.5 Merge event

Burst event: When more than one activity leaves an event, such an event is known as a burst event.

Example

FIGURE 13.6 Burst event

Merge and burst event: An activity may be a merge and burst event at the same time; as with respect to some activities it can be a merge event and with respect to some other activities it may be a burst event.

Example

FIGURE 13.7 Merge and burst event

Network: An arrow diagram denoting all the activities of a project taking into account the technological sequence of the activities is called a project network. It is represented by activities on an arrow diagram or simply an arrow diagram.

Remark: There is another method of depicting a project network—by representing activities on nodes. This is called an AON diagram. To avoid confusion we use only activity on arrow diagrams throughout the text.

13.2.2 Rules of Network Construction

1. There must be no loops. (That is, a loop is not possible in any real project network.)

Example

FIGURE 13.8 Loop in a network

In the above network the activities, A, B, and C forms a loop which is not allowed.

2. Each activity is represented by one and only one arrow in a network.

3. In order to ensure correct precedence relationship in an arrow diagram, the following questions must be asked whenever addition is made to the network.

  1. What activity must be completed immediately before this activity starts?
  2. What activity follows this?
  3. What activities must occur simultaneously with this activity?

4. The logical sequence (or interrelationship) between activities must follow the following rules:

  1. An event cannot occur until all the incoming activities into it have been completed.
  2. An activity cannot start unless all the preceding activities on which it depends have been completed.
  3. Though dummy activities do not consume either any resource or time, it still has to follow the rules 4(i) and 4(ii).

Some Important Tips for Drawing a Good Network

  1. Avoids crossing of arrows.
  2. Use straight arrows.
  3. Do not attempt to represent the duration of an activity by its arrow length.
  4. Use arrows from left to right (or right to left). Avoid mixing two directions; vertical and horizontal arrows may be used if necessary.
  5. Use dummies freely in rough draft but final network should not have any redundant dummies.
  6. The network has only one entry point, called the start event, and one point of emergence, called the end event.

Errors in a Network

  1. Looping
  2. Dangling: To disconnect an activity before the completion of all activities in a network diagram is known as dangling.

    Example

    FIGURE 13.9

  3. Redundancy: Unnecessarily inserting a dummy activity in a network logic is known as the error of redundancy.

13.2.3 Fulkerson’s Rule (ij rule) of Numbering Events

  1. Number the start node which has no predecessor activity as 1.
  2. Delete all the activities emanating from this node 1.
  3. Number all the resulting start nodes without any predecessor as 2, 3, …
  4. Delete all the activities originating from the start nodes without any predecessor next to the last number in step (3).
  5. Number all the resulting new start nodes without any predecessor next to the last number in step (3).
  6. Repeat the process until the terminal node without any successor activity is reached and number this terminal node suitably.

Example 1

Draw a network for the following project and number the events according to Fulkerson’s rule.

  • A is the start event and k is the end event.
  • J is the successor event to F.
  • C and D are successor events to B.
  • D is the preceding event to G.
  • E and F occur after event C.
  • E precedes F.
  • C restrains the occurrence of G and G precedes H.
  • H precedes J.
  • F restrains the occurrence of H.
  • K succeeds event J.

Solution:

FIGURE 13.10

Example 2

Consider a project with the following WBS for building a site preparation. Determine the precedence relationship, draw the network and number the events.

  • Clear the site
  • Survey and layout
  • Rough grade
  • Exavacate the sewer
  • Exavacate for electrical manholes
  • Instal sewer and backfill
  • Instal electrical manhones
  • Construct boundary wall.

Solution: Looking at the list of activities we can fix the following precedence order:

B succeeds A and C succeeds B, that is, B > A, C > B.

D and E can start together after the completion of C, that is, D, E > C.

F will follow D and G will follow E, that is, F > D, G > 1.

H can start after C, that is, H > C.

Thus the precedence relationships are:

B > A; C > B; D, E, H > C; F > D; and G > E.

The project can be represented in the form of a network as shown below:

TABLE 13.11

Example 3

Draw a network for jobbing production and indicate the critical path from the following:

Solution: The network of the given situation is as follows:

FIGURE 13.12

Example 4

Draw an event-oriented network for the following data:

Solution:

FIGURE 13.13

13.3 CRITICAL PATH METHOD (CPM)

After the construction of a project’s network its time analysis becomes essential for planning various activities of the project. The duration of individual activities may be uniquely determined (in case of CPM) or may involve three time estimates (in case of PERT) out of which the expected duration of an activity is computed.

The main objective of time analysis is to prepare the planning schedule of a project. The planning schedule should include the following factors:

  • Total completion time for the project.
  • Earliest time when each activity can start.
  • Latest time when each activity can be started without delaying the total project.
  • Float for each activity, that is, the amount of time by which the completion of an activity can be delayed without delaying the total project completion.
  • Identification of critical activities and critical path.

Notations: We shall use the following notations for basic scheduling computations:

(ij) or ij = Activity (i, j) with tail event i and head event j.
TE or Ei = Earliest occurrence time of event i
TL or Lj = Latest allowable occurrence time of event j.
Dij = Estimated completion time (duration of activity (i, j))
ESij (or) (ES)ij = Earliest starting time of activity (i, j)
EFij (or) (EF)ij = Earliest finish time of activity (i, j)
LSij (or) (LS)ij = Latest starting time of activity (i, j)
LFij (or) (LF)ij = Latest finishing time of activity (i, j)

For calculating the above mentioned times, we shall discuss two methods, namely forward pass computation and backward pass computation.

13.3.1 Forward Pass Computation (for Earliest Event Time)

In this method, calculations begin from the initial event, proceed through the network visiting events in an increasing order of event number and end at the final event. At each event we calculate earliest occurrence event time (TE or Ei) and earliest start and finish time for each activity that begins at that event.

When calculations end at the final event, its earliest occurrence time gives the earliest possible completion time of the entire project.

  • Set the earliest occurrence time of initial event as zero
  • The earliest starting time of activity (i, j) is the earliest event of the tail end event, that is, (ES)ij = Ei.
  • The earliest finish time of activity (i, j) is the earliest starting + the activity duration. That is,

    (EF)ij = (ES)ij + Dij

    or,

    (EF)ij = Ei + Dij

  • The earliest event time for event j is the maximum of the earliest finish times of all activities ending into that event. That is,

13.3.2 Backward Pass Computation (for Latest Allowable Time)

In this method calculations begin from the final event, proceed through the network visiting events in the decreasing order of event numbers and end at the initial node. At each event, we calculate the latest occurrence event time TL or Lj for the corresponding event, latest finish and start time for each activity that is terminating at the event, such that the earliest finish time for the project remains the same.

  • For ending event assume E = L. Remember that all Es have been computed by forward pass computation.
  • The latest finish time for activity (i, j) is equal to the latest event time of event j, (Lf)ij = Lj
  • The latest starting time activity (i, j) = the latest completion time of (i, j)–the activity time (duration)

    or,

    (LS)ij = (Lf)ijDij

    or,

    (LS)ij = LjDij

  • Latest event time for event i is the minimum of the latest start time of all activities originating from that event.

    That is,

13.3.3 Computation of Float and Slack Time

After calculating the earliest and latest occurrence time the next step is to calculate the floats as defined below:

Total float (TF or (TF)ij of an activity is defined as the difference between the latest finish and the earliest finish of the activity or the difference between the latest start and the earliest start of the activity.

i.e.

TF = (TF)ij = (LS)ij - (ES)ij

or,

(TF)ij = (LF)ij - (EF)ij

This is the most important type of float because it concerns with the overall project duration.

Total float of an activity is the amount of time by which that particular activity may be delayed without affecting the duration of the project.

Free Float (FF or (FF)ij) of an activity is that portion of the total float which can used for rescheduling that activity without affecting the succeeding activity.

That is,

FF = FFij = Total float of ij − (TLTE) of the event j

where,

TL = Latest occurrence Time
TE = Earliest occurrence Time

Independence Float (IF or IFij) of an activity is the amount of time by which an activity can be rescheduled without affecting the preceding or succeeding activities of that activity.

i.e.

IF = IFij = Free float of ij - (TLTE) of the event i.

The negative value of independent float is considered as zero.

Remarks:

  1. The relation between the three floats is given by Independent float ≤ Free float ≤ Total float.
  2. The concept of floats is useful to the management in representing under-utilised resources and flexibility of the schedule and the extent to which the resources will be utilised on different activities.
  3. The floats can be used for redeployment of resources to level the same or to reduce project duration. However, one should bear in mind that whenever the float in a particular activity is utilised, the float of not only that activity but that of other activities would also change.

Event slacks: For any given event, event slack is defined as the difference between the latest event and earliest event times.

For a given activity i–j,

Head event slack = LjEj
Tail event slack = LiEi

The floats can be represented in terms of head and tail event slacks also.

Total float = LjEiDij
Free float = EjEi–Dij = (LjEiDij)–(LjEj)
= Total float–Head event slack

Independent float = EjLiDij
= (EjEiDij)–(LiEi)
= Free float–Tail event slack.

Time Scale Representation of Floats and Slacks

The various floats and slacks for an activity ij can be represented on a time scale as follows:

FIGURE 13.14

Conclusions Drawn from Total Values

From the value of a total float we can draw the following conclusion:

If the total float is positive then it may indicate that the resources for the activity are more than adequate. If the total float of an activity is zero it may indicate that the resources are just adequate for that activity. If the total float is negative, it may indicate that the resources for the activity are inadequate.

13.3.4 Critical Path

Critical event: Since the slack of an event is the difference between the latest and earliest event times, that is, slack (i) = LiEi, the events with zero slack times are called critical events.

That is, the event (i) is said to be critical if Ei = Li.

Critical activity: Since the difference between the latest start time and earliest start time of an activity is usually called as total float, the activities with zero total float are known as critical activities.

That is, an activity is said to be critical if a delay in its start will cause a further delay in the completion date of the entire project.

Critical path: Path connecting the first initial node to the very last terminal node, of longest duration in any project network is called the critical path.

That is, the sequence of critical activities in a network is called the critical path. Double or darker lines may be used to denote the critical path.

Main Features of Critical Path

  1. If a project has to be shortened, then some of the activities on the critical path must also be shortened. The application of additional resources on other activities will not give the desired result unless the critical path is shortened first.
  2. The variation in actual performance from the expected activity duration time will be completely reflected in a one-to-one fashion in the anticipated completion of the whole project.

Example 1

Listed in the Table are the activities and sequencing requirements necessary for the completion of a research project.

 

TABLE 13.1

  • Draw a network diagram for this project.
  • Find the critical path and duration of the project.
  • Find the total, free and independent floats of various activities.

Solution:

FIGURE 13.15

The network of the given project is shown in Fig. 13.15. Using forward pass computations TEi or Ei for each node i is as follows:

TE1 = 0

TE2 = TE1 + 5 = 0 + 5 = 5
TE3 = TE2 + 2 = 5 + 2 = 7
TE4 = TE3 + 2 = 7 + 2 = 9
TE5 = Max. {TE1 + 6, TE4 + 0} = Max. {0 + 6, 9 + 0} = 9
TE6 = TE5 + 2 = 9 + 2 = 11
TE7 = TE5 + 6 = 9 + 6 = 15
TE8 = Max {TE7 + 0, TE6 + 5}
= Max {15 + 0, 11 + 5} = 16
TE9 = TE8 + 6 = 16 + 6 = 22
TE10 = Max {TE7 + 4, TE9 + 2}
= Max {15 + 4, 22 + 2 = 24}
TE11 = TE10 + 3 = 24 + 3 = 27
TE12 = Max {TE11 + 1, TE4 + 1}
= Max {27 + 1, 9 + 1} = 28

Now, by using backward pass computations the value TLj for each node j is computed.

TL12 = 28
TL11 = TL12 - 1 = 28 - 1 = 27
TL10 = TE11 - 3 = 27 - 3 = 24
TL9 = TL10 - 2 = 24 - 2 = 22
TL8 = TL9 - 6 = 22 - 6 = 16
TL7 = Min {TL10 - 4, TL8 - 0}
= Min {24 - 4, 16 - 0} = 16
TL6 = TL8 - 5 = 16 - 5 = 11
TL5 = Min {TL7 - 6, TL6 - 2}
= Min {16 - 6, 11 - 2} = 9
TL4 = Min {TL12 - 1, TL5 - 0}
= Min {28 - 1, 9 - 0} = 9
TL3 = TL4 - 2 = 9 - 2 = 7
TL2 = TL3 - 2 = 7 - 2 = 5
TL1 = Min {TL5 - 6, TL2 - 5}
= Min {9 - 5, 5 - 5} = 0

We recall that the critical path is a longest path in the network. Here, the critical path is

B—C—D—E—H—I—J—L—M (or)
1—2—3—4—5—6—8—9—10—11—12

It is shown by double lines in Fig. 13.15.

We observe that the critical path is the sequence of those activities for which TE and TL values are equal for the starting as well as the ending nodes. There is another way of identifying the critical path. It is the sequence of activities with total float equal to zero.

The various floats of each activity are calculated in Table 13.2.

TABLE 13.2

We observe that total float can also be calculated using (6)–(4). In the above Table free float is calculated by using the formula:

Free float of activity ij = Total float–(TLTE) of event j

For example,

Free float of 1–5 = 3–(TLTE) of node 5
= 3–0 = 3

Independent float of each activity is calculated by using the formula:

Independent float of ij = Total float of its ij–(TLTE) of node i

For example,

Independent float of 1–5 = Free float of 1–5–(TLTE) of node 1
= 3–0 = 3.

Example 2

Draw the network and find the critical path and various floats.

Solution: The network is shown in Fig. 13.16 and the numbering of the nodes is according to Fulkerson’s rule:

FIGURE 13.16

Using forward pass computations, the earliest occurrence time TEi or Ei is calculated for each node Ei as follows:

Set TE1 = 0
TE2 = TE1 + 2 = 0 + 2 = 2
TE3 = TE1 + 2 = 0 + 2 = 2
TE4 = TE2 + 4 = 2 + 4 = 6
TE5 = Max {TE2 + 3, TE4 + 0}
= Max {2 + 3, 6 + 0} = 6
TE6 = Max {TE5 + 6, TE3 + 8} = 12

Now, by using backward pass computations, the latest occurrence time TLi or Li for each node i is calculated as follows:

Set TL6 = TE6 = 12
TL5 = TL6–6 = 6
TL3 = TL6–8 = 4
TL4 = TL5–0 = 6–0 = 6
TL2 = Min {TL5–3, TL4–4} = 2
TL1 = Min {TL2–2, TL3–2} = 0

Hence, the critical path is 1–2–4–5–6.

The critical path is represented by double lines in the network. The project duration is 12 days. The various floats for each activity are calculated and represented in the following Table.

 

TABLE 13.3

We observe that the total float can also be calculated by using (5)–(3). In the above Table free float is calculated by using the formula

Free float of activity ij = Total float–(TLTE) of event j

For example,

free float of 1–3 = Total float of 1–3–(TLTE) of node 3.
= 2–2 = 0.

Independent float of each activity is calculated by using the formula:

Independent float of ij = Total float of ij–(TLTE) of node i

For example,

Independent float of 3–6 = Total float of 3–6–(TLTE) of node 3
= 2–2 = 0.

Example 3

A project schedule has the following characteristics:

  • Construct a network diagram.
  • Compute the total float, free float and independent float for each activity.
  • Find the critical path and total project duration.

Solution: The network is shown in Fig. 13.17. The earliest occurrence time TEi and the latest occurrence time TLi are calculated as explained in Examples 1 and 2.

FIGURE 13.17

Critical path is 1–3–5–7–8–10 and the project duration is 22 days.

 

TABLE 13.4

Example 4

Construct PERT network and compute

  • Total float, free float and independent float for each activity.
  • Critical path and its duration.
  • Find the minimum number of cranes the project must have for its activities 2–5, 3–7 and 8–9 without delaying the project. Then, is there any change required in PERT network? If so, indicate the same.

Solution: The network is given in Fig. 13.18.

FIGURE 13.18

The TEi and TLi are calculated using forward pass computations and backward pass computations, respectively. The various floats are calculated in the Table 13.5.

 

TABLE 13.5

(b) Critical path is 1–3–6–9 with duration 15 months.

(c) Minimum number of cranes.

Finish 3–7 at 7 with one crane.

Finish 2–5 at 7 + 4 = 11 with the same crane.

Finish 5–8 at 11 + 1 = 12 without the crane.

Finish 8–9 at 12 + 3 = 15 with the same crane.

Therefore, one crane will be sufficient, 2–5, 5–8, and start at 7, 11 and 12, respectively.

Example 5

A project schedule has the following characteristics:

  • Construct the PERT network and find the critical path and time duration of the project.
  • Activities 2–3, 4–5, 6–9 each requires one unit of the same key equipment to complete it. Do you think availability of one unit of the equipment in the organisation is sufficient for completing the project without delaying it? If so what is the schedule of these activities?

Solution: The network of the project is given in Fig. 13.19.

FIGURE 13.19

TEi and TLi are calculated using forward pass computations and backward pass computations, respectively. The critical path is 1-4-8-9 with a duration of 15 days. The total float of various activities are calculated as follows:

TABLE 13.6

(c) Activity 6–9 can only be undertaken when both 2–3 and 4–5 and their following activities are over. Thus, 2–3 and 4–5 contend for the equipment. The two alternative schedules for these are:

The second alternative does not delay the project completion time and hence is to be recommended.

13.4 PROJECT EVALUATION AND REVIEW TECHNIQUE (PERT)

This technique, unlike CPM, takes into account the uncertainty of project durations. If the duration of activities in a project is uncertain, then activity scheduling calculations done using the expected value of the durations. However, such expected duration estimation may not give an accurate answer. Thus, rather than estimating directly the expected completion time of an activity, three values are considered. From these, a single value is estimated for further consideration. This is called three-time estimates in PERT.

  1. Optimistic time estimate (t0 or a) is the duration of any activity when everything goes on well during the project. That is, labourers are available and come in time, machines are working properly, money is available whenever needed, there is no scarcity of raw material needed, and so on.
  2. Pessimistic time estimate (tp or b) is the duration of an activity when almost everything goes against our will and a lot of difficulties are faced while doing a project.
  3. Most likely time estimate (tm or m) is the duration of an activity when some things go on well and some thing go wrong while doing a project.

These three time values are shown in Fig. 13.20.

FIGURE 13.20 Time distribution curve

Two main assumptions made in PERT calculations are:

  1. The activity durations are independent. That is, the time required to complete an activity will have no bearing on the completion time of any other activity of the project.
  2. The activity durations follow β distribution. β distribution is a probability distribution with density function K(ta)a (βt)b with mean and standard deviation .

13.4.1 PERT Procedure

Step 1: Draw the project network.

Step 2: Compute the expected duration of each activity .

Step 3: Compute the expected variance σ2 of each activity.

Step 4: Compute the earliest start, earliest finish, latest start, latest finish and total float of each activity.

Step 5: Determine the critical path and identify critical activities.

Step 6: Compute the expected variance of the project length (also called the variance of the critical path) which is the sum of the variances of all the critical activities.

Step 7: Compute the expected standard deviation of the project length σc and calculate the standard normal deviate

where,

TS = specified or scheduled time to complete the project
TE = normal expected duration (duration of the project)
σc = expected standard deviation of the project length

Example 1

A small project is composed of activities whose time estimates are listed in the Table below. Activities are identified by their beginning (i) and ending (j) node numbers.

  • Draw the project network.
  • Find the expected duration and variance for each activity. What is the expected project length?
  • Calculate the variance and standard deviation of the project length. What is the probability that the project will be completed
    1. at least 4 weeks earlier than expected?
    2. no more than 4 weeks later than expected time?
  • If the project due in 19 weeks, what is the probability of meeting the due date? Given:

Solution: The expected time and variance of each activity is calculated in the following Table:

 

TABLE 13.7

The network is drawn with the help of te.

FIGURE 13.21

(b) By examining all the paths we see that the critical path is 1-3-5-6. (Critical path can also be obtained by calculating TEi and TLi of each event or node.) can also be obtained by examining all possible paths.

Duration of project = 17 weeks.
Variance of project length = Sum of the variances of the critical activities

(c) The standard normal deviate is

   (i)

Ts = 13

i.e.

P(TS ≤ 13) = P(Z ≤–1.33)
= 0.5–ϕ (1.33)
= 0.5–0.4082
= 0.0918 = 9.18%

FIGURE 13.22

   (ii)

TS = 21

P(TS ≤ 21) = P(Z ≤ 1.33)
= 0.5 + ϕ (1.33)
= 0.5 + 0.4082
= 0.9082
= 0.9082 ≈ 90 82%

(d) When the due date is 19 weeks,

∴ Probability of meeting the due date is

P(Z ≤ 0.67) = 0.5 + ϕ (0.67)
= 0.5 + 0.2486
= 0.7486 ≈ 74.86%

Thus, the probability of not meeting the due date is 1–0.7486 is 0.2514 or 25.14%.

Example 2

For the network below, the estimate t0, tm and tp are given in this order for each of the activities. Find the probability of completing the project in 25 days.

FIGURE 13.23

Solution: The expected time and variance of each activity are calculated in Table 13.8.

 

TABLE 13.8

The te is represented in the network as follows:

FIGURE 13.24

The critical path is calculated as follows:

  Path Duration
  1–2–4–6–7 19 days
  1–2–4–5–6–7 20.3 days
  1–2–4–5–7 21.3 days
  1–2–3 -7 16 days
  1–2–3–5–7 18 days
  1–2-3–5–6–7 17 days

Hence, the critical path is 1–2–4–5–7 and the expected project duration TE = 21.3 days.

P(TS ≤ 25) = P(Z ≤ 1.55)
= 0.5 + ϕ (1.55)
= 0.5 + 0.4394 = 0.9394 ≈ 93.94%

Here, we note that the critical path can also be determined by calculating TEi and TLi for each node.

Example 3

The following Table gives optimistic time (a), the most likely time (m) and the pessimistic time (b). Draw the network of the project and calculate the slack for each event. Find the critical path and the probability of completing the project in 35 days.

Solution: By using te in Table 13.19 the network is drawn.

FIGURE 13.25

The expected time for each activity and variance of each activity are calculated in Table 13.9.

 

TABLE 13.9

The critical path is 1–3–4–7–10. The project duration is, 33 days. That is, TE = 33 days. The expected variance of the critical path is

= 0.11 + 2.25 + 0.69 + 4
= 7.05

So, the expected standard deviation

P(TS ≤ 35) = P(Z ≤ 0.75)

= 0.5 + ϕ (0.75)

= 0.5 + 0.2734

= 0.7734 ≈ 77.34%

The various floats are calculated in Table 13.10.

 

TABLE 13.10

Example 4

Three time estimates (in months) of all activities of a project are as given below:

  1. Find the expected duration and standard deviation of each activity.
  2. Construct the project network.
  3. Determine the critical path, expected project length and expected variance of project length.
  4. What is the probability that the project will be completed (i) two months earlier than expected? (ii) What due date has about 90% chance of being met?

Solution: The expected duration and expected standard deviation of each activity is calculated in Table 13.11.

 

TABLE 13.11

(b) The network is shown in Fig. 13.26

FIGURE 13.26

(c) Critical path: 1–2–3–4–5–6

Expected project length = 14 months

Expected variance = 0.0045 + 1.0609 + 0.25 + 0.2209 + 0.0011
= 1.5374

Hence, the expected standard deviation is

(d)   (i) TS = 12, TE = 14,  c = 1.2399

P(TS ≤ 12) = P(Z ≤ – 1.61)
= 0.50 - ϕ (1.61)
= 0.5 - 0.4463 = 0.0537 = 5.3%

Required probability = 5.4%

(ii) Z value for 90% area in the normal table = 1.28 (approximately). Let TS be the required time.

Then,

i.e.

TS = 1.28 × 1.2399 + 14
= 15.58 months (nearly).

13.5 RESOURCE ANALYSIS IN NETWORK SCHEDULING

In the earlier discussions on PERT and CPM, it was assumed that the only constraint for an activity was the starting date and the completion date. Availability of resources and cost aspects were not considered. There are two kinds of costs which can influence project schedules—direct costs and indirect costs.

Direct costs are the costs directly associated with each activity such as machine costs, labour costs, and so on. Indirect costs are the costs due to management services, rentals, insurance including allocation of fixed expenses, cost of security, and so on.

While direct costs allocated to a project goes up with the increase in project duration in direct costs go high as the time for individual activity is reduced.

Crashing: The process of reducing an activity time by putting extra effort is called crashing the activity. It is the process of shortening a project and is usually achieved by adding extra resources to an activity.

It may be noted that for technical reasons, the duration of an activity cannot be reduced indefinitely. The crash time represents the fully expedited or the minimum activity duration time that is possible, and any attempts to further ‘crash’ would only raise the direct costs of the activity without reducing the time. The activity cost corresponding to the crash time is called the crash cost which equals the minimum direct cost required to achieve the crash performance time. These are in contrast to the normal time and the normal cost of the activity. The normal cost is equal to the absolute minimum of the direct cost required to perform an activity. The corresponding activity duration is known as the normal time.

The time-cost relationship can be represented by the time-cost trade-off curve shown in Fig. 13.27.

FIGURE 13.27

For simplicity, the relationship between normal-time cost and crash-time cost for an activity is assumed to be linear instead of being. Thus, the crash cost per unit of time can be estimated by computing the relative change in cost (cost slope) per unit change in time. From Fig. 13.27, it is clear that one must be interested in the central region or the curve contained between points A and B. To establish a trade-off between time and cost, the direct cost of completing an activity per unit time is computed as follows:

The cost slope represents the rate of increase in the cost of performing an activity per unit increase in time and is called cost/time trade-off. It varies from activity to activity.

There is a method for finding the optimum duration and the associated least cost called the least cost schedule. It should be observed that there is no need to crash all jobs to get a project done faster. Only critical activities need be expedited. Least cost schedule will indicate which critical activities are to be crashed and how much so as to get the optimum duration.

13.5.1 Time Cost Optimisation Algorithm (or) Time Cost Trade-off Algorithm (or) Least Cost Schedule Algorithm

Step 1: Draw the network.

Step 2: Determine the critical path and the normal duration. Also, identify the critical activities.

Step 3: Find the total normal cost and the normal duration of the project.

Step 4: Compute the cost slope for each activity by using the formula

Step 5: Crash the critical activity of least cost slope first to the maximum extend possible so that the project duration is reduced simultaneously.

Step 6: Calculate the new direct cost cumulatively by adding the cost of the crashing to the current direct cost.

Total cost = New direct cost + Current indirect cost.

Step 7: When critical activities are crashed and the duration is reduced, other paths may also become critical. Such critical paths are called parallel critical paths. When there is more than one critical path in a network, project duration can be reduced only when either the duration of a critical activity common to all critical paths is reduced or the durations of the different suitable activities on different critical paths are simultaneously reduced.

Step 8: Stop when the total cost is minimum. This gives optimum (least cost) schedule called optimum duration.

Remarks:

  1. Minimum (least) duration need not be the same as (least cost) optimum duration.
  2. When no indirect cost is given the least cost optimum duration is the same as the normal duration where no crashing is done but least cost duration may be found out.

Example 1

The following Table gives the activities in a construction project and other relevant information:

Indirect costs vary as follows:

  • Draw an arrow diagram of the project.
  • Determine the project duration which will result in minimum total cost.

Solution: With the help of normal time, network is constructed and is shown in Fig. 13.28.

FIGURE 13.28

To identify the critical path

  Path Duration (in days)
  1–2–5 12
  1–4–5 10
  1–2–4–5 13
  1–3–4–5 8

Hence, the critical path is 1–2–4–5, project duration is 13 days and the critical activities are 1–2, 2–4 and 4–5.

Cost slope for each activity is calculated by using the formula

Among the critical activities, activity with least cost slope is A(1–2). So, crash the activity A by 4–3 = 1 (Normal time–crash time) day. Thus, project duration reduces to 12 days and the total project cost = Total direct cost + Increased direct cost due to crashing.

Indirect cost for 12 days

= 713 (i.e. total of normal cost) + 1 × 30 + 250 = 993.

The new network is shown in Fig. 13.29.

FIGURE 13.29

By examining all the paths from node 1 to node 5, we observe that the critical path is again 1–2–4–5. The activity 1–2 is already crashed. Among the critical activities 2–4 and 4–5, the activity with the smallest cost slope is D (2–4). Hence, crash activity D (2–4) by 2 = 5–3 days. The network is shown in Fig. 13.30.

FIGURE 13.30

Now, there are three critical paths

1–2–5
1–4–5
1–2–4–5

each with, duration 10 days.

 

Total cost = 743 + 2 × 50 + 100 = 943.

Since there are more than one parallel critical path, crashing must be performed.

Since critical activities A and D cannot be crashed further, therefore, crash activities F and G by 2 days each to reduce the project duration by 2 days. The new network is shown in Fig. 13.31.

FIGURE 13.31

The critical paths are

 

1–4–5
1–2–5
1–2–4–5

each with duration 8 days.

 

Total cost = Total direct cost + Increased direct cost due to crashing + Indirect cost for 8 days
= 843 + (2 × 30 + 2 × 70) + 50 = 1,093.

Since all the activities in the critical path 1–2–5 are crashed, further parallel crashing is not possible. The crashing-schedule of the project is as shown in Table 13.12.

 

TABLE 13.12

From the Table we see that minimum total cost is 943 and the optimum duration is 10 days.

Example 2

The following data is pertaining to a project with normal time and crash time.

  1. If the indirect cost is 100 per day, find the least cost schedule (optimum duration).
  2. What is the minimum duration?

Solution: The network is drawn using the normal time and is shown in Fig. 13.32.

FIGURE 13.32

We observe that the critical path is 1–2–5.

 

Normal duration = 18 days
Total cost = Direct cost + Indirect cost
= 580 + 1,800
= 2,380

Cost slope for various activities are called as follows:

Since 1–2 is the critical activity with least cost slope, crash the activity 1–2 by 2 (8–6) days. The new network is shown in Fig. 13.33.

FIGURE 13.33

Critical path is again 1–2–5.

Current duration is 16 days.

 

Current total cost = 580 + 2 × 50 + 16 × 100
= 2,280

Since 1–2 cannot be crashed further, crash the critical activity 2–5 by 4 days. (Even through 5 days are available for crashing 2–5, we take 4 days, since if we crash 2–5 by 5 days then the path 1–2–5 will become non-critical.)

The new network is given in Fig. 13.34.

FIGURE 13.34

Current critical path:

  1. 1–2–5
  2. 1–3–4–5

Current duration is 12 days.

 

Current total cost = 680 + 4 × 60 + 12 × 100
= 2,120.

Since there are more than one critical paths, only parallel crashing is allowed. Crash the critical activities 2–5 and 4–5 by 1 day each. The duration of the path 1–2–4–5 is 11 days and also the activity 2–5 can be crashed only by 1 day. The resulting network is shown in Fig. 13.35.

FIGURE 13.35

Current critical paths:

 

1–2–5
1 – 3 – 4 – 5

Current duration:

 

12 – 1 = 11 days

Current total cost = 920 + 1 × 60 + 1 × 10 + 11 × 100
= 2,090

No further crashing is possible since all the activities on the critical path 1–2–5 have been crashed to the maximum extent.

The crashing schedule of the project is as shown in Table 13.13.

 

TABLE 13.13

(b) From Table 13.13, we observe that the optimum duration is 11 days and the minimum duration is also 11 days.

Example 3

A small project consists of the jobs in the accompanying Table. With each job is listed its normal time and a minimum or crash time (in days). The cost (in per day) of crashing each job is also given.

  1. What is the normal project length and minimum project length?
  2. Determine the minimum crashing cost of schedules ranging from normal length down to and including the minimum length schedule, that is, if L is the length of the normal schedule, find the cost of schedules which are L, L–1, L–2, so days long.

Overhead costs total 60 per day. What is the optimal length schedule duration on each job for the optimal solution?

Solution: Using the normal duration the network is drawn and is shown in Fig. 13.36.

FIGURE 13.36

The critical path is calculated as follows:

 

  Path   Duration
  1–2–4–5   16 days
  1–4–5   17 days
  1–3–4–5   20 days

The critical path is 1–3–4–5 and the critical activities are 1–3, 3–4 and 4–5.

 

Total cost = Direct cost + Indirect cost
= 0 + 20 × 60 = 1,200.

Among the critical activities, the activity with the least cost slope is 3–4. Hence, crash the critical activity 3–4 by 1 day. The new network is given in Fig. 13.37.

FIGURE 13.37

Critical path: 1–3–4–5 and the project duration is 19 days.

 

Total cost = Direct cost + Indirect cost
= 1 × 15 + 19 × 60 = 1,155

Now, if we crash the critical activity by 1 more day the critical path becomes 1–3–4–5 and the project duration 18 days.

 

Total cost = Direct cost + Indirect cost
= 15 + 1 × 15 + 18 × 60 = 1,110

If we crash the critical activity by 1 more day, then the critical paths are

 

1–3–4–5

and,

1–4–5

The project duration is 17 days

 

Total cost = Direct cost + Indirect cost
= 30 + 1 × 15 + 17 × 60 = 1,065

If we simultaneously crash (parallel crash) 3–4 and 1–4 by 1 day each then the critical paths are

 

1–3–4–5
1–4–5

and,

1–2–4–5

The projection duration is 16 days.

 

Total cost = 45 + 1 × 15 + 1 × 30 + 16 × 60 = 1,050.

If we cash activity 4–5 by 1 day, the critical path remains the same and the project duration becomes 15 days.

 

Total cost = 90 + 1 × 40 + 15 × 60 = 1,030.

If we perform parallel crash of activities 1–3, 1–4 and 2–4 by 1 day each, the project duration becomes 14 days.

 

Total cost = 130 + 1 × 25 + 1 × 30 + 1 × 10 + 14 × 60 = 1,035.

If we perform parallel crash of activities 1–3, 1–4 and 2–4 by 1 day each, the critical path remains the same and the project duration becomes 13 days.

 

Total cost = 195 + 1 × 25 + 1 × 30 + 1 × 10 + 13 × 60 = 1,040.

If we perform parallel crash of activities 1–3, 1–4 and 1–2 by 1 day each, then the critical path becomes the same and the project duration becomes 12 days.

 

Total cost = 260 + 1 × 25 + 1 × 30 + 1 × 20 + 12 × 60
= 1,055.

Further crashing is not possible. The crashing schedule of the project is shown in the Table 13.14.

 

TABLE 13.14

From Table 13.14, we observe that the optimum duration is 15 days and the minimum duration is 12 days.

13.6 RESOURCE ALLOCATION AND SCHEDULING

A resource is defined by the physical variables such as crew size (labour), finance (cost), equipment (shop facilities), and so on, available to the management to achieve the objective of the project. Problems of resource scheduling vary in kind and complexity depending upon the nature of the project and its organisational set up. It is but natural that activities are scheduled so that no two of them requiring the same facility occur at the same time, wherever possible. The problem of scheduling activities so that none of the precedence relations are violated is an extremely difficult task even for projects of modest size. The problem of scheduling project with the limited resources is usually large, combinatorially. Even the powerful techniques aided by the fastest, most sophisticated computer can solve only small projects having not more than about 100 activities. Analytical techniques are impractical for real world problems of this type. One turns to heuristic programmes for such cases.

Lacking time or inclination to pursue more through problem solving procedures, one employs a rule of thumb arising out of experience, expertise and commonsense. In some cases, the rule of thumb is insufficient. It must be combined with other rules to take into consideration additional factors or exceptional circumstances. A collection of such rules for solving a particular problem is called a heuristic programme. Such a programme may require a computer for solving complex problem.

Heuristic programmes for resource scheduling are

  1. Resource leveling programmes
  2. Resource allocation progarmmes

Resource Levelling Programmes

In the process of resource levelling, the activities are critically sequenced, subject to the constraint of availability of resources, and the minimum period of the project is redetermined accordingly.

Under this technique, the project manager may be able to lower the maximum resource requirements by shifting a non-critical activity between its earliest start time and latest finish time.

The two rules normally used in scheduling non-critical activities are as under:

  1. If the total float of a non-critical activity is equal to its free float, then it can be scheduled any where between its earliest start and latest completion times.
  2. If the total float of a non-critical activity is more than its free float, then its starting time can be delayed relative to its earliest start time by no more than the amount of its free float without affecting the scheduling of its immediately succeeding activities.

Resource smoothen: If the constraint is the total project duration, then the resource allocation only smoothens the demand on resources in order than the demand of any resource is an uniform as possible. The periods of maximum demand are located and the activities according to their float values are shifted for balancing the availability and requirement of resources. So, the intelligent utilisation of floats can smoothen the demand of resources to the maximum possible extent. Such type of resource allocation is called ‘resource smoothing’ or ‘load smoothing’.

Procedure

  1. Calculate the earliest start and latest finish times of each activity and then draw a time-scaled version (or squared) of the network. Critical path in the network is drawn along a straight line and non-critical activities are on either sides of this line. Resource requirement of each activity is given along the arrows.
  2. Draw the resource histogram by taking the earliest start times or latest start times of activities on the x-axis and cumulative resources required on the y-axis.
  3. Shift start times of non-critical activities having largest float first in order to smoothen the resources.

Example 1

Given below is the crew size (manpower) requirement for each activity in a project:

  1. Draw the network of the project activities.
  2. Rearrange the activities suitably for reducing the existing total crew size.
  3. If only 9 men are available for the execution of the project, rearrange the activities suitably for leveling the manpower resource.

Solution: The network is given in Fig. 13.38.

FIGURE 13.38

Numbers in brackets with each activity arrow in the network represent the manpower requirement of the activity.

The earliest and latest completion times of each activity are indicated along the nodes of Fig. 13.38.

The critical path is 0 → 1 → 3 → 5 → 7 → 9 and the project duration is 20 days.

In the time scaled version, the critical path is drawn along the straight line and non-critical are added in dotted lines, as shown in Fig. 13.39.

FIGURE 13.39

(b) The numbers above the arrows indicate the crew size (the resource requirements), the numbers below the arrows indicate the days and the non-critical paths are added as shown in Fig. 13.39. The resource histogram can now be drawn by summing up the manpower requirements for each day. This is shown in Fig. 13.40.

FIGURE 13.40

From Fig. 13.41, we observe that the maximum demand of 15 men occurs on the 15th and 16th days. To smoothen load, the activities will have to be shifted depending upon the floats. Since the path 3–6– 8–9 has a float of two days, the activities 6–8 and 8–9 are shifted to the right. Thus, the start of each of these activities is delayed by 2 days. Similarly, activity 4–7 can be shifted to the right so that it starts on the 10th day instead of starting on the 7th day. After making the necessary shifting, the network is drawn as shown in Fig. 13.41.

FIGURE 13.41

Resource histogram for this squared network is given in Fig. 13.42. This indicates that the maximum manpower required is 11 men.

(c) Since only 9 men are available instead of 11, therefore, activities have to rearranged and expanded in term of their completion time. This would increase the total project durations from 20 days to 25 days.

FIGURE 13.42

Example 2

A Chennai construction company is bidding on a contract to install a line of microwave towers. It has identified the following activities, along with their expected times, predecessor restrictions, and work requirements.

The contract specifies that the project must be completed in 14 weeks. The company will assign a fixed numbers of workers to the project for its entire duration and so it would like to ensure that the minimum number of workers is assigned and that the project is completed in 14 weeks. Find a schedule which will do this.

Solution: Using the precedence relationship, the network diagram is given in Fig. 13.43.

FIGURE 13.43

The earliest and latest completion times of each activity are indicated along the nodes in Fig. 13.43. The critical path is B → E → G → H and the project duration is 14 weeks. The time-scaled variation of the network, showing the critical path along the straight line is shown in Fig. 13.44. Numbers above the arrows indicate the workers.

FIGURE 13.44

To determine the minimum number of workers required to complete the project, the critical activities are scheduled first. Since non-critical activity A is scheduled at t = 0 followed by the non-critical activities C and D on the fourth day, workers required would rise to 8. The total float of activity A is more than its free float and so the earliest start time as well as free float is zero. Therefore, it has to be scheduled otherwise it would result in delay of the project.

Activity C has float of 7 weeks and activity F has a float of 2 weeks. Requirement of workers in the 5th, 6th and 7th weeks is 8 and during the 8th and 9th weeks is 9 workers. This demand has to be smoothened. For this, we shift activity F to the 9th week. Thus, the total weekly requirement of workers after rearranging the activities comes to be of 6 during the entire project duration of 14 weeks as shown in Fig. 13.45.

FIGURE 13.45

13.7 APPLICATION AND DISADVANTAGES OF NETWORKS

13.7.1 Application Areas of PERT/CPM Techniques

PERT/CPM techniques are widely used in the following typical areas:

Building construction: It is one of the largest areas in which the network techniques of project management have found applications.

Administration: Networks are used by the administration for streamlining paper work, for making major administrative changes in the system, for long-range planning and for developing staffing plans, and so on.

Manufacturing: The design, development, and testing of new machines, installing machines and plant layouts are a few examples of PERT/CPM applications to the manufacturing function of a firm.

Research & Development: R & D is the most expensive area where PERT techniques area used for development of new products, processes and systems.

Inventory planning: Installation of production and inventory control, acquisition of spare parts, and other, have been greatly helped by network techniques.

Marketing: Networks are also used for advertising programmes for development and launching of new products and for planning their distribution.

13.7.2 Uses of PERT/CPM for Management

  1. PERT/CPM techniques help the management in properly planning the complicated projects, controlling the working plan and also keeping the plan up-to-dare. These are also helpful in searching the potential spots and in taking corrective measures.
  2. The network techniques provide a number of checks and safeguards against going astray in developing the plan for project. Thus, there is little chance of oversight of certain activities and events.
  3. These techniques help the management in reaching the goal in minimum time and at least cost and also in forecasting the probable project duration and the associated cost.
  4. The networks clearly designate the responsibilities of different supervisors. The supervisor of an activity himself knows the time schedule and also the supervisors of other activities with whom he has to operate.
  5. The flexibility of the network permits the management to make necessary alternations and improvements as and when needed. These allocations can be made during the deployment of resources or reviewing.
  6. Application of network techniques has resulted in better managerial control, better utilisation of resources, improved communication and progress reporting, and better decision-making.
  7. Application of PERT/CPM techniques have resulted in saving of time which directly results in the saving of cost. Also, saving in time or early completion of the project results in earlier return of revenue and introduction of the product or process ahead of the competitors, resulting in increased profits.

13.7.3 Disadvantages of Network Techniques

The following difficulties are faced by the management while using the network techniques:

  1. The difficulty arises while securing realistic time estimates. In new and non-repetitive projects, the time estimates produced are often mere guesses.
  2. It is sometimes troublesome to develop a clear logical network. This depends upon the data input and thus the plan can be better than the personnel who provides the data.
  3. The natural tendency to oppose changes results in the difficulty of persuading the management to accept these techniques.
  4. Determination of level of network detail is another troublesome area. The level of detail varies from planner to planner and depends upon his judgment and experience.
  5. The planning and implementation of networks require personnel trained in network methodology. Managements are reluctant to spare the existing staff to learn these techniques or to recruit trained personnel.
13.8 NETWORK FLOW PROBLEMS

13.8.1 Introduction

Consider a network of pipelines that transport crude oil from oil wells to refineries. Intermediate booster and pumping stations are installed at appropriate distances to move the crude in the network. Each pipe segment has a finite maximum of crude flow (or capacity). The maximum flow of a fluid in each pipe segment will be limited to a particular value depending on the diameter of the pipe in that segment or the slope of the pipe in that segment. A pipe segment may be unidirectional or bidirectional. A unidirectional segment has a finite capacity in one direction and a zero capacity in the opposite direction.

Source and Sink

All flow through a directed and connected network originates at one node, called the source, and terminates at another node, called the sink. All the remaining nodes are called transshipment models. Flow through an arc is allowed only in the direction indicated by the arrowhead, where the maximum flow is noted as the capacity of the arc.

Objective

The main objective is to maximise the total amount of flow from the source to the sink. The amount is determined by measuring either the amount leaving the source or the amount entering the sink.

Example 1

Figure 13.46 demonstrates a typical pipeline network.

FIGURE 13.46

How can we determine the maximum capacity of the network between the wells and the refineries?

Solution: The solution of the proposed problem requires converting the network into one with a single source and a single sink. This requirement can be accomplished by using unidirectional infinite capacity arcs as shown in Fig. 13.46.

Given an arc (i, j) with i < j, we use the notation to represent the flow capacities in the two directions ij and ji, respectively. To eliminate ambiguity, we replace on the arc next to i with placed next to node j as shown in Fig. 13.47.

FIGURE 13.47

13.8.2 Max-flow Min-cut Theorem

The max-flow min-cut theorem states that for any network with a single source and a single sink the maximum flow through the network equals the minimum cut value in the network.

13.8.3 Enumeration of Cuts

A cut defines a set of arcs whose deletion from the network causes a complete disruption of flow between the source and sink nodes. The cut capacity equals the sum of the capacities of the associated networks.

Among all possible cuts in the network, the cut with the smallest capacity gives the maximum flow in the network.

Example 2

Consider the network given in Fig. 13.48. The bidirectional capacities are shown on the respective arcs.

FIGURE 13.48

For arc (3, 4), the flow limit is 10 units from 3 to 4 and 5 units from 4 to 3.

This network illustrates three cuts whose capacities are computed in Table 13.15.

 

TABLE 13.15

Maximum flow in the network does not exceed 60 units. We cannot tell what the maximal flow is until all the cuts in the network are enumerated. Unfortunately, the enumeration of all the cuts is not a simple task. Hence, the enumeration procedure cannot be used to determine the maximal flow in the network.

13.8.4 Ford–Fulkerson Algorithm

The Ford–Fulkerson method is an algorithm that computes the maximum flow in a flow network. The idea behind the algorithm is very simple. As long as there is a path from the source (start node) to the sink (end node) with available capacity on all edges in the path, we send flow along one of these points. Then we find another path, and so on. A path with available capacity is called an augmenting path.

Algorithm

Let G(V, E) be a graph, and for each edge from u to v, let c(u, v) be the capacity and f (u, v) be the flow.

Our aim is to find the maximum flow from the source s to the sink t.

 

  Capacity Constraints:    
  ∀(u, v) ∊ Ef(u, v) ≤ c(u, v)   The flow along an edge cannot exceed its capacity.
  Skew Symmetry:    
  ∀(u, v) ∊ Ef(u, v) = –f(u, v)   The net flow from u to v must be the opposite of the net flow from v to u.
  Flow Conservation:    
  uv : us ^ ut   Unless u is s or t, the net flow to a node is zero, except the source, which produces the flow, and the sink, which consumes the flow.

This means that the flow through the network is a legal flow after each round in the algorithm. We define the residual network Gf (V, Ef) to be the network with capacity Cf (u, v) = c(u, v)–f (u, v) and no flow. Note that it can happen that a flow from v to u is allowed in the residual network, though it is disallowed in the original network:

If f(u, v) > 0   and   c(v, u) = 0   then   cf(v, u) = c(v, u) – f(v, u) = f(u, v) > 0.

Inputs: Graph G with flow capacity C, a source node s, and a sink node t

Output: A flow f from s to t, which is maximum

  1. f(u, v) ← 0 for all edges (u, v)
  2. While there is a path from s to t in Gf, such that cf(u, v) > 0 for all edges (u, v) ∊ p:
    1. Find cf(p) = min{cf (u, v):(u, v) ∊ p}
    2. For each edge (u, v) ∊ p
      1. f(u, v) ← f(u, v) + cf(p) (send flow along the path)
      2. f(v, u) ← f(u, v) – cf(p) (the flow must be returned later)

The path in step 2 can be found using breadth-first search (BFS) or depthfirst search (DFS) in Gf (V, Ef).

When no more paths in step 2 can be found, s will not be able to reach t in the residual network. If S is the set of nodes reachable by s in the residual network, then the total capacity in the original network from S to the reminder of V is on the one hand is equal to the total flow we found from s to t and on the other hand serves as an upper bound for all such flows.

13.8.5 Maximal Flow Algorithm

The idea of the maximal flow algorithm is to find a breakthrough path with net positive flow that links the source and the sink nodes. We will use this idea to develop the maximal flow algorithm.

Algorithm

Step 1: Form a From–To capacity matrix [C] for the given flow network. Cij is the flow from node i to node j, where i = 1 to n and j = 1 to n. Set the interaction number k = 1 and cumulative flow x = 0.

Step 2: Trace a path from source (s) to destination (t) directly or passing through some intermediate nodes, which have same feasible quantity of flow. Check whether such path exists; if so, go to step 3, otherwise go to step 6.

Step 3: Find the minimum among the capacities of various links of paths traced in step 2. Denote the quantity by Qk. Set X = X + Qk.

Step 4: Find the next flow matrix [A] by performing the following steps.

  1. Subtract Qk from all Cij values corresponding to all forward links of the path traced.
  2. Add Qk to all the Cij values corresponding to all backward links of the path traced.

Step 5: Renumber the iteration as k = k + 1 and proceed to step 2.

Step 6: Find a new flow matrix [B] by subtracting the elements of flow matrix [A] obtained in the last iteration from the corresponding elements of flow matrix [C] in the first iteration. That is,

Step 7: (a) The cell entries of the flow matrix [B] represent the flows in various arcs of the network.

   (b) The maximal flow from source (s) to destination (t) is X.

   (c) Map the cell entries on the corresponding arcs of the network showing the actual flows in various arcs to achieve the maximal flow of X.

Example 3

Determine the maximal flow from source (1) to sink (6), for the network given in Fig. 13.49.

FIGURE 13.49

Solution:

Iteration 1

Step 1: Write a capacity matrix [C] (Table 13.16).

 

TABLE 13.16

Step 2: Assume the path 1–3–6

Step 3: Q1 = min(C13, C36) = min(60, 50) = 50
Feasibility quantity of flow through the path is 50, that is, X = 50.

Step 4: (a) Subtract 50 from all Cij values corresponding to all forwards links of the path traced.

   (b) Add 50 to all Cij values corresponding to all backward links of the path traced. Then we get the flow matrix as shown in Table 13.17.

 

TABLE 13.17

Iteration 2

Take step 1 of iteration 1.

Step 2: Assume the path 1–2–4–6.

Step 3: Q2 = min(A12, A24, A46) = min(30, 25, 35) = 25
Feasible quantity of flow through the path is 25.
Cumulative flow, X = X + Q2 = 50 + 25 = 75

Step 4: (a) Subtract Q2 from all Aij values corresponding to all forward links of the path traced.

   (b) Add Q2 to all the Aij values corresponding to all backward links of the path traced.

Then we obtain the following flow matrix (Table 13.18).

 

TABLE 13.18

Iteration 3

Step 2: Start with node 1; assume the path 1–4–6.

Step 3: Q3 = min(B14, B46) = min(15, 10) = 10
Therefore, the feasible quantity of flow through the path is X = X + Q3 = 75 + 10 = 85.

Step 4: (a) Subtract Q3 from all Bij values corresponding to all forward links of the path traced.

   (b) Add Q3 to all the Bij values corresponding to all backward links of the path traced.
Then the resultant matrix is as shown in Table 13.19.

 

TABLE 13.19

Iteration 4

Step 2: Starting from node 1, consider the path 1–2–5–6; then
Q4 = min(D12, D25, D56) = min(5, 5, 30) = 5
Therefore, the feasible quantity of flow through the path is 5.
Cumulative flow, X = X + Q4 = 85 + 5 = 90
Applying step 5, as in the earlier iterations, we get Table 13.20.

 

TABLE 13.20

Iteration 5

Starting from node1, assume the path 1–3–4–5–6. Here
Q5 = min(E13, E34, E45, E56) = min(10, 20, 10, 25) = 10
The feasible quantity of flow through this path is 10.
Cumulative flow, X = X + Q5 = 90 + 10 = 100
Step 5 as in earlier iterations gives Table 13.21.

 

TABLE 13.21

No more flow is possible from node 1 to node 6. Subtract the matrix elements of Table 13.21 from the corresponding elements of Table 13.16 and write only the positive values in Table 13.22, as depicted.

 

TABLE 13.22

The maximal flow from node 1 to node 6 is 100 units and the network diagram is as shown in Fig. 13.50.

FIGURE 13.50

Example 4

Determine the maximal flow from source 1 to destination 5 for the network shown in Fig. 13.51.

FIGURE 13.51

Solution:

Iteration 1

Write the flow matrix for the given network as given in Table 13.23.

 

TABLE 13.23

Step 1: Assume the path 1–3–5.

Q1 = min(C13, C35) = min(30, 20) = 20
Let X = 20.

Subtract 20 from all Cij values corresponding to all forward links of the path traced. Add 20 to all Cij values corresponding to all backward links of the path traced.
Then we get the flow matrix as shown in Table 13.24.

 

TABLE 13.24

Iteration 2

Assume the path 1–4–3–5.

Q2 = min(A14, A43, A35) = min(10, 5, 0) = 0

Update X = X + 0 = 20.

Hence, there is no change in A.

Iteration 3

Assume the path 1–4–5.

Q3 = min(A14, A45) = min(10, 20) = 10

Update X = X + 10 = 20 + 10 = 30.

Applying step 5 gives the flow matrix as given in Table 13.25.

 

TABLE 13.25

Iteration 4

Assume the path 1–2–3–5.

Q4 = min(B12, B23, B35) = min(20, 40, 0) = 0

Update X = X + 0 = 30 + 0 = 30.

Iteration 5

Assume the path 1–2–3–4–5.

Q5 = min(B12, B23, B34, B45) = min(20, 40, 10, 10) = 10

Update X = X + 10 = 30 + 10 = 40.

Applying step 5, we get Table 13.26.

 

TABLE 13.26

Iteration 6

Assume the path 1–2–5.

Q5 = min(D12, D25) = min(10, 30) = 10

Update X = X + 10 = 50.

Applying step 5, we get Table 13.27.

 

TABLE 13.27

Iteration 7

Assume the path 1–3–2–5.

Q6 = min(E13, E32, E25) = min(10, 10, 20) = 10

Update X = X + 10 = 50 + 10 = 60.

Applying step 5, we get Table 13.28.

 

TABLE 13.28

No more flow is possible from node 1 to node 5.

Step 6 of the algorithm gives Table 13.29.

 

TABLE 13.29

The maximal flow from node 1 to node 5 is 60 units and the network diagram is as shown in Fig. 13.52.

FIGURE 13.52

13.8.6 Linear Programming Modelling of Maximal Flow Problem

Define xij as the amount of flow in arc (i, j) and let Cij be the capacity of the arc. Assume that s and t are the start and terminal nodes between which we need to determine the maximum flow in the capacitated network.

The constraints of the problem preserve the in–out flow at each node, with the exception of the start and terminal nodes. The objective function maximises either the total ‘out’ flow from start node s or the total ‘in’ flow to terminal node t.

Example 5

Consider the maximum flow model of Example 4. Take s = 1 and t = 5. Table 13.30 summarises the associated Lp with two different objective functions depending on whether we are maximising the output from node 1 (= z1) or the input to node 5 (= z2).

FIGURE 13.53

The city water manager wants to determine a flow plan that will maximise the flow of water to the city.

Formulate this problem as a maximum flow problem by identifying a source, a sink and the transshipment nodes, and then drawing the complete network that shows the capacity of each arc.

 

TABLE 13.30

Solution: The optimal solution is

x12 = 20; x13 = 30; x14 = 10; max z1 = 60 (total outflow from start node 1)

x34 = 10; x25 = 30; x35 = 20; x45 = 20; max z2 = 60 (total inflow to terminal node 5)

13.9 SPANNING TREE ALGORITHMS

13.9.1 Basic Terminologies

A path in a network is a sequence of distinct branches that join nodes regardless of the direction of flow in each branch. A path forms a loop or cycle if it connects a node to itself (Fig. 13.54).

FIGURE 13.54

A directed loop (or a circuit) is a loop in which all the branches are oriented in the same direction.

A connected network is such that every two distinct nodes are linked by at least one path.

A tree is a connected network that may involve only a subset of all the nodes of the network.

A spanning tree links all the nodes of the network with no loops allowed.

Consider the graph given in Fig. 13.55.

FIGURE 13.55

Some of the spanning trees of Fig. 13.55 are shown in Fig. 13.56.

FIGURE 13.56

A typical application occurs in the creation of a network of paved roads that link several rural towns, where the road between two towns may pass through one or more other towns. The most economical design of road system calls for minimising the total miles of paved roads, a result that is achieved by implementing the minimal spanning tree algorithm.

13.9.2 Some Applications of the Spanning Tree Algorithms

  1. Design of telecommunication networks (fibre-optic networks, computer networks, leased line telephone networks, cable television networks, etc.)
  2. Design of a lightly used transportation network to minimise the total cost of providing the links (rail lines, roads, etc.)
  3. Design of a network of high-voltage electrical power transmission lines
  4. Design of a network of wiring on electrical equipment (e.g. a digital computer system) to minimise the total length of the wire
  5. Design of a network of pipelines to connect a number of locations

13.9.3 Algorithm for Minimum Spanning Tree

Step 1: Select any node arbitrarily, and then connect it (i.e. add a link) to the nearest node.

Step 2: Identify the unconnected node that is closest to a connected node, and then connect these nodes (i.e. add a link between them). Repeat this step until all nodes have been connected.

Step 3: (Tie breaking) Ties for the nearest distinct node (step 1) or the closest unconnected node (step 2) may be broken arbitrarily, and the algorithm must still yield an optimal solution. However, such ties are a signal that there may be (but need not be) multiple optimal solutions. All such optimal solutions can be identified by pursuing all ways of breaking ties to their conclusion.

Example 1

Seervada Park has recently been set aside for a limited amount of sightseeing and backpack hiking. Cars are not allowed into the park, but there is a narrow, winding road system for trams and for jeeps driven by the park rangers. The road system is shown in Fig. 13.57 where location O is the entrance into the park; other letters designate the locations of ranger stations. The numbers give the distance of these winding roads in miles.

FIGURE 13.57

How should the lines be laid to accomplish with a minimum total number of miles of line installed?

Solution: Arbitrarily select node O to start.

Step 1: The unconnected node closest to node O is node A. Connect node A to node O. Draw a double arc between these nodes (to denote that this edge is selected) and insert 1 (as this is the edge selected in step 1) (Fig. 13.56).

FIGURE 13.58

Step 2: The unconnected node closest to either node O or node A is node B (closest to A). Connect node B to node A.

Step 3: The unconnected node closest to node O, A, or B is node C (closest to B). Connect node C to node B.

Step 4: The unconnected node closest to node O, A, B or C is node E (closest to B). Connect node E to node B.

Step 5: The unconnected node closest to node O, A, B, C or E is node D (closest to E). Connect node D to E.

Step 6: The only unconnected node is T. It is closest to node D. Connect node T to node D.

All the nodes are now connected. The minimal spanning tree is shown with double lines. The total length of the links is 14 miles.

Example 2

The National Park service plans to develop wildemess areas for tourism. Four locations in the area are designated for automobile access. These sites and the distances (in miles) between them are listed in Table 13.31. To inflict the least harm on the environment, the park service wants to minimise the miles of roadway required to provide the desired accessibility. Determine how roads should be built to achieve this objective.

 

TABLE 13.31

Solution: The network after connecting the nodes is shown in Fig. 13.59.

FIGURE 13.59

The minimal spanning tree is as shown in Fig. 13.60.

FIGURE 13.60

Minimum distance = 7.1 + 16.2 + 8.3 + 5.2 = 38.8 miles.

Example 3

Solve the minimum span problem for the network given in Fig. 13.61.

FIGURE 13.61

Solution: The network after connecting the nodes is shown in Fig. 13.62.

FIGURE 13.62

Minimum distance = 55.

13.10 SHORTEST ROUTE PROBLEM

Of the three types of network techniques, namely maximum flow model, minimum spanning tree model and shortest path model, the first two techniques have been covered in the previous sections.

The shortest-route problem determines the shortest route between a source and destination in a transportation network. The shortest-path model can be further classified into the following:

  1. Shortest path between only one pair of nodes
  2. Shortest path between any pair of nodes

13.10.1 Shortest Path Model

Determination of the shortest path using specialised procedure is known as the shortest-path model. The following two algorithms can be used to find the shortest path in a distance network.

  1. Dijkstra’s Algorithm
  2. Floyd’s algorithm

Dijkstra’s algorithm is designed to determine the shortest routes between the source node and every other node in the network. Floyd’s algorithm is more general because it allows the determination of the shortest route between any two nodes in the network. The areas in the network may be directed or undirected.

The computation of the algorithm advances from a node i to an immediately succeeding node j using a special labelling procedure. Let ui be the shortest distance from source node 1 to node i, and define dij(≥ 0) as the length of arc (i, j). Then the label for node j is defined as

 

[uj, i] = [ui + dij, i], dij ≥ 0

Node labels in Dijkstra’s algorithm are of two types: temporary and permanent. A temporary label can be replaced with another label if a shorter route to the same node can be found. At the point when it becomes evident that no better route can be found, the status of the temporary label is changed to permanent.

Step 0: Label the source node (node 1) with the permanent label [0, −]; set i = 1.

Step 1: (a) Compute the temporary labels [ui + dij, i] for each node j that can be reached from node i, provided j is not permanently labelled. If node j is already labelled with [uj, k] through another node k and if ui + dij < uj, replace [uj, k] with [ui + dij, i].

   (b) If all the nodes have permanent labels, stop. Otherwise, select the label [ur, s] with the shortest distance (=ur) from among all the temporary labels (break ties arbitrarily). Set i = r and repeat step 1.

Example 1

Using Dijkstra’s algorithm, find the shortest path from source a to destination f from the network given in Fig. 13.63.

FIGURE 13.63

Solution:

Iteration 0

Assign the permanent label [0, −] to node a.

Iteration 1

Nodes b and c can be reached from node a. Thus the list of labelled nodes (temporary and permanent) is as shown in Table 13.32.

 

TABLE 13.32

Node Label Status
a [0, −] Permanent
b [0 + 2, a] [2, a]← Temporary
c [0 + 3, a] [3, a] Temporary

For the two temporary labels [2, a] and [3, a], node b yields the smaller distance (= 2). Thus the status of node b is changed to permanent.

Iteration 2

Nodes c and e can be reached from node b. Then the list of labelled node will be as given in Table 13.33.

 

TABLE 13.33

Node Label Status
a [0, −] Permanent
b [2, a] Permanent
c [2 + 2.3, b], [3, a] [3, a]← Temporary
e [2 + 1.7, b] [3.7, b] Temporary

Now, among the nodes with temporary labels, node c has the smallest distance (= 3). Thus status of c is changed to permanent.

Iteration 3

Nodes d and e can be reached from node c. Thus the list of labelled nodes will be as shown in Table 13.34.

 

TABLE 13.34

Node Label Status
a [0, −] Permanent
b [2, a] Permanent
c [3, a] Permanent
d [3 + 1.5, c] [4.5, c] Temporary
e [3.7, b], [3 + 5.4, c] [3.7, b]← Temporary

From the two temporary labels, node e has the smallest distance (= 3.7) and so its status can be made as permanent.

Iteration 4

Nodes d and f can be reached from node e. Thus, the list of labelled nodes will be as shown in Table 13.35.

 

TABLE 13.35

Node Label Status
a [0, −] Permanent
b [2, a] Permanent
c [3, a] Permanent
d [4.5, c]← Temporary
e [3.7, b] Permanent
f [3.7 + 3.3, e] = [7, e] Temporary

Among the nodes with temporary labels, node d has the least distance (= 4.5) and so its status is made as permanent.

Now node f is the only node with temporary label that can be reached from node d (Table 13.36).

 

TABLE 13.36

Node Label Status
Node Label Status
a [0, −] Permanent
b [2, a] Permanent
c [3, a] Permanent
d [4.5, c] Permanent
e [3.7, b] Permanent
f [7, e][6.8, d] [6.8, d] Temporary

The status of the only node with temporary label (f) can be changed as permanent.

The shortest route from a to f is obtained as

 

f → [6.8, d ] [4.5, c] → [3, a] → a

Thus, the shortest route is acdf and the shortest distance is 6.8.

Remark:

The problem can be done in a single network as can be seen in Example 2.

Example 2

Figure 13.64 depicts a network with the distances in miles between pairs of cities 1, 2, … and 8. Find the shortest route between the following cities:

  1. Cities 1 and 8
  2. Cities 1 and 6
  3. Cities 4 and 8
  4. Cities 2 and 6

FIGURE 13.64

Solution: All the iterations can be done on a single network. Note that the suffix denotes the iteration number (Fig. 13.65).

FIGURE 13.65

  1. To find the shortest distance between cities 1 and 8:
    (8)[8, 6] → (6)[6, 3] → (3)[2, 2] → 2[1, 1] →(1)
    That is 1–2–3–6–8
    or 1–3–6–8
    or 1–3–5–6–8
    or 1–2–5–6–8
    ∴ Shortest distance = 8 miles
  2. To find the shortest distance between cities 1 and 6:
    (6)[6, 5] → (5)[3, 3] → 3[2, 1] → 1
    or
    (6)[6, 5] → (5)[3, 2] → 2[1, 1] → 1
    or
    (6)[6, 3] → 3[3, 3] → (3)[2, 1] → 1
    ∴ Shortest distance = 5 miles
  3. To find the shortest distance between cities 4 and 8:
    (8)[8, 6] → (6)[6, 5] → (5)[3, 2]–4.
    ∴ Shortest distance = 8 miles
  4. Shortest distance between cities 2 and 6:
    (6)[6, 3] → (3)[2, 2]–(2)
    or
    (6)[6, 5] → (5)[3, 2]–(2)
    ∴ Shortest distance = 5 miles

Example 3

The network shown in Fig. 13.66 gives the permissible routes and their length in miles between city 1 (node 1) and four other cities (nodes 2 to 5). Determine the shortest distance from city 1 to each of the remaining four cities.

FIGURE 13.66

Solution: Figure 13.67 shows the network diagram after iterations.

FIGURE 13.67

  1. Shortest distance from 1 to 2:
    (2)[55, 4] → (4)[40, 3] → (3)[30, 1] → (1).
    ∴ Shortest distance = 5 miles
  2. Shortest distance from 1 to 3:
    (3)[30, 1] → (1)
    ∴ Shortest distance = 30 miles
  3. Shortest distance from 1 to 4:
    (4)[40, 3] → (3)[30, 1] → 1
    ∴ Shortest distance = 40 miles
  4. Shortest distance from 1 to 5:
    (5)[90, 3] → 3[30, 1] → 1
    or
    (5)[90, 4] → (4)[40, 3] → (3)[30, 1] → 2
    Shortest distance = 90 miles
    Shortest route is 1–3–5 (or) 1–3–4–5.

Applications of Shortest Route Problem

The following are three categories of applications of the shortest route problem:

  1. Minimise the total distance travelled.
  2. Minimise the total cost of a sequence of activities.
  3. Minimise the total time of sequence of activities.

Floyd’s Algorithm

Floyd’s algorithm is more general than Dijkstra’s because it determines the shortest route between any two nodes in the network. The algorithm represents an n-node network as an n × n square matrix. Each entry (i, j) of the matrix gives the distance dij from node i to node j and dij = ∞ if i is not linked directly to j.

Given three nodes i, j and k with connecting distances shown on the arcs (refer Fig. 13.68), it is shortest to reach k from i passing through j if

 

dij + djk < dik

FIGURE 13.68

In this case, it is optimal to replace the direct route from ik with the indirect route ijk. This triple operation exchange is applied systematically to the network using the following steps.

Step 0: Define the starting distance matrix D0 and node sequence matrix S0 as given below. The diagonal elements are marked with (−) to indicate that they are blocked. Set k = 1.

General step k: Define row k and column k as pivot row and pivot column. Apply the triple operation to each element in Dk– 1, for all i and j. If the condition dik + dkj < dij (ik, jk, and ij) is satisfied, make the following changes:

  1. Create Dk by replacing dij in Dk– 1 with dik + dkj.
  2. Create Sk by replacing Sij in Sk– 1 with k. Set k = k + 1 and repeat step k.

After n steps, we can determine the shortest route between nodes i and j from the matrices Dn and Sn using the following rules:

  1. From DN, dij gives the shortest distance between nodes i and j.
  2. From Sn, determine the intermediate node k = Sij, which yields the route ikj.

If Sik = k and Skj = j, stop; all the intermediate nodes of the route have been found. Otherwise, repeat the procedure between nodes i and k, and nodes k and j.

Example 1

Find the shortest routes between every two nodes, in the network given in Fig. 13.69. The distances (in miles) are given on the arcs. Arc (3, 5) is directional so that no traffic is allowed from node 5 to node 3. All other arcs allow traffic in both directions:

FIGURE 13.69

Solution:

Iteration 0

The matrices D0 and S0 give the initial representation of the network. D0 is symmetric except that d53 = ∞ because no traffic is allowed from node 5 to node 3.

Iteration 1

Pivot row—First row

Pivot column—First column (indicated by arrows → and ↓ in D0)

The double boxed elements, d23 and d23, are the only ones that can be improved by the triple operation. Thus to obtain D1 and S1 from D0 and S0:

  1. Replace d23 with d21 + d13 = 3 + 10 = 13 and set S23 = 1.
  2. Replace d32 with d31 + d12 = 10 + 3 = 13 and set S32 = 1.

Iteration 2

Set k = 2, as shown by the arrow in D1. The triple operation is applied to the boxed elements in D1 and S1 and these changes are incorporated in D2 and S2.

Iteration 3

Set k = 3, as shown by the shaded column in D2. The new matrices are given by D3 and S3.

Iteration 4

Set k = 4, as shown by the arrows in D3. The new matrices are given by D4 and S4.

Iteration 5

Set k = 5, as shown by the shaded row and column in D4. No further improvements are possible in this iteration. From D4 and S4 we can determine the shortest route between any two nodes in the network. For example, the shortest distance from node 1 to node 5 is d15 = 12. To find the shortest route we recall that a segment (i, j) represents a direct link only if Sij = j. Otherwise i and j are linked through at least one other intermediate node. Since S24 = 4 and S45 = 5, the route is initially given as 1 → 4 → 5. Now since S14 ≠ 4, the segment (1, 4) is not a direct link. Since S14 = 2 and S24 = 4, the route is replaced with 1 → 2 → 4. Because S12 = 2 and S24 = 4 no further intermediate nodes exist. Thus, the optimal route is 1 → 2 → 4 → 5 and the length of the route is 12 miles.

EXERCISES

Section 13.2

Construct the network for each of the projects whose activities and their precedence relationships are as given below:

 

1.

2. A < C, D, I; B < G, F; D < G, F, F; F < H, K, G, H < J, I, J, K < E

3. A, B, C can start simultaneously A < F, E; B < D, C, E, D < G

4.

5. A < C, D; B < C, D; C < E; D, E < F

6. A < C, D, B < E; C, E < F, G; D < H, G < I; H, I < J

7.

8. Draw the network for the project whose activities with their predecessor relationships are given below:

9. Draw the network for the project whose activities with their predecessor relationships are given below:
A, C, D can start simultaneously; E > B, C; F, G > D, H, I, > E, F; J > I, G; K > H; B > A.

10. Construct the network for the project whose activities and their relationships are as given below: Activities: A, D, E can start simultaneously; B, C > A; G, F > D, C; H > E, F

11. Draw the network for the project whose activities and their precedence relationships are as given below:

12. Construct the network of the project whose precedence relationships are given below:
B < E, F; F < G; C < G, L; E, G < H, L, H < I; L < M; H, M < N, H < J; I, J < P; P < Q.

13. Construct the network diagram comprising activities B, C, …, Q and N such that the following constraints are satisfied:
B > E, F; C < G, L; E, G < H; L, H < I, L < M; H < N; H < J; I, J < P; P < Q. The notation X < Y means that the activity X must be finished before Y can begin.

14. Listed in the Table are the activities and the sequence necessary for a maintenance job on heat exchangers in a refinery:

15. Construct the arrow diagram comprising activities A, B, … and L such that the following relationships are satisfied:

  1. A, B and C, the first activities of the project, can start simultaneously.
  2. A and B precede D.
  3. B precedes E, F and H.
  4. F and C precede G.
  5. E and H precede I and J.
  6. C, D, F and J precede K.
  7. K precedes L.
  8. I, G and L are the terminal activities of the project.

16. A publisher has a contract with an author to publish a textbook. The (simplified) activities associated with the production of the textbook are given. Develop the associated network of the project.

17. An assembly is to be made from two parts X and Y. Both parts must be turned on a lathe and Y must be polished whereas X need not be polished. The sequence of activities together with their predecessors are given below:

Activity Description Predecessor activity
A Open work order
B Get material for X A
C Get material for Y A
D Turn X on lathe B, C
E Turn Y on lathe E
F Polish Y D, F
G Assemble X and Y G
H Pack  

Draw a network diagram for the project

18. Draw a network diagram from the following list of activities:

19. A new type of water pump is to be designed for an automobile. Its major specifications are given in the Table.

Activity Description Predecessor activity
A Drawing prepared and approved
B Cost analysis A
C Tool feasibility(economics) A
D Tool manufactured C
E Favourable cost B, C
F Raw material procured D, E
G Sub–assemblies ordered E
H Sub–assemblies received D, F
I Parts manufactured I, H
J Final assembly J
K Testing and shipment  

Draw the arrow diagram of activities of the project.

20. Draw the network for jobbing production and indicate the critical path from the following:

Section 13.3

21. Draw the network diagram for the following activities and find the critical path and total float.

Job Job time (days) Immediate predecessors
A 13
B 8 A
C 10 B
D 9 C
E 11 B
F 10 E
G 8 D, F
H 6 E
I 7 H
J 14 G, I
K 18 J

[Answer: Critical path is A–B–E–F–G–J–C and the project duration is 82 days. Total float:

22. An architect has been awarded a contract to prepare plans for an urban renewal project. The job consists of the following activities and their estimated times:

  1. Draw an arrow diagram for this project.
  2. Indicate the critical path, and calculate the total and free float for each activity.

[Answer: Critical path is A–D–F–G and project duration: 8 days.]

23. The following maintenance job is to be performed periodically on the heat exchangers in a refinery:

  1. Draw an arrow diagram for his project.
  2. Identify the critical path. What is its length?
  3. Find the total float and free float for each task.

[Answer: Critical path is A–B–C–F–H–I–J; project duration = 8 days.]

24. A project consists of a series of tasks labeled A, B, …, H, I with the following relationships (W < X, Y means X and Y cannot start until W is complete; X, Y < W means W cannot start until both X and Y be complete). With this notation construct the network diagram having the following constraints

 

A < D, E; B, D < F; C < G; B, G < H, F, G < I

Also, find the minimum time of completion of the project, when the time (in days) of completion of each task is as follows:

[Answer: Project duration is 67 days.]

25. A small project consists of 7 activities for which the relevant data are given below:

  1. Draw the network and find the project completion time.
  2. Calculate total float for each of the activities.
  3. Draw the time scaled diagram.

[Answer: Project duration is 20 days. Total float is as follows

26. The following are the details of estimated time of activities of a certain project.

  1. Find the critical path and the expected time of the project.
  2. Calculate the earliest start and earliest finish time for each activity.
  3. Calculate the slack for each activity.

[Answer: Critical path : A–C–D–F

27. The following Table gives the activities in a construction project and the time duration:

  1. Draw the activity network of the project.
  2. Find the total float and free float for each activity.
  3. Determine the critical path and the project duration.

[Answer: Critical path: 1–2–3–4–5; project duration: 45 days

28. Determine early start (TEi) and late start (TLi) in respect of all the node points and identify the Critical path in respect of the following network.

[Answer: Critical paths are:

  1. 1–2–5–8–10
  2. 1–2–5–7–10.]

29. Find the critical path and calculate the slack time of each event for the following PERT diagram.

[Answer: Critical path is 1–3–5–9; project duration is 15 days. Slack time is as follows:

30. Tasks A, B, C, …, H, I constitute a project. The notation X < Y means that the task X must be finished before Y can begin. With this notation A < D, A < E, B < F, D < F, C < G, C < H, F < I, G < I, draw a graph to represent the sequence of tasks and find the minimum time of completion of the project when the time (in days) of completion of each task is as follows:

[Answer: Critical path is A–D–F–I. The minimum time to complete the project is 44 days.]

31. Given the following information:

  1. Draw the arrow diagram.
  2. Identify the critical path and find the total project duration.
  3. Determine total, free and independent floats.

[Answer: Critical path is 0–1–3–6–7. Project duration = 27 days

32. Calculate the total float, free float and independent float for the project whose activities are given below.

33. Construct the network for the project whose activities are given below and compute the total, free and independent float of each activity and hence determine the critical path and project duration.

[Answer: Crititical path is 0–1–3–6–7 and the project duration = 31 weeks.

34. A small maintenance project consists of the following 10 jobs. The precedence relationships are identified by their node numbers:

  1. Draw an arrow diagram representing the project.
  2. Calculate early and late start and finish times for each job.
  3. Which jobs are critical?
  4. How much slack does job (3, 5) have?

[Answer: Critical jobs are (1, 2), (2, 4) (4, 6) and (6, 8) and the slack of (3, 5) is 3 days.]

35. Draw the network for the data given below and compute:

  1. Critical path
  2. Early start and late start times for each activity
  3. Total slack for each activity

[Answer: Critical path C–E–I; project duration = 22 weeks

36. Draw the network for the following project and compute the earliest and latest times for each event and find the critical path.

[Answer: Critical path: 1–2–4–6–7–8

37. A project schedule has the following characteristics

Construct PERT network and find the critical path.

[Answer: Critical path is 1–3–5–7–8–10 and the project duration = 22 days.]

38. Draw the network and determine the critical path for the given data:

Find the total, free and independent floats of each activity.

[Answer: Critical path is 1–2–4–5–6; project duration is 31 days.

39. What are the different types of floats associated with an activity in a CPM model? What are their uses?

40. The following refers to a project network:

  1. Draw the network.
  2. Determine the critical and project completion time
  3. Draw the graph showing optimum requirements versus time.

[Answer: The critical paths are A–D–G–H–I and A–E–F–H–I and the project duration is 10 days.]

41. A maintenance activity consists of the following jobs. Draw the network for the project and calculate the total float and free float for each activity.

42. A network consists of 9 cities A, B, C, … to I, as nodes. The arc length data given below represents the amount of cable to be laid for establishing telephone links between the nodes. It is required to lay cable lines in such a manner that any node can connect to any other node (if necessary through another node) such that the total cable laid is minimum. Determine between what nodes the cable lines should be laid:

AB = 30,

BC = 15,

CD = 30,

AC = 45,

BE = 22,

CF = 23,

AD = 60,

BF = 22,

DF = 15,

DG = 38,

EF = 7,

EH = 15,

FH = 23,

EI = 60,

GI = 15,

HI = 45,

GH = 15,

[Answer: Cable lines must be laid by connecting the cities in the following order:

A-B-C-D-E-F-I-H;

A-C-D-F-I-H.]

43. Draw the network diagram for the following activities and find critical path and total float of each activity.

[Answer: Critical path is 1–2–3–5–6–8–9–10

44. Define an activity, event and dummy constraints in a PERT network, Using the following information plot a network, determine the critical path and compute slack for all events.

If the duration of activity 5-6 is increased to 6 and for activity 3-6 is reduced, with will be the new critical path?

Section 13.4

45. A project consists of the following activities and the time estimates:

  1. Draw the network.
  2. What is the probability that the project will be completed in 27 days.

[Answer: (a) Critical path:1–4–7; project duration is 25 days; (b) Required Probability = 0.6368.]

46. The following indicates the details of a project. The durations are in days; ‘a’ refers to optimistic time, ‘m’ refers to most likely time and ‘b’ refers to pessimistic time duration.

  1. Draw the network.
  2. Find the critical path.
  3. Determine the excepted standard deviation of the completion time.

[Answer: The critical path is 1–2–4–5. The expected standard deviation of the completion time = 1.09 (nearly).]

47. (a) One of the activities in a PERT project has an expected duration of 12 weeks with a standard deviation of 2 weeks, the most likely time estimate of this activity is 12 weeks. Calculate the optimistic and pessimistic time estimates for this capacity.

(b) Consider the following project.

Find the path and a standard deviation. What is the probability that the project will be completed by 18 weeks?

[Answers: (a) tp = 18 weeks, to = 6 weeks
(b) Critical path: A–C–F, s = 1.37
Prob. (completing in 18 weeks) = 0.928.]

48. A civil engineering firm has to bid for the construction of a dam. The activities and time estimates are given in next page:

The policy of the firm with respect to submitting bids is to bid the minimum amount that will provide a 95% probability of at best breaking even. The fixed costs for the project are 8 lakhs and the variable costs are 9,000 every day spend working on the project. The duration is in days.
    What amount should the firm bid under this policy? (you may perform the calculations on duration, etc. up to two decimal places.)

[Answer: Critical path is 1-2-3-5-7-9 and the project duration = 77.49 days.

Amount of bid = 8 lakh + 9,000 × 86]
= 15, 74,000.]

49. A construction company is preparing a PERT network for laying the foundation of a new art museum. Given the following set of activities, their predecessor requirements and three time estimates of completion time.

  1. Draw the PERT network.
  2. Compute the slack for each activity and determine the critical path.
  3. The contract specifies a 5,000 per week penalty for each week the completion of the project extends beyond 37 weeks. What is the probability that this company will have to pay a maximum penalty of 15,000?

[Answer:

(ii)

(iii) 93% probability of paying a maximum penalty of 15,000.]

50. Assuming that the expected times are normally distributed, find the probability of meeting the schedule date as given for the network.

Schedule project completion date is 30 days. Also, find the date on which the project manager can complete the project with a probability of 0.90.

[Answer: Required probability = 0.71 or 0.81]

51. In the network shown in Figure the three time estimates for the activities are indicated. Number the events according to Fulkerson’s rule and calculate the variance and expected time for each activity.

52. A project has the following characteristics

Construct a PERT network. Find the critical path and variance for each event. Find the project duration at 95% probability.

[Answer: Critical path is 1–2–4–6–7–9–10.]

53. For the project

Find the earliest and latest expected times to each event and also the critical path of the network.

[Answer: Critical path is A–C–E–H–K.]

54. A small project consists of 7 activities, the details of which are given below.

  1. Draw the network, number of nodes, find the critical path, the expected project completion time and the next most critical path.
  2. What project duration will have 95% confidence of completion.

[Answer: Critical path A–B–D–F. Expected project duration is 27 days. Next critical path A-B-D-G with a duration of 25 days. Project duration which has 95% probability of completion if Z = (1.64) = or T1 = 1.64 × + 27 = 34 days.]

55. A sociologist plans a questionnaire survey consisting of the following tasks:

  1. For this PERT network find the expected task duration and the variance of task durations.
  2. Draw a network for this project and find the critical path. What is the expected length of the critical path? What is the variance of the length of the critical path?
  3. What is the probability that the length of the critical path does not exceed 60 days?

56. A project has the following activities and other characteristics:

  1. Draw the PERT network diagram.
  2. Identify the critical path.
  3. Prepare the activity schedule for the project.
  4. Determine the mean project completion time.
  5. Find the probability that the project is completed in 36 weeks.
  6. If the project manager wishes to be 99% sure that the project is completed on 30 May 2004, when should he start the project work?

57. The owner of a fastfood restaurant chain is considering a new computer system for accounting and inventory control. A computer company has sent the following information about computer system installation:

  1. Construct an arrow diagram for this problem.
  2. Determine the critical path and the expected completion time.
  3. Determine the probability of completing the project in 55 days.

58. Consider a project having the following activities and time estimates:

  1. Draw an arrow diagram for the project.
  2. Compute the excepted project completion time.
  3. What should be the due date to have 0.90 probability of completion?
  4. Find the total float and free float (both early and late) for all non-critical activities.

59. The following Table lists the jobs of a network along with their time estimates.

  1. Draw the network.
  2. Calculate the length and variance of critical path.
  3. Find the probability that the project will be completed within 30 days.

60. The following Table lists the jobs of a network with three time estimates:

  1. Draw the project network.
  2. What is the approximate probability that the jobs on the critical path will be completed by of 42 days?

61. The data for a small PERT project is as given below where a represents optimistic time, m most likely time and b pessimistic time estimates of the activities A, B, …, J, K.

Precedence relationships: A, B, C can start immediately. A < D, I; B < G, F; D < G, F; C < E; E < H, K; F < H, K; G, H < J.
    Draw the arrow network of the project. Calculate earliest and latest expected time to reach each node, and find the critical path. What is the probability that the project will be completed 2 days later than excepted?

62. The three estimates for the activities of a project are given below:

Draw the project network. Calculate the total slack and free slack of each activity. Find out the critical path of the project and project duration. What is the probability that the project will be completes at least 5 days earlier than expected? What is the probability of completing the project on or before 22 days?

63. Consider a project consisting of 7 jobs A, B,…G with the following precedence relations and time estimates.

Draw the project network and find the probability of completing the project in 30 days.

Section 13.5

64. The following Table gives the activities in a construction project and other relevant information.

Fixed-cost data for the different project durations are given below:

  1. Draw a PERT network for the project.
  2. Determine the project duration which will result in minimum total project cost.

65. The following is a Table showing details of a project:

Indirect cost is 400 per day. Find the optimum duration and the associated minimum project cost.

     [Answer: The optimum duration is 19 weeks and the associated minimum cost is 1,32,200.]

66. The activities of a project are tabulated below with immediate predecessor and normal crash time cost.

  1. Draw the network corresponding to the normal time.
  2. Determine the critical path and the normal duration and cost of the project.
  3. Suitably crash the activities so that the normal duration may be reduced by 3 days at minimum cost. Also, find the project cost for this shortened duration if the indirect cost per day is 25.

67. The time and cost estimates and precedence relationship of the difference activities constituting a project are given below:

  1. Draw a project network diagram and find the critical path.
  2. If a dead line of 17 weeks is imposed for completion of the project, what activities will be crashed, what would be the additional cost and what would be critical activities of the crashed network after crashing?

68. The Table below shows jobs, their normal time and cost time and cost for a project.

Indirect cost for the project is 300 per day.

  1. Draw the network for the project?
  2. What is the normal duration cost of the project?
  3. If all activities are crashed, what will be the project duration and corresponding cost?
  4. Find the optimum duration and minimum project cost.

[Answer: The normal duration is 20 days. Minimum total cost is 5,350 and the optimum duration of the project is 17 days.]

69. The following Table gives the activities in a construction project and other relevant information.

  1. Draw the activity network of the project.
  2. Find the total and free float of each activity.
  3. Using the above information, crash or shorten the activity step by step until the shortest duration is reached.

[Answer: Normal duration of the Project = 45 days.]

Minimum duration of the project is 42 days with a cost of 2,220.]

70. In the project network shown in Figure the nodes are denoted by numbers and the activities by letters. The normal and crash durations of the various activities along with the associated costs are shown below:

Determine the least cost 36 days schedule.

[Answer: The least cost for 36 days is 12,200.]

71. The following time-cost table (time in days, cost in rupees) applies to a project. Use it to arrive at the network associated with completing the project in minimum time at minimum cost.

[Answer: The minimum durations is 7 days with associated cost as 11,800.]

72. A maintenance foreman has given the following estimate of time and cost of jobs in a maintenance project:

Overhead cost is Rs 25 per hour. Find

  1. the normal duration of the project and associated cost.
  2. the minimum (optimum) duration of the project and associated cost.
  3. the least duration of the project and its cost.
  4. if all the activities are crashed what will be the project duration and the corresponding cost.

73. The following Table gives data on normal time-cost and crash time cost of a project.

The indirect cost per day is 100.

  1. Draw the network and identify the critical path.
  2. What is the normal project duration and the associated cost?
  3. Crash the relevant activities systematically and determine the optimum project completion time and cost.

[Answer: Critical path is 1–2–4–6–7 and the normal project duration is 22 days with an associated cost of 6,900. The optimum project duration is 13 days with an associated cost of 11,750]

74. A small project has 7 activities. The relevant data about these activities is given below:

  1. Find out the normal duration and the minimum duration?
  2. What is the percentage increase in cost to complete the project in 21 days?

[Answer: The normal duration to complete the project is 25 days. The minimum duration is 21 days and the associated cost is 5,100. The percentage increase in cost to complete the project in 21 days is 13.3%.]

75. The Table below provides cost and gives estimates of 7 activities of a project:

  1. Draw the project network corresponding to normal time.
  2. Determine the critical path and the normal durations and normal cost of the project.
  3. Crash the activities so that the project completion time reduces to 9 weeks, with minimum additional cost.

[Answer: Project duration = 16 weeks and the associated normal cost = 82,000. After crashing the project duration reduces to quiet by incurring a total additional costs of 36,000.]

76. The following Table gives data on normal and crashed time and cost for a project.

Find the optimum project time and corresponding minimum total project cost by crashing appropriate activities in proper order. Show the network on time-scale at each step. The indirect cost per day is 400.

[Answer: Optimum project duration = 27 days, minimum total cost = 19,750]

77. Find the optimum schedule for the given project, with overhead cost of 75 per day.

  1. Draw the project network using normal duration.
  2. Find the path and the project duration for case (i).
  3. Find the optimal schedule and optimal project duration.

[Answer: Optimum project duration: 12 days with min. cost = 1,760]

78. The required data for a small project consisting of different activities are given below:

  1. Draw the network and find out the normal project length and minimum project length.
  2. If the project is to be completed in 21 days with minimum crash cost, which activities should be crashed by how many days?

[Answer: Project duration = 26 days and the minimum length = 21 days.

Crash activities: A by 1 day, G by 2 days, H by 2 days, C by 2 days and D by 2 days; total additional cost for project duration of 21 days is 1,233,33.]

79. Suggest optimal crashing schedule for the following project:

Section 13.6

80. Consider the network shown below:

The critical path is 1–2–3–4–5–6 and the project duration time is 24 days. At the end of 15th day, a review of the existing conditions is made and the observations are listed below:

  1. Activities 1–2, 2–3 and 2–4 are already complete.
  2. Activity 3–5 is in progress since last 2 days and needs 6 more days for completion.
  3. Activity 3–4 is in progress since last 2 days and needs 2 more days for completion.
  4. Activity 4–5 can be completed in 3 days as against originally planned 4 days.
  5. Activity 5–6 needs 4 days for completion.

Formulate a new project based on the reviews at the end of 15 days.

81. A project has the following activities and durations.

  1. Draw the network of the project and find its duration.
  2. At the end of 25 days it is observed that
    1. activities 12, 13, 14 have been completed.
    2. activity 24 is being done and will be completed in 5 more days.
    3. activity 36 is in progress and will need 20 more days for completion.
    4. activity 67 is presenting some problem and will take 15 days.

Draw the updated network and find out its revised duration. 12 denotas activity 1–2 and same is true for other activities.

Section 13.7

82. The manpower required for each activity of a project is given in the following Table.

The contractor stipulates that for the first 26 days only 4 to 5 men and during the remaining days 8 to 11 men are available. Find whether it is possible to rearrange the activity suitable for leveling the manpower resources satisfying the above condition.

83. Following are the manpower requirements for each activity in a project.

Activity Normal time Manpower required
0–1 2 4
1–2 3 3
1–3 4 3
2–4 2 5
3–5 4 3
3–6 3 4
4–7 6 3
5–7 6 6
6–8 5 2
7–9 4 2
8–9 4 9
  1. Draw the network diagram of the project activities.
  2. Rearrange the activities suitably for reducing the existing total manpower requirement.
  3. If only 9 men are available for the execution of the project, then rearrange the activities suitably for levelling the manpower resource.

84. Following are the manpower requirements for each activity in project

Activity Normal time (days) Manpower required per day
1–2 10 2
1–3 11 3
2–4 13 4
2–6 14 3
3–4 10 1
4–5 7 3
4–6 17 3
5–7 13 5
6–7 9 8
7–8 1 11
  1. Draw the network and find out total float and free float for each activity.
  2. The contractor stipulates that during the first 26 days only 4 to 5 men and during the remaining days 8 to 11 men only can be made available. Rearrange the activities suitable for leveling the manpower resources, satisfying the above conditions.

85. The activities, activity durations and manpower requirements of a project are given below:

Activity Duration (days) No. of men required
1–2 2 5
1–3 2 4
1–4 0 0
2–5 2 2
2–6 5 3
3–7 4 6
4–8 5 2
5–9 6 8
6–9 3 7
7–8 4 4
8–9 6 3

There are eleven persons who can be employed for this project. Carry out appropriate manpower levelling so that the fluctuations of workforce requirement from day to day are as small as possible.

86. The activity comprising a certain project have been identified as follows:

  1. For the above project, draw the network. Determine the critical path and its duration.
  2. If there were only three men available at any one time, how long would the project take and how would you allocate the men to the activities?
  3. If there were no restrictions on the amount of labour available explain how you might schedule the activities.

87. A project consists of 10 activities, each of which requires either, or both, of the two types of resources R1 and R2 for its performance. The duration of the activities and their resources requirements are as follows:

Resource availability: 7 units of R1 and 5 units R2. Determine the duration of the project under the gives resource constraints. If the resources were not a problem, how long would the project take to complete in the normal course?

88. A project consists of 9 activities. The Table below shows the duration for each activity and the corresponding labour requirements. Draw a network and establish the critical path.
      Also, draw a square network assuming that all the activities begin at the earliest start time. Adjust the project work such that there will be smooth demand for the resources.

Activity Duration No.of labourers
1–2 3 5
2–4 2 3
2–3 3 7
3–4 0 0
3–5 3 2
4–5 7 2
3–6 2 1
5–6 6 6
4–6 3 5

89. The following data is given for a small project:

  1. Draw the PERT chart.
  2. Indicate the critical path without taking account of resource constraint.
  3. Give the bar diagram on time-scaled network.
  4. From the time-scaled chart given in (c) prepare a resource a aggregation profile.
  5. Now, prepare a resource allocation profile with 2 men constraint and another diagram for 5 days constraint.

Section 13.8

 

90. Determine the maximal flow in each arc for the following network.

91. Determine the maximal flow from source O to sink T for the following network.

92. Find the maximum flow from source A to sink D, through the network given below.

93. Find the maximum flow of oil from location 1 to location 5 using a linear programming model.

Section 13.9

 

94. The Midwest TV cable company is in the process of providing cable service to five new housing development areas. The following figure depicts the potential TV linkages among the five areas. The cable miles are shown on each branch. Determine the most economical cable network.

95. Determine the minimal spanning tree of the network given in problem 95, under each of the following separate conditions:

  1. Node 5 and 6 are linked by a 2-mile cable.
  2. Nodes 2 and 5 cannot be linked.
  3. Nodes 2 and 6 are linked by a 4-mile cable.
  4. The cable between nodes 1 and 2 is 8 miles long.
  5. Nodes 3 and 5 are linked by a 2-mile cable.
  6. Node 2 cannot be linked directly to nodes 3 and 5.

96. In intermodel transportation, loaded track trailers are shipped between railroad terminals by placing the trailer on special flatbed carts. The following network shows the location of the main railroad terminals in the United States and the existing railroad tracks. The objective is to decide which tracks should be revitalised to handle the intermodal traffic. In particular, the Los Angeles (LA) terminal must be linked directly to Chicago (CH) to accommodate the anticipated heavy traffic between the two locations. Other than that, all the remaining terminals can be linked directly or indirectly such that the total length (in miles) of the selected tracks is minimised. Determine the railroad tracks that must be included in the revitalisation programme.

97. Find the minimum spanning tree of the network given below:

98. Consider the details of a distance network as shown below:

  1. Construct the distance network.
  2. Find the minimum spanning tree.

Section 13.10

 

99. Determine the shortest route between node 1 and every other node in the network given below:

100. Find the minimum cost path connecting A and L in the network given below:

101. Apply Dijkstra’s algorithm to find the shortest route from s to t in the graph given below:

102. Apply Floyd’s algorithm to the network given below. Arcs (7, 6) and (6, 4) are unidirectional, and all the distances are in miles. Determine the shortest route between the following pairs of nodes.

  1. From node 1 to node 7
  2. From node 7 to node 1
  3. From node 6 to node 7

103. ABC mobile phone company services six geographical areas. The satellite distances (in miles) among the six areas are given in the following figure. ABC needs to determine the most efficient message routes that should be established between each two areas in the network.