Networks PDF

MBA-H2040 Quantitative Techniques for Managers UNIT III NETWORK PROBLEMS Introduction A network consists of several destinations...

MBA-H2040 Quantitative Techniques for Managers UNIT III NETWORK PROBLEMS Introduction A network consists of several destinations or jobs which are linked with one another. A manager will have occasions to deal with some network or other. Certain problems pertaining to networks are taken up for consideration in this unit. LESSON 1 SHORTEST PATH PROBLEM LESSON OUTLINE  The description of a shortest path problem.  The determination of the shortest path. LEARNING OBJECTIVES After reading this lesson you should be able to - understand a shortest path problem - understand the algorithm for a shortest path problem - work out numerical problems THE PROBLEM Imagine a salesman or a milk vendor or a post man who has to cover certain previously earmarked places to perform his daily routines. It is assumed that all the places to be visited by him are connected well for a suitable mode of transport. He has to cover all the locations. While doing so, if he visits the same place again and again on the same day, it will be a loss of several resources such as time, money, etc. Therefore he shall place a constraint upon himself not to visit the same place again and again on the same day. He shall be in a position to determine a route which would enable him to cover all the locations, fulfilling the constraint. The shortest route method aims to find how a person can travel from one location to another, keeping the total distance traveled to the minimum. In other words, it seeks to identify the shortest route to a series of destinations. EXAMPLE Let us consider a real life situation involving a shortest route problem. A leather manufacturing company has to transport the finished goods from the factory to the store house. The path from the factory to the store house is through certain 196 MBA-H2040 Quantitative Techniques for Managers intermediate stations as indicated in the following diagram. The company executive wants to identify the path with the shortest distance so as to minimize the transportation cost. The problem is to achieve this objective. 95 Store house 2 4 Factory 40 40 35 65 70 6 40 1 100 5 20 3 Linkages from Factory to Store house The shortest route technique can be used to minimize the total distance from a node designated as the starting node or origin to another node designated as the final node. In the example under consideration, the origin is the factory and the final node is the store house. STEPS IN THE SHORTEST ROUTE TECHNIQUE The procedure consists of starting with a set containing a node and enlarging the set by choosing a node in each subsequent step. Step 1: First, locate the origin. Then, find the node nearest to the origin. Mark the distance between the origin and the nearest node in a box by the side of that node. In some cases, it may be necessary to check several paths to find the nearest node. Step 2: Repeat the above process until the nodes in the entire network have been accounted for. The last distance placed in a box by the side of the ending node will be the distance of the shortest route. We note that the distances indicated in the boxes by each node constitute the shortest route to that node. These distances are used as intermediate results in determining the next nearest node. SOLUTION FOR THE EXAMPLE PROBLEM Looking at the diagram, we see that node 1 is the origin and the nodes 2 and 3 are neighbours to the origin. Among the two nodes, we see that node 2 is at a distance of 40 units from node 1 whereas node 3 is at a distance of 100 units from node 1. The minimum of {40, 100} is 40. Thus, the node nearest to the origin is node 2, with a distance of 40 units. So, out of the two nodes 2 and 3, we select node 2. We form a set of nodes {1, 2} and construct a path connecting the node 2 with node 1 by a thick line and mark the distance of 40 in a box by the side of node 2. This first iteration is shown in the following diagram. 40 197 MBA-H2040 Quantitative Techniques for Managers 95 Store house 2 4 40 40 6 Factory 35 65 70 1 40 5 100 3 20 ITERATION No. 1 Now we search for the next node nearest to the set of nodes {1, 2}. For this purpose, consider those nodes which are neighbours of either node 1 or node 2. The nodes 3, 4 and 5 fulfill this condition. We calculate the following distances. The distance between nodes 1 and 3 = 100. The distance between nodes 2 and 3 = 35. The distance between nodes 2 and 4 = 95. The distance between nodes 2 and 5 = 65. Minimum of {100, 35, 95, 65} = 35. Therefore, node 3 is the nearest one to the set {1, 2}. In view of this observation, the set of nodes is enlarged from {1, 2} to {1, 2, 3}. For the set {1, 2, 3}, there are two possible paths, viz. Path 1 → 2 → 3 and Path 1 → 3 → 2. The Path 1 → 2 → 3 has a distance of 40 + 35 = 75 units while the Path 1 → 3 → 2 has a distance of 100 + 35 = 135 units. Minimum of {75, 135} = 75. Hence we select the path 1 → 2 → 3 and display this path by thick edges. The distance 75 is marked in a box by the side of node 3. We obtain the following diagram at the end of Iteration No. 2. 40 95 Store house 2 4 Factory 40 40 6 35 65 70 1 40 5 100 3 20 75 ITERATION No. 2 REPEATING THE PROCESS We repeat the process. The next node nearest to the set {1, 2, 3} is either node 4 or node 5. Node 4 is at a distance of 95 units from node 2 while node 2 is at a distance of 40 units from node 1. Thus, node 4 is at a distance of 95 + 40 = 135 units from the origin. 198 MBA-H2040 Quantitative Techniques for Managers As regards node 5, there are two paths viz. 2 → 5 and 3 → 5, providing a link to the origin. We already know the shortest routes from nodes 2 and 3 to the origin. The minimum distances have been indicated in boxes near these nodes. The path 3 → 5 involves the shortest distance. Thus, the distance between nodes 1 and 5 is 95 units (20 units between nodes 5 and 3 + 75 units between node 3 and the origin). Therefore, we select node 5 and enlarge the set from {1, 2, 3} to {1, 2, 3, 5}. The distance 95 is marked in a box by the side of node 5. The following diagram is obtained at the end of Iteration No. 3. 40 95 Store house 2 4 40 40 6 35 65 70 1 40 5 Factory 100 3 20 95 75 ITERATION No. 3 Now 2 nodes remain, viz., nodes 4 and 6. Among them, node 4 is at a distance of 135 units from the origin (95 units from node 4 to node 2 + 40 units from node 2 to the origin). Node 6 is at a distance of 135 units from the origin (40 + 95 units). Therefore, nodes 4 and 6 are at equal distances from the origin. If we choose node 4, then travelling from node 4 to node 6 will involve an additional distance of 40 units. However, node 6 is the ending node. Therefore, we select node 6 instead of node 4. Thus the set is enlarged from {1, 2, 3, 5} to {1, 2, 3, 5, 6}. The distance 135 is marked in a box by the side of node 6. Since we have got a path beginning from the start node and terminating with the stop node, we see that the solution to the given problem has been obtained. We have the following diagram at the end of Iteration No. 4. 40 95 Store house 2 4 40 40 6 35 65 70 1 40 135 5 Factory 100 3 20 95 75 ITERATION No. 4 MINIMUM DISTANCE Referring to the above diagram, we see that the shortest route is provided by the path 1 → 2 → 3 → 5 → 6 with a minimum distance of 135 units. 199 MBA-H2040 Quantitative Techniques for Managers QUESTIONS 1. Explain the shortest path problem. 2. Explain the algorithm for a shortest path problem 3. Find the shortest path of the following network: 30 3 5 40 40 1 30 50 30 45 6 25 35 2 4 4. Determine the shortest path of the following network: 2 16 5 7 9 7 1 4 15 6 8 4 25 3 LESSON 2 MINIMUM SPANNING TREE PROBLEM LESSON OUTLINE  The description of a minimum spanning tree problem.  The identification of the minimum spanning tree. LEARNING OBJECTIVES After reading this lesson you should be able to - understand a minimum spanning tree problem - understand the algorithm for minimum spanning tree problem - locate the minimum spanning tree 200 MBA-H2040 Quantitative Techniques for Managers - carry out numerical problems Tree: A minimally connected network is called a tree. If there are n nodes in a network, it will be a tree if the number of edges = n-1. Minimum spanning tree algorithm Problem : Given a connected network with weights assigned to the edges, it is required to find out a tree whose nodes are the same as those of the network. The weight assigned to an edge may be regarded as the distance between the two nodes with which the edge is incident. Algorithm: The problem can be solved with the help of the following algorithm. The procedure consists of selection of a node at each step. Step 1: First select any node in the network. This can be done arbitrarily. We will start with this node. Step 2: Connect the selected node to the nearest node. Step 3: Consider the nodes that are now connected. Consider the remaining nodes. If there is no node remaining, then stop. On the other hand, if some nodes remain, among them find out which one is nearest to the nodes that are already connected. Select this node and go to Step 2. Thus the method involves the repeated application of Steps 2 and 3. Since the number of nodes in the given network is finite, the process will end after a finite number of steps. The algorithm will terminate with step 3. How to break ties: While applying the above algorithm, if some nodes remain in step 3 and if there is a tie in the nearest node, then the tie can be broken arbitrarily. As a consequence of tie, we may end up with more than one optimal solution. Problem 1: Determine the minimum spanning tree for the following network. 60 5 2 70 60 60 80 100 7 1 3 40 120 50 8 201 4 6 MBA-H2040 Quantitative Techniques for Managers 80 50 60 30 90 Solution: Step 1: First select node 1. (This is done arbitrarily) Step 2: We have to connect node 1 to the nearest node. Nodes 2, 3 and 4 are adjacent to node 1. They are at distances of 60, 40 and 80 units from node 1. Minimum of {60, 40, 80} = 40. Hence the shortest distance is 40. This corresponds to node 3. So we connect node 1 to node 3 by a thick line. This is Iteration No. 1. 60 5 2 70 60 60 80 100 7 1 3 40 120 50 8 80 50 60 30 90 6 4 Iteration No. 1 Step 3: Now the connected nodes are 1 and 3. The remaining nodes are 2, 4, 5, 6, 7 and 8. Among them, nodes 2 and 4 are connected to node 1. They are at distances of 60 and 80 from node 1. Minimum of {60, 80} = 60. So the shortest distance is 60. Next, among the nodes 2, 4, 5, 6, 7 and 8, find out which nodes are connected to node 3. We find that all of them are connected to node 3. They are at distances of 60, 50, 80, 60, 100 and 120 from node 3. Minimum of {60, 50, 80, 60, 100, 120} = 50. Hence the shortest distance is 50. Among these nodes, it is seen that node 4 is nearest to node 3. Now we go to Step 2. We connect node 3 to node 4 by a thick line. This is Iteration No.2. 60 5 2 70 60 60 80 100 7 1 3 202 MBA-H2040 Quantitative Techniques for Managers 40 120 50 8 80 50 60 30 4 90 6 Iteration No. 2 Next go to step 3. Now the connected nodes are 1, 3 and 4. The remaining nodes are 2, 5, 6, 7 and 8. Node 2 is at a distance of 60 from node 1. Nodes 5, 6, 7 and 8 are not adjacent to node 1. All of the nodes 2, 5, 6, 7 and 8 are adjacent to node 3. Among them, nodes 2 and 6 are nearer to node 3, with equal distance of 60. Node 6 is adjacent to node 4, at a distance of 90. Now there is a tie between nodes 2 and 6. The tie can be broken arbitrarily. So we select node 2. Connect node 3 to Node 2 by a thick line. This is Iteration No. 3. 60 5 2 70 60 60 80 100 7 1 3 40 120 50 8 80 50 60 30 4 90 6 Iteration No. 3 We continue the above process. Now nodes 1, 2, 3 and 4 are connected. The remaining nodes are 5, 6, 7 and 8. None of them is adjacent to node 1. Node 5 is adjacent to node 2 at a distance of 60. Node 6 is at a distance of 60 from node 3. Node 6 is at a distance of 90 from node 4. There is a tie between 203 MBA-H2040 Quantitative Techniques for Managers nodes 5 and 6. We select node 5. Connect node 2 to node 5 by a thick line. This is Iteration No. 4. 60 5 2 70 60 60 80 100 7 1 3 40 120 50 8 80 50 60 30 4 90 6 Iteration No. 4 Now nodes 1, 2, 3, 4 and 5 are connected. The remaining nodes are 6, 7 and 8. Among them, node 6 is at the shortest distance of 60 from node 3. So, connect node 3 to node 6 by a thick line. This is Iteration No. 5. 60 5 2 70 60 60 80 100 7 1 3 40 120 50 8 80 50 60 30 4 90 6 Iteration No. 5 Now nodes 1, 2, 3, 4, 5 and 6 are connected. The remaining nodes are 7 and 8. Among them, node 8 is at the shortest distance of 30 from node 6. Consequently we connect node 6 to node 8 by a thick line. This is Iteration No. 6. 204 MBA-H2040 Quantitative Techniques for Managers 60 5 2 70 60 60 80 100 7 1 3 40 120 50 8 80 50 60 30 4 90 6 Iteration No. 6 Now nodes 1, 2, 3, 4, 5, 6 and 8 are connected. The remaining node is 7. It is at the shortest distance of 50 from node 8. So, connect node 8 to node 7 by a thick line. This is Iteration No.7. 60 5 2 70 60 60 80 100 7 1 3 40 120 50 8 80 50 60 30 4 90 6 Iteration No. 7 Now all the nodes 1, 2, 3, 4, 5, 6, 7 and 8 are connected by seven thick lines. Since no node is remaining, we have reached the stopping condition. Thus we obtain the following minimum spanning tree for the given network. 60 5 2 60 7 1 3 205 8 MBA-H2040 Quantitative Techniques for Managers 40 50 50 60 30 Minimum Spanning Tree QUESTIONS 1. Explain the minimum spanning tree algorithm. 2. From the following network, find the minimum spanning tree. 75 6 2 80 55 90 100 1 3 70 40 25 60 5 4 30 3. Find the minimum spanning tree of the following network: 12 5 2 15 5 8 2 10 13 8 1 3 6 9 4 10 5 7 4 4 206 MBA-H2040 Quantitative Techniques for Managers 207 MBA-H2040 Quantitative Techniques for Managers LESSON 3 PROJECT NETWORK LESSON OUTLINE  The key concepts  Construction of project network diagram LEARNING OBJECTIVES After reading this lesson you should be able to - understand the definitions of important terms - understand the development of project network diagram - work out numerical problems KEY CONCEPTS Certain key concepts pertaining to a project network are described below: 1. Activity An activity means a work. A project consists of several activities. An activity takes time. It is represented by an arrow in a diagram of the network. For example, an activity in house construction can be flooring. This is represented as follows: flooring Construction of a house involves various activities. Flooring is an activity in this project. We can say that a project is completed only when all the activities in the project are completed. 2. Event It is the beginning or the end of an activity. Events are represented by circles in a project network diagram. The events in a network are called the nodes. Example: Start Stop Punching Starting a punching machine is an activity. Stopping the punching machine is another activity. 3. Predecessor Event The event just before another event is called the predecessor event. 4. Successor Event The event just following another event is called the successor event. Example: Consider the following. 3 208 1 2 4 6 MBA-H2040 Quantitative Techniques for Managers In this diagram, event 1 is predecessor for the event 2. Event 2 is successor to event 1. Event 2 is predecessor for the events 3, 4 and 5. Event 4 is predecessor for the event 6. Event 6 is successor to events 3, 4 and 5. 5. Network A network is a series of related activities and events which result in an end product or service. The activities shall follow a prescribed sequence. For example, while constructing a house, laying the foundation should take place before the construction of walls. Fitting water tapes will be done towards the completion of the construction. Such a sequence cannot be altered. 6. Dummy Activity A dummy activity is an activity which does not consume any time. Sometimes, it may be necessary to introduce a dummy activity in order to provide connectivity to a network or for the preservation of the logical sequence of the nodes and edges. 7. Construction of a Project Network A project network consists of a finite number of events and activities, by adhering to a certain specified sequence. There shall be a start event and an end event (or stop event). All the other events shall be between the start and the end events. The activities shall be marked by directed arrows. An activity takes the project from one event to another event. An event takes place at a point of time whereas an activity takes place from one point of time to another point of time. CONSTRUCTION OF PROJECT NETWORK DIAGRAMS Problem 1: Construct the network diagram for a project with the following activities: Activity Name of Immediate 209 MBA-H2040 Quantitative Techniques for Managers EventEvent Activity Predecessor Activity 12 A - 13 B - 14 C - 25 D A 36 E B 46 F C 56 G D Solution: The start event is node 1. The activities A, B, C start from node 1 and none of them has a predecessor activity. A joins nodes1 and 2; B joins nodes 1 and 3; C joins nodes 1 and 4. So we get the following: A 2 1 3 B C 4 This is a part of the network diagram that is being constructed. Next, activity D has A as the predecessor activity. D joins nodes 2 and 5. So we get 1 A 2 D 5 Next, activity E has B as the predecessor activity. E joins nodes 3 and 6. So we get 1 B 3 E 6 Next, activity G has D as the predecessor activity. G joins nodes 5 and 6. Thus we obtain D G 2 5 6 Since activities E, F, G terminate in node 6, we get 5 G 3 6 E 4 210 MBA-H2040 Quantitative Techniques for Managers F 6 is the end event. Combining all the pieces together, the following network diagram is obtained for the given project: D 2 5 A G Start event End event 1 B 3 E 6 C F 4 We validate the diagram by checking with the given data. Problem 2: Develop a network diagram for the project specified below: Activity Immediate Predecessor Activity A - B A C, D B E C F D G E, F Solution: Activity A has no predecessor activity. i.e., It is the first activity. Let us suppose that activity A takes the project from event 1 to event 2. Then we have the following representation for A: 211 MBA-H2040 Quantitative Techniques for Managers A 1 2 For activity B, the predecessor activity is A. Let us suppose that B joins nodes 2 and 3. Thus we get 1 A 2 B 3 Activities C and D have B as the predecessor activity. Therefore we obtain the following: C B 4 2 3 D 5 Activity E has D as the predecessor activity. So we get C E 3 4 6 Activity F has D as the predecessor activity. So we get D F 3 5 6l ” Activity G has E and F as predecessor activities. This is possible only if nodes 6 and 6l are one and the same. So, rename node 6l as node 6. Then we get D F 3 5 6! and 4 E 6 7 G 5 212  MBA-H2040 Quantitative Techniques for Managers F G is the last activity. Putting all the pieces together, we obtain the following diagram the project network: Start event C 4 E End event 1 A 2 B 3 G 6 7 D F 5 The diagram is validated by referring to the given data. Note: An important point may be observed for the above diagram. Consider the following parts in the diagram C E 3 4 6 and D F 3 5 6l ” We took nodes 6 and 6l as one and the same. Instead, we can retain them as different nodes. Then, in order to provide connectivity to the network, we join nodes 6l and 6 by a dummy activity. Then we arrive at the following diagram for the project network: 4 Start event C E 6 1 2 3 G A B dummy activity 7 D 5 F 6l End event ! 213 MBA-H2040 Quantitative Techniques for Managers QUESTIONS: 1. Explain the terms: event, predecessor event, successor event, activity, dummy activity, network. 2. Construct the network diagram for the following project: Activity Immediate Predecessor Activity A - B - C A D B E A F C, D G E H E I F, G J H, I 214 MBA-H2040 Quantitative Techniques for Managers LESSON 4 CRITICAL PATH METHOD (CPM) LESSON OUTLINE  The concepts of critical path and critical activities  Location of the critical path  Evaluation of the project completion time LEARNING OBJECTIVES After reading this lesson you should be able to - understand the definitions of critical path and critical activities - identify critical path and critical activities - determine the project completion time INTRODUCTION The critical path method (CPM) aims at the determination of the time to complete a project and the important activities on which a manager shall focus attention. ASSUMPTION FOR CPM In CPM, it is assumed that precise time estimate is available for each activity. PROJECT COMPLETION TIME From the start event to the end event, the time required to complete all the activities of the project in the specified sequence is known as the project completion time. PATH IN A PROJECT A continuous sequence, consisting of nodes and activities alternatively, beginning with the start event and stopping at the end event of a network is called a path in the network. CRITICAL PATH AND CRTICAL ACTIVITIES Consider all the paths in a project, beginning with the start event and stopping at the end event. For each path, calculate the time of execution, by adding the time for the individual activities in that path. The path with the largest time is called the critical path and the activities along this path are called the critical activities or bottleneck activities. The activities are called critical 215 MBA-H2040 Quantitative Techniques for Managers because they cannot be delayed. However, a non-critical activity may be delayed to a certain extent. Any delay in a critical activity will delay the completion of the whole project. However, a certain permissible delay in a non –critical activity will not delay the completion of the whole project. It shall be noted that delay in a non-critical activity beyond a limit would certainly delay the completion the whole project. Sometimes, there may be several critical paths for a project. A project manager shall pay special attention to critical activities. Problem 1: The following details are available regarding a project: Activity Predecessor Duration (Weeks) Activity A - 3 B A 5 C A 7 D B 10 E C 5 F D,E 4 Determine the critical path, the critical activities and the project completion time. Solution: First let us construct the network diagram for the given project. We mark the time estimates along the arrows representing the activities. We obtain the following diagram: Start event B 3 D End event 5 10 1 A 2 3 5 F 6 C 4 7 E 4 5 Consider the paths, beginning with the start node and stopping with the end node. There are two such paths for the given project. They are as follows: Path I 216  MBA-H2040 Quantitative Techniques for Managers A B D F 1 2 3 5 6 3 5 10 4 with a time of 3 + 5 + 10 + 4 = 22 weeks. Path II A C E F 1 2 4 5 6 3 7 5 4 with a time of 3 + 7 + 5 + 4 = 19 weeks. Compare the times for the two paths. Maximum of {22,19} = 22. We see that path I has the maximum time of 22 weeks. Therefore, path I is the critical path. The critical activities are A, B, D and F. The project completion time is 22 weeks. We notice that C and E are non- critical activities. Time for path I - Time for path II = 22- 19 = 3 weeks. Therefore, together the non- critical activities can be delayed upto a maximum of 3 weeks, without delaying the completion of the whole project. Problem 2: Find out the completion time and the critical activities for the following project: D 5 2 20 A 8 G 8 B E H 11 K 6 1 6 8 10 3 10 16 I 14 L 5 C 7 J 9 F 7 10 4 25 Solution: In all, we identify 4 paths, beginning with the start node of 1 and terminating at the end node of 10. They are as follows: Path I A D G K 1 2 5 8 10 217 MBA-H2040 Quantitative Techniques for Managers 8 20 8 6 Time for the path = 8 + 20 + 8 + 6 = 42 units of time. Path II B E H K 1 3 6 8 10 10 16 11 6 Time for the path = 10 + 16 + 11 + 6 = 43 units of time. Path III B E I L 1 3 6 9 10 10 16 14 5 Time for the path = 10 + 16 + 14 + 5 = 45 units of time. Path IV C F J L 1 4 7 9 10 7 25 10 5 Time for the path = 7 + 25 + 10 + 5 = 47 units of time. Compare the times for the four paths. Maximum of {42, 43, 45, 47} = 47. We see that the following path has the maximum time and so it is the critical path: C F J L 1 4 7 9 10 7 25 10 5 The critical activities are C, F, J and L. The non-critical activities are A, B, D, E, G, H, I and K. The project completion time is 47 units of time. Problem 3: Draw the network diagram and determine the critical path for the following project: Activity Time estimate (Weeks) 1- 2 5 1- 3 6 218  MBA-H2040 Quantitative Techniques for Managers 1- 4 3 2 -5 5 3 -6 7 3 -7 10 4 -7 4 5 -8 2 6 -8 5 7 -9 6 8 -9 4 Solution: We have the following network diagram for the project: D 5 2 5 2 H A 5 1 B 3 E 6 I 8 K 6 7 5 4 9 3 C F 10 J 6 7 4 G 4 Solution: We assert that there are 4 paths, beginning with the start node of 1 and terminating at the end node of 9. They are as follows: Path I A D H K 1 2 5 8 9 5 5 2 4 Time for the path = 5 + 5 + 2 + 4 = 16 weeks. Path II B E I K 1 3 6 8 9 219 MBA-H2040 Quantitative Techniques for Managers 6 7 5 4 Time for the path = 6 + 7 + 5 + 4 = 22 weeks. Path III B F J 1 3 7 9 6 10 6 Time for the path = 6 + 10 + 6 = 16 weeks. Path IV C G J 1 4 7 9 3 4 6 Time for the path = 3 + 4 + 6 = 13 weeks. Compare the times for the four paths. Maximum of {16, 22, 16, 13} = 22. We see that the following path has the maximum time and so it is the critical path: B E I K 1 3 6 8 9 6 7 5 4 The critical activities are B, E, I and K. The non-critical activities are A, C, D, F, G, H and J. The project completion time is 22 weeks. 220 MBA-H2040 Quantitative Techniques for Managers QUESTIONS: 1. Explain the terms: critical path, critical activities. 2. The following are the time estimates and the precedence relationships of the activities in a project network: Activity IMMEDIATE time estimate Predecessor (weeks) Activity A - 4 B - 7 C - 3 D A 6 E B 4 F B 7 G C 6 H E 10 I D 3 J F, G 4 K H, I 2 Draw the project network diagram. Determine the critical path and the project completion time. 221 MBA-H2040 Quantitative Techniques for Managers LESSON 5 PERT LESSON OUTLINE  The concept of PERT  Estimates of the time of an activity  Determination of critical path  Probability estimates LEARNING OBJECTIVES After reading this lesson you should be able to - understand the importance of PERT - locate the critical path - determine the project completion time - find out the probability of completion of a project before a stipulated time INTRODUCTION Programme Evaluation and Review Technique (PERT) is a tool that would help a project manager in project planning and control. It would enable him in continuously monitoring a project and taking corrective measures wherever necessary. This technique involves statistical methods. ASSUMPTIONS FOR PERT Note that in CPM, the assumption is that precise time estimate is available for each activity in a project. However, one finds most of the times that this is not practically possible. In PERT, we assume that it is not possible to have precise time estimate for each activity and instead, probabilistic estimates of time alone are possible. A multiple time estimate approach is followed here. In probabilistic time estimate, the following 3 types of estimate are possible: 1. Pessimistic time estimate ( t p ) 2. Optimistic time estimate ( to ) 3. Most likely time estimate ( tm ) The optimistic estimate of time is based on the assumption that an activity will not involve any difficulty during execution and it can be completed within a short period. On the other hand, a pessimistic estimate is made on the assumption that there would be unexpected 222 MBA-H2040 Quantitative Techniques for Managers problems during the execution of an activity and hence it would consume more time. The most likely time estimate is made in between the optimistic and the pessimistic estimates of time. Thus the three estimates of time have the relationship to  tm  t p. Practically speaking, neither the pessimistic nor the optimistic estimate may hold in reality and it is the most likely time estimate that is expected to prevail in almost all cases. Therefore, it is preferable to give more weight to the most likely time estimate. We give a weight of 4 to most likely time estimate and a weight of 1 each to the pessimistic and optimistic time estimates. We arrive at a time estimate ( te ) as the weighted average of these estimates as follows: to  4 tm  t p te  6 Since we have taken 6 units ( 1 for t p , 4 for tm and 1 for to ), we divide the sum by 6. With this time estimate, we can determine the project completion time as applicable for CPM. Since PERT involves the average of three estimates of time for each activity, this method is very practical and the results from PERT will be have a reasonable amount of reliability. MEASURE OF CERTAINTY The 3 estimates of time are such that to  t m  t p. Therefore the range for the time estimate is t p  to. The time taken by an activity in a project network follows a distribution with a standard deviation of one sixth of the range, approximately. t p  to i.e., The standard deviation =   6 2  t t  and the variance =    p o  2  6  The certainty of the time estimate of an activity can be analysed with the help of the variance. The greater the variance, the more uncertainty in the time estimate of an activity. Problem 1: Two experts A and B examined an activity and arrived at the following time estimates. Expert Time Estimate 223 MBA-H2040 Quantitative Techniques for Managers to tm tp A 4 6 8 B 4 7 10 Determine which expert is more certain about his estimates of time: Solution: 2 t t  Variance (  ) in time estimates =  p o  2  6  2 84 4 In the case of expert A, the variance =     6  9 2  10  4  As regards expert B, the variance =   1  6  So, the variance is less in the case of A. Hence, it is concluded that the expert A is more certain about his estimates of time. Determination of Project Completion Time in PERT Problem 2: Find out the time required to complete the following project and the critical activities: Activity Predecessor Optimistic time Most likely time Pessimistic time Activity estimate (to days) estimate (tm days) estimate (tp days) A - 2 4 6 B A 3 6 9 C A 8 10 12 D B 9 12 15 E C 8 9 10 F D, E 16 21 26 G D, E 19 22 25 H F 2 5 8 I G 1 3 5 Solution: From the three time estimates t p , tm and to , calculate te for each activity. We obtain the following table: Activity Optimistic 4 x Most likely Pessimistic to+ 4tm+ tp Time estimate time estimate time estimate time estimate to  4 tm  t p (to) (tp) te  6 A 2 16 6 24 4 B 3 24 9 36 6 C 8 40 12 60 10 D 9 48 15 72 12 E 8 36 10 54 9 F 16 84 26 126 21 224 MBA-H2040 Quantitative Techniques for Managers G 19 88 25 132 22 H 2 20 8 30 5 I 1 12 5 18 3 Using the single time estimates of the activities, we get the following network diagram for the project. B 3 D F H6 6 12 21 5 A 1 4 2 C 10 E 5G I 8 9 22 3 4 7 Consider the paths, beginning with the start node and stopping with the end node. There are four such paths for the given project. They are as follows: Path I A D B F H 1 3 2 5 6 8 4 6 12 21 5 Time for the path: 4+6+12+21+5 = 48 days. Path II A B D G I 1 2 3 5 7 8 4 6 12 6 3 6 Time for the path: 4+6+12+ 6+3 = 31 days. Path III A C E F H 1 4 6 4 2 10 9 215 5 8 3 7 Time for the path: 4+10+9+ 21+5 = 49 days. Path IV A C E G I 1 2 4 5 7 8 4 10 9 6 3 6 Time for the path: 4+10+9+ 6+3 = 32 days. Compare the times for the four paths. Maximum of {48, 31, 49, 32} = 49. We see that Path III has the maximum time. Therefore the critical path is Path III. i.e., 1 2 4 5 6 8. The critical activities are A, C, E, F and H. The non-critical activities are B, D, G and I. Project time (Also called project length) = 49 days. Problem 3: Find out the time, variance and standard deviation of the project with the following time estimates in weeks: 225 MBA-H2040 Quantitative Techniques for Managers Activity Optimistic time Most likely time Pessimistic time estimate (to) estimate (tm) estimate (tp) 1-2 3 6 9 1-6 2 5 8 2-3 6 12 18 2-4 4 5 6 3-5 8 11 14 4-5 3 7 11 6-7 3 9 15 5-8 2 4 6 7-8 8 16 18 Solution: From the three time estimates t p , tm and to , calculate te for each activity. We obtain the following table: Activity Optimistic 4 x Most likely Pessimistic to+ 4tm+ tp Time estimate time estimate time estimate time estimate to  4 tm  t p (to) (tp) te  6 1-2 3 24 9 36 6 1-6 2 20 8 30 5 2-3 6 48 18 72 12 2-4 4 20 6 30 5 3-5 8 44 14 66 11 4-5 3 28 11 42 7 6-7 3 36 15 54 9 5-8 2 16 6 24 4 7-8 8 64 18 90 15 With the single time estimates of the activities, we get the following network diagram for the project. C 3 F 12 11 2 D 5 G 5I A 6 7 4 4 1 5 B H 8 E 15 9 6 Consider the paths, beginning with the start node and stopping with the end node. There are three such paths for 7 the given project. They are as follows: Path I A C F I 1 2 3 5 8 226 MBA-H2040 Quantitative Techniques for Managers 6 12 11 4 Time for the path: 6+12+11+4 = 33 weeks. Path II A D G I 1 2 4 5 8 6 5 73 4 Time for the path: 6+5+7+ 4= 22 weeks. Path III B E H 1 6 9 7 8 5 15 3 Time for the path: 5+9+15 = 29 weeks. Compare the times for the three paths. Maximum of {33, 22, 29} = 33. It is noticed that Path I has the maximum time. Therefore the critical path is Path I. i.e., 1 2 3 5 8 The critical activities are A, C, F and I. The non-critical activities are B, D, G and H. Project time = 33 weeks. Calculation of Standard Deviation and Variance for the Critical Activities: Critical Optimistic Most likely Pessimistic Range Standard Variance Activity time time time (tp - to ) deviation = 2 t t  estimate estimate estimate t t 2  p o  (to) (tm) (tp)  p o  6  6 A: 12 3 6 9 6 1 1 C: 23 6 12 18 12 2 4 F: 35 8 11 14 6 1 1 I: 58 2 4 6 4 2/3 4/9 Variance of project time (Also called Variance of project length) = Sum of the variances for the critical activities = 1+4+1+ 4/9 = 58/9 Weeks. Standard deviation of project time = √Variance = √58/9 = 2.54 weeks. Problem 4 A project consists of seven activities with the following time estimates. Find the probability that the project will be completed in 30 weeks or less. Activity Predecessor Optimistic time Most likely time Pessimistic time Activity estimate (to days) estimate (tm days) estimate (tp days) A - 2 5 8 B A 2 3 4 C A 6 8 10 D A 2 4 6 E B 2 6 10 F C 6 7 8 G D, E, F 6 8 10 Solution: 227 MBA-H2040 Quantitative Techniques for Managers From the three time estimates t p , tm and to , calculate te for each activity. The results are furnished in the following table: Activity Optimistic 4 x Most Pessimistic time to+ 4tm+ tp Time estimate time estimate likely time estimate (tp) to  4 tm  t p (to) estimate te  6 A 2 20 8 30 5 B 2 12 4 18 3 C 6 32 10 48 8 D 2 16 6 24 4 E 2 24 10 36 6 F 6 28 8 42 7 G 6 32 10 48 8 With the single time estimates of the activities, the following network diagram is constructed for the project. 3 B 3 6 E C 4F 8 7 A D G 5 4 8 1 2 5 6 Consider the paths, beginning with the start node and stopping with the end node. There are three such paths for the given project. They are as follows: Path I A B E G 1 2 3 5 6 5 3 46 8 8 Time for the path: 5+3+6+8 = 22 weeks. Path II A C F G 1 2 4 5 6 5 8 47 8 8 Time for the path: 5+8+7+ 8 = 28 weeks. Path III A D G 1 2 5 6 5 4 84 Time for the path: 5+4+8 = 17 weeks. Compare the times for the three paths. Maximum of {22, 28, 17} = 28. It is noticed that Path II has the maximum time. 228 MBA-H2040 Quantitative Techniques for Managers Therefore the critical path is Path II. i.e., 1 2 4 5 6. The critical activities are A, C, F and G. The non-critical activities are B, D and E. Project time = 28 weeks. Calculation of Standard Deviation and Variance for the Critical Activities: Critical Optimistic Most likely Pessimistic Range Standard Variance Activity time time time estimate (tp -to) deviation = 2 estimate estimate (tp ) t t  t p  to   p o  2 (to) (tm)   6  6 A: 12 2 5 8 6 1 1 C: 24 6 8 10 2 4 3 9 4 F: 45 6 7 8 1 1 3 9 2 G: 56 6 8 10 2 4 4 3 9 Standard deviation of the critical path = √2 = 1.414 The standard normal variate is given by the formula Given value of t  Expected value of t in the critical path Z  SD for the critical path 30  28 So we get Z  = 1.414 1.414 We refer to the Normal Probability Distribution Table. Corresponding to Z = 1.414, we obtain the value of 0.4207 We get 0.5 + 0.4207 = 0. 9207 Therefore the required probability is 0.92 i.e., There is 92% chance that the project will be completed before 30 weeks. In other words, the chance that it will be delayed beyond 30 weeks is 8% QUESTIONS: 1. Explain how time of an activity is estimated in PERT. 2. Explain the measure of certainty in PERT. 3. The estimates of time in weeks of the activities of a project are as follows: Activity Predecessor Optimistic Most likely Pessimistic Activity estimate of time estimate of time estimate of time A - 2 4 6 B A 8 11 20 C A 10 15 20 D B 12 18 24 229 MBA-H2040 Quantitative Techniques for Managers E C 8 13 24 F C 4 7 16 G D,F 14 18 28 H E 10 12 14 I G,H 7 10 19 Determine the critical activities and the project completion time. 4. Draw the network diagram for the following project. Determine the time, variance and standard deviation of the project.: Activity Predecessor Optimistic Most likely Pessimistic Activity estimate of time estimate of time estimate of time A - 12 14 22 B - 16 17 24 C A 14 15 16 D A 13 18 23 E B 16 18 20 F D,E 13 14 21 G C,F 6 8 10 230 MBA-H2040 Quantitative Techniques for Managers 5. Consider the following project with the estimates of time in weeks: Activity Predecessor Optimistic Most likely Pessimistic Activity estimate of time estimate of time estimate of time A - 2 4 6 B - 3 5 7 C A 5 6 13 D A 4 8 12 E B,C 5 6 13 F D,E 6 8 14 Find the probability that the project will be completed in 27 weeks. 231 MBA-H2040 Quantitative Techniques for Managers NORMAL DISTRIBUTION TABLE Area Under Standard Normal Distribution 0.00 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.0 0.0000 0.0040 0.0080 0.0120 0.0160 0.0199 0.0239 0.0279 0.0319 0.0359 0.1 0.0398 0.0438 0.0478 0.0517 0.0557 0.0596 0.0636 0.0675 0.0714 0.0753 0.2 0.0793 0.0832 0.0871 0.0910 0.0948 0.0987 0.1026 0.1064 0.1103 0.1141 0.3 0.1179 0.1217 0.1255 0.1293 0.1331 0.1368 0.1406 0.1443 0.1480 0.1517 0.4 0.1554 0.1591 0.1628 0.1664 0.1700 0.1736 0.1772 0.1808 0.1844 0.1879 0.5 0.1915 0.1950 0.1985 0.2019 0.2054 0.2088 0.2123 0.2157 0.2190 0.2224 0.6 0.2257 0.2291 0.2324 0.2357 0.2389 0.2422 0.2454 0.2486 0.2517 0.2549 0.7 0.2580 0.2611 0.2642 0.2673 0.2704 0.2734 0.2764 0.2794 0.2823 0.2852 0.8 0.2881 0.2910 0.2939 0.2967 0.2995 0.3023 0.3051 0.3078 0.3106 0.3133 0.9 0.3159 0.3186 0.3212 0.3238 0.3264 0.3289 0.3315 0.3340 0.3365 0.3389 1.0 0.3413 0.3438 0.3461 0.3485 0.3508 0.3531 0.3554 0.3577 0.3599 0.3621 1.1 0.3643 0.3665 0.3686 0.3708 0.3729 0.3749 0.3770 0.3790 0.3810 0.3830 1.2 0.3849 0.3869 0.3888 0.3907 0.3925 0.3944 0.3962 0.3980 0.3997 0.4015 1.3 0.4032 0.4049 0.4066 0.4082 0.4099 0.4115 0.4131 0.4147 0.4162 0.4177 1.4 0.4192 0.4207 0.4222 0.4236 0.4251 0.4265 0.4279 0.4292 0.4306 0.4319 1.5 0.4332 0.4345 0.4357 0.4370 0.4382 0.4394 0.4406 0.4418 0.4429 0.4441 1.6 0.4452 0.4463 0.4474 0.4484 0.4495 0.4505 0.4515 0.4525 0.4535 0.4545 1.7 0.4554 0.4564 0.4573 0.4582 0.4591 0.4599 0.4608 0.4616 0.4625 0.4633 1.8 0.4641 0.4649 0.4656 0.4664 0.4671 0.4678 0.4686 0.4693 0.4699 0.4706 1.9 0.4713 0.4719 0.4726 0.4732 0.4738 0.4744 0.4750 0.4756 0.4761 0.4767 2.0 0.4772 0.4778 0.4783 0.4788 0.4793 0.4798 0.4803 0.4808 0.4812 0.4817 2.1 0.4821 0.4826 0.4830 0.4834 0.4838 0.4842 0.4846 0.4850 0.4854 0.4857 2.2 0.4861 0.4864 0.4868 0.4871 0.4875 0.4878 0.4881 0.4884 0.4887 0.4890 2.3 0.4893 0.4896 0.4898 0.4901 0.4904 0.4906 0.4909 0.4911 0.4913 0.4916 2.4 0.4918 0.4920 0.4922 0.4925 0.4927 0.4929 0.4931 0.4932 0.4934 0.4936 2.5 0.4938 0.4940 0.4941 0.4943 0.4945 0.4946 0.4948 0.4949 0.4951 0.4952 2.6 0.4953 0.4955 0.4956 0.4957 0.4959 0.4960 0.4961 0.4962 0.4963 0.4964 2.7 0.4965 0.4966 0.4967 0.4968 0.4969 0.4970 0.4971 0.4972 0.4973 0.4974 2.8 0.4974 0.4975 0.4976 0.4977 0.4977 0.4978 0.4979 0.4979 0.4980 0.4981 2.9 0.4981 0.4982 0.4982 0.4983 0.4984 0.4984 0.4985 0.4985 0.4986 0.4986 3.0 0.4987 0.4987 0.4987 0.4988 0.4988 0.4989 0.4989 0.4989 0.4990 0.4990 LESSON 6 EARLIEST AND LATEST TIMES 232 MBA-H2040 Quantitative Techniques for Managers LESSON OUTLINE  The concepts of earliest and latest times  The concept of slack  Numerical problems LEARNING OBJECTIVES After reading this lesson you should be able to - understand the concepts of earliest and latest times - understand the concept of slack - calculate the earliest and latest times - find out the slacks - identify the critical activities - carry out numerical problems INTRODUCTION A project manager has the responsibility to see that a project is completed by the stipulated date, without delay. Attention is focused on this aspect in what follows. Key concepts Certain key concepts are introduced below. EARLIEST TIMES OF AN ACTIVITY We can consider (i) Earliest Start Time of an activity and (ii) Earliest Finish Time of an activity. Earliest Start Time of an activity is the earliest possible time of starting that activity on the condition that all the other activities preceding to it were began at the earliest possible times. Earliest Finish Time of an activity is the earliest possible time of completing that activity. It is given by the formula. The Earliest Finish Time of an activity = The Earliest Start Time of the activity + The estimated duration to carry out that activity. LATEST TIMES OF AN ACTIVITY We can consider (i) Latest Finish Time of an activity and (ii) Latest Start Time of an activity. Latest Finish Time of an activity is the latest possible time of completing that activity on the condition that all the other activities succeeding it are carried out as per the plan of the management and without delaying the project beyond the stipulated time. Latest Start Time of an activity is the latest possible time of beginning that activity. It is given by the formula Latest Start Time of an activity = The Latest Finish Time of the activity - The estimated duration to carry out that activity. 233 MBA-H2040 Quantitative Techniques for Managers TOTAL FLOAT OF AN ACTIVITY Float seeks to measure how much delay is acceptable. It sets up a control limit for delay. The total float of an activity is the time by which that activity can be delayed without delaying the whole project. It is given by the formula Total Float of an Activity = Latest Finish Time of the activity - Earliest Finish Time of that activity. It is also given by the formula Total Float of an Activity = Latest Start Time of the activity - Earliest Start Time of that activity. Since a delay in a critical activity will delay the execution of the whole project, the total float of a critical activity must be zero. EXPECTED TIMES OF AN EVENT An event occurs at a point of time. We can consider (i) Earliest Expected Time of Occurrence of an event and (ii) Latest Allowable Time of Occurrence an event. The Earliest Expected Time of Occurrence of an event is the earliest possible time of expecting that event to happen on the condition that all the preceding activities have been completed. The Latest Allowable Time of Occurrence of an event is the latest possible time of expecting that event to happen without delaying the project beyond the stipulated time. PROCUDURE TO FIND THE EARLIEST EXPECTED TIME OF AN EVENT Step 1. Take the Earliest Expected Time of Occurrence of the Start Event as zero. Step 2. For an event other than the Start Event, find out all paths in the network which connect the Start node with the node representing the event under consideration. Step 3. In the “Forward Pass” (i.e., movement in the network from left to right), find out the sum of the time durations of the activities in each path identified in Step 2. Step 4. The path with the longest time in Step 3 gives the Earliest Expected Time of Occurrence of the event Working Rule for finding the earliest expected time of an event: For an event under consideration, locate all the predecessor events and identify their earliest expected times. With the earliest expected time of each event, add the time duration of the activity connecting that event to the event under consideration. The maximum among all these values gives the Earliest Expected Time of Occurrence of the event. 234 MBA-H2040 Quantitative Techniques for Managers PROCUDURE TO FIND THE LATEST ALLOWABLE TIME OF AN EVENT We consider the “Backward Pass” (i.e., movement in the network from right to left). The latest allowable time of occurrence of the End Node must be the time of completion of the project. Therefore it shall be equal to the time of the critical path of the project. Step 1. Identify the latest allowable time of occurrence of the End Node. Step 2. For an event other than the End Event, find out all paths in the network which connect the End node with the node representing the event under consideration. Step 3. In the “Backward Pass” (i.e., movement in the network from right to left), subtract the time durations of the activities along each such path. Step 4. The Latest Allowable Time of Occurrence of the event is determined by the path with the longest time in Step 3. In other words, the smallest value of time obtained in Step 3 gives the Latest Allowable Time of Occurrence of the event. Working Rule for finding the latest allowable time of an event: For an event under consideration, locate all the successor events and identify their latest allowable times. From the latest allowable time of each successor event, subtract the time duration of the activity that begins with the event under consideration. The minimum among all these values gives the Latest Allowable Time of Occurrence of the event. SLACK OF AN EVENT The allowable time gap for the occurrence of an event is known as the slack of that event. It is given by the formula Slack of an event = Latest Allowable Time of Occurrence of the event - Earliest Expected Time of Occurrence of that event. SLACK OF AN ACTIVITY The slack of an activity is the float of the activity. Problem 1: The following details are available regarding a project: Activity Predecessor Duration (Weeks) Activity A - 12 235 MBA-H2040 Quantitative Techniques for Managers B A 7 C A 11 D A 8 E A 6 F B 10 G C 9 H D, F 14 I E, G 13 J H, I 16 Determine the earliest and latest times, the total float for each activity, the critical activities and the project completion time. Solution: With the given data, we construct the following network diagram for the project. 3 F 10 B 7 H D 14 5 A 8 J 1 12 2 E 16 8 7 6 I C 11 13 G 9 6 4 with the start node and stopping with the end node. There are Consider the paths, beginning four such paths for the given project. They are as follows: Path I A B F H J 1 2 3 5 7 1 12 7 10 14 16 Time of the path = 12 + 7 + 10 + 14 + 16 = 59 weeks. Path II A D H