Question

write a four pages essay on analyzing networks?

this is for Linear Algebra.

Answer 1

Meaning of Network Analysis:

Network analysis has played an important role in field of engineering. Application of network analysis have been made in information theory, study of transportation problem and planning and control of research and development projects.

In transportation problem, there are member of routes to reach a terminal, but we like to choose a route for which the cost or time is minimum. There is a problem to select the shortest route through a network. Thus the problem of network analysis is to find a course of action, which minimize some measure of performance.

A project consists of no. of interrelated activities which must be executed in specific order to complete the project. The activities are interrelated in a logical sequence In such a way that some activities cannot start until some others are compiled.

These activities require time and consumption of resources like labour, money, material and machine etc. The main objective before starting any project is to schedule the required activities is an efficient manner so as to complete it-on or before a specified time limit at minimum cost of its completion.

The techniques of O.R. which are used for planning, scheduling and controlling large and complex projects are termed as network analysis or network techniques. These techniques are based on the representation of the project as a network of activities.

A network is essentially a graphical plan consisting of a certain configuration of arrows and nodes for showing the logical sequence of various activities to be performed to complete the project.

Basic Concepts of Network Analysis:

i. Activity:

All projects may be viewed as being composed of operations or tasks called activities, which require the expenditure of time and resources for their accomplishments. An activity is depicted by a single arrow (→) on the project network. The activity arrows are called arcs. The activity arrow is not scaled, the length of the activity time is only a matter of convenience and clarity and does not represent importance of time.

The head of the arrow shows the sequence or flow of activities. An activity cannot begin until the completion of the preceding activities. It is important that activities be defined so that beginning and end of each activity can be identified clearly.

Generally, there are three types of activities are found in a network, which are:

a. Predecessor activity:

An activity which must be completed before one or more other activities start is known as predecessor activity.

b. Successor activity:

Activity that cannot be started until one or more of the other activities are completed, but immediately succeed them are called successor activities.

c. Concurrent activity:

Activities which can be accomplished concurrently are known as concurrent activities.

d. Dummy activity:

An activity which does not consume any kind of resource and/ or time is known as dummy activity.

A dummy activity is added in a network only to establish the given precedence relationship among other activities of project in following two situations:

(a) When two or more parallel activities in a project have same starting and finishing points.

(b) When two or more activities have some (but not all) of their immediate predecessor activities in common

A dummy activity is generally shown by a dotted line in network diagrams:

ii. Event:

An event in a network diagram is a specific instant of time which marks the start, or the end of an activity. Event consumes neither time nor resources. It is represented by a circle and the event number is written within the circle. The event circles are called nodes. Therefore, the major difference between activities and events is that activities represent the passage of time whereas events are points in time

All activity arrows must begin and end with event nodes as shown below:

The events can be further classified into following three categories:

a. Merge Event:

An event which represents the joint completion of more than one activity is known as merge event.

b. Burst Event:

An event which represents the beginning of more than one activity is known as burst event.

c. Merge and Burst Event:

An event may be merged for some activities and burst for some other activities simultaneously.

Techniques in Network Analysis:

The most commonly used network techniques are:

1. Critical Path Method (CRM).

2. Programme Evaluation and Review Technique (PERT).

i. Critical Path Method (CPM):

CPM method developed by E.I. du pont de Nemours Company (USA) in 1958 and named as critical path method (CPM) to schedule and control the project. CPM is applicable to both large and small projects, taking from space programmes to wedding or horse shows.

It is widely recognized and is the most versatile and potent management planning techniques. The objective of critical path analysis is to estimate the total project duration and to assign starting and finishing times to all activities involved in the project.

This method involves following steps:

1. Break down the project into various activities systematically. Label all activities. Arrange all the activities in logical sequence. Construct the network diagram.

2. Number all the nodes (events) and activities. Find the time for each activity considering it to be deterministic. Indicate the activity times on the arrow diagram.

3. Calculate earliest start time, earliest finish time, latest start time and latest finish time. Tabulate activity normal times, earliest times and latest times.

4. Determine the total float for each activity by taking difference between the earliest time and latest time for each node.

5. Identify the critical activities (the activities with zero float) and connect them with the beginning node and the ending node in the network diagram by double line arrow. This gives the critical path.

6. Calculate the total project duration.

7. It is intended to reduce the total project duration, crash the critical activities of the network.

8. Optimize the cost.

9. Update the network and smooth the network resources.

Time Estimate in CPM:

The basic objective of the time analysis is to get a planned schedule of the project for which the following factors should be known:

(i) Total completion time of the project.

(ii) Earliest time when each activity can begin.

(iii) Latest time when each activity can be started without delaying the total project.

(iv) Float for each activity i.e., amount of time by which the completion of an activity can be delayed without delaying the total project completion time.

(v) Identification of critical activities and critical path.

The basic scheduling computations can be grouped into the following heads:

1. Forward pass method (For Earliest event time):

Based on fixed occurrence time of the initial network event, the forward pass computation yields the earliest start and earliest finish times for each activity and indirectly the earliest expected occurrence time for each event.

This consists of the following steps:

1. The computation begin from the start node and move to the ‘end’ node. To accomplish this, the forward pass computations start with an assumed earliest occurrence time of zero for the initial project event.

i.e. E1 = ; i = 1

2. Calculate earliest start time for each activity which begins at event i. This is equal to the earliest occurrence time of event i (Tail event) i.e., ESij = Ei for all activity (i, j) starting from event i.

3. Calculate earliest finish time of each activity (I, j) which is the earliest start time of the activity plus the duration of the activity, i.e.

EFij = ESij + tij

= Ei + tij

4. Calculate earliest occurrence time for event j (J > i) which is the maximum of the earliest finish times of all activities ending into that event, i.e.

Ej = Maximum (ESij + tij)

= Max [Ei + tij]

The computed values are put into the lower left portion of each event.

2. Backward pass method (For latest allowable time):

In this method calculation begin from last event L.

The various steps are as follows:

1. Set the latest occurrence time of last event L which is equal to the earliest occurrence time of that event obtained from forward pass method.

i.e., Assume L = E for ending event.

2. Latest finish time for activity (i,j) equal to the latest event time of event j, i.e., LFij = Li

3. Latest starting time of activity (i,j) is the latest completion time of (i,j) minus the activity time i.e.

LSij = LFij – tij

= Li – tij

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

Thus

Li = Minimum (LSij)

= Min (LFij – tij)

= Min (Lj – Lij)

The computed values are put into the lower right portion of each event.

CPM Systems:

Activity-On-Arrow (AOA) Network:

In this type of network representation activity is represented by an arrow. The tail of the arrow represents the start and the head of the arrow represents the end of the activity. The description of activity is written above the arrow. Events are represented by circles or nodes at the start and the end of an activity arrow.

These diagrams have a single starting node from which all activities with no predecessors may start. The diagram then move from left to right, ending with a single ending node, where all activities come together with no successor.

Advantages of AOA Network:

1. Many computer programmes are based on AOA network.

2. AOA diagrams give a better sense of the flow of time throughout a project.

3. AOA diagrams can be superimposed on a time scale with the arrow diagram, the correct length indicate the time requirement.

Activity-On-Node (AON) Network:

In AON networks, activities are represented by circles or nodes and arrows are used only to show the dependency relationship between the activity nodes. Generally these diagrams have no particular starting or ending node for the whole project. The lack of dummy activities in diagrams makes them easier to draw and understand.

Advantages of AON networks:

1. AON diagram does not require dummy activities.

2. They are easier to draw and understand.

3. They are easier to revise and update.

Comparison between the representation on AOA and AON networks:

Rules of AOA Network Construction:

Following rules have to be followed while constructing a network:

1. In network diagram arrow represents activities and circles the events. The length of arrow has no significance.

2. Each activity should be represented by only one arrow and must start and end in a circle called event. The tail of an arrow represents the start and head the completion of work.

3. The direction of arrow indicates the direction of work flow. The normal convention is to go from left to right.

4. All networks are constructed logically on the basis of principle of dependency.

5. An events cannot occur until all the incoming activities into it have been completed.

6. An activity cannot start until all the preceding activities have been completed.

7. No set of activities cannot form a circular loop.

Numbering the Events (Fulkerson’s Rule):

After the network is drawn in a logical sequence, every event is assigned a number. The number sequence must be such so as to reflect the flow of the network- A number is placed inside the circle. The rule devised by D.R. Fulkerson is used for numbering.

The procedure for applying this rule consists of identifying the initial event and then gradually converting the succeeding event by deleting the arrows from the previous preceding events. A number is assigned only when by such deletions, a node is converted into initial event. It involves the following.

Steps:

1. Event numbers should be unique.

2. Event numbering should be carried out on a sequential basis from left to right,

3. The initial event which has all outgoing arrows with no incoming arrow is membered as.

4. Delete all arrows emerging from all the numbered events. This will create at least one new start event out of the proceeding events.

5. Number all new start events 2, 3 and so on. Repeat this process until all terminal event without any successor activity is reached, Number the terminal node suitably.

Example:

Construct a network for the project whose activities and their precedence relationship are as given below:

Solution:

From the given constraint, it is clear that A.D are the starting activity and I the terminal activity. B, C are starting with the same event and are both the predecessors of the activity F. Also E has to be the predecessor of both F and H, Hence, we have to introduce a dummy activity.

D1 is the dummy activity.

Finally we have the following network:

ii. PERT Computation:

PERT (Programme Evaluation and Review Technique) was developed by a navy sponsored resource team composed of Messrs. D G. Malcolm, J.R. Roseboom, C.E. dark and W. Fazor in about 1950.

This is essentially a management technique and it tailored properly, can be used with advantage for responsibility accounting in addition to attaining other well defined objectives. It is a method in which we try to exercise logical discipline in planning and controlling projects.

PERT is designed for scheduling complex projects that involves many inter-related tasks. It improves the planning process because:

1. It forms the planner to define the projects various component activities and events logically.

2. It provides a basis for normal time estimates and yet allow for some measure of optimum or pessimism in estimating completion dates.

3. It shows the effects of changes to the overall plan as they contemplated.

4. It provides a built in means for on-going evaluation of the plan.

5. It facilitates the process of communication between planners management by either adhering organisational lines or crossing over them. In essence, PERT makes the clear cut assignment of responsibility possible.

After the project has been planned and its implementation is underway, PERT continues to be of use in controlling the project:

1. It provides all parties involved a common basis of progress reporting, both, within organisation and outside of it.

2. It identifies likely troubles pots before they are encountered.

3. It provides data specially tailored to each level of management.

4. It focuses management attention on the critical path, where it is most needed, as well as on other no-critical activities that finish resources essential to the completion of activities of the critical path.

5. It permits the effects of various reallocation alternatives to be simulated such that the impact of any proposed changes in the overall project can be predicted. In other words PERT answers ‘the what’ if questions.

Because of these planning and controlling features, PERT is especially effective in projects with many distinct tasks in which the complex inter relationships between tasks and projects with respect to personnel scheduling and time constraints are of critical importance.

PERT System of Three Time Estimates:

The main objective in the analysis through PERT is to find out the completion for a particular event within specified date. If yes, what are the chances of completing the job? The PERT approach takes into account the uncertainties. In this approach, three time values are associated with each activity of the optimistic value, the pessimistic value, and the most likely value. These three time values provide a measure of uncertainty associated with that activity.

1. The optimistic time:

This is the shortest possible time in which the activity can be finished. It assumes that everything goes very well. This is denoted by t0 or a.

2. Most likely Time (tm):

This is the most likely time as probably the actual time required to complete an activity. In this case it assumes that things go in the normal way, with a few delays or breakdown etc. this is denoted by tm or m.

3. Pessimistic time (tp):

This time is based on the assumption that everything will go badly. Thus, it is the maximum possible time required to perform an activity. However, this does not include major catastrophes like labour strikes, acts of God, and unrest. It is denoted by tp or b

4. Expected Time or Average Time (te):

In PERT activity duration is not a single time estimate, in fact a random variable which is characterized by some probability distribution usually β distribution. To estimate the parameters of β- distribution PERT uses three time estimates for each activity.

The optimistic time, most likely time and pessimistic time are combined statistically to develop the expected time (te) for an activity. The fundamental assumption in PERT is that the three time estimates form the end points and mode of Beta distribution.

According to β-distribution, we can get the expected time for an activity to complete by adding together 1/6th of the optimistic, 2/3rd of the most likely and 1/6″‘of the pessimistic time estimate.

5. Variance (σ2):

Variance for an activity is estimated on the basis of analogy to the normal distribution where 99% of the area under the normal curve lies within the ± 3σ from the mean or fall within the range approximately 6σ in length therefore, the interval (to, t) or range (to– tp) is assumed to enclose about 6σ of a symmetric distribution. Thus, if denote the standard deviation, then

PERT Algorithm:

The various steps involved in developing PERT network for analyzing any project are summarized below:

Steps 1:

1. Develop a list of activities that made up the project including immediate predecessors.

2. A rough PERT network is drawn on the basis of the three questions for each activity.

(i) Which activities precede this one?

(ii) Which activities follow this one?

(iii) Which activities are concurrent with this one?

Obviously, the first activity would be preceded by none and the last activity would be followed by none. During rough sketching such logical rules as insertion of dummies, activities should be straight, slanting or bent but not curved, etc., may be ignored.

3. The network is then suitably sketched to conform to rules and conventions.

4. Events are numbered in ascending order from left to right.

5. Time estimates for each activity are then obtained.

They are:

(i) The most likely estimate, m

(ii) Pessimistic estimate, a

(iii) The optimistic estimate, b

6. Then upon the assumption of beta distribution for the activity duration, the expected time, te for each activity is computed from the following formula:

7. Using the expected activity time estimates, determine the earliest start time and the earliest finish time for each activity, the earliest finish time for the complete project corresponds to the earliest finish time for the last activity.

8. After determining the latest start time and the latest finish time for each activity, compute the float associated with each activity, the critical path activities are the activities with zero float. Determine now the critical path through the given network.

9. Using the values for b and a which were determined in step 5.

Calculate the variance (σ2) of each activities time estimates by:

10. Use the variability in the activity times to estimate the variability of the project completion date, then using this estimate, compute the probability of meeting a specified completion date by using the standard normal equation.

Where Z = no of standard deviations the due date or target date lies from the mean or expected date.

Crashing or compressing the project may have to be undertaken if the critical path duration is not acceptable to the management or resource allocation may have to be performed if resources are limited.