Networks Presentation
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Networks Presentation as PDF for free.
More details
- Words: 2,776
- Pages: 39
Chapter 12 - NETWORKS PERT, CPM,PERT/COST Scheduling with Resource Limitations Maximal-Flow Problem Minimal-Spanning-Tree Problem Shortest-Route Problem Dynamic Programming
Objectives >Introduce the concepts of networks and networking technique as a solution models for complex project-scheduling problems. >Review in detail the concepts and use of PERT and PERT/COST to plan and control projects. >Show the use of CPM in the planning and control of projects. >Demonstrate how to schedule projects involving resource limitations.
Networks - Complex projects requires a series of activities, some of which must be performed sequentially and others that can be performed in parallel with other activities. This collection of series and parallel tasks can be modelled as a network.
PERT (Program Evaluation and Review Technique) - is a network model that allows for randomness in activity completion times. PERT was developed in the late 1950’s for the US Navy’s Polaris project having thousands of contractors. It has the potential to reduce both the time and cost required to complete a project.
Steps in the PERT Planning Process 1) Identify Activities and Milestones - activities are the tasks required to complete the project, milestones are the events marking the beginning and end of one or more activities. It is helpful to list the tasks in a table that in later steps can be expanded to include information on sequence and duration. 2) Determine Activity Sequence - this step may be combined with the activity identification step since the activity sequence is evident for some tasks. Other tasks mat require more analysis to determine the exact order in which they must be performed.
3) Construct the Network Diagram - using the activity sequence information, a network diagram can be can be drawn showing the sequence of the serial and parallel activities. For the original activity-on-arc model, the activities are depicted by arrowed lines and milestones are depicted by circles or “bubbles”.
4) Estimate Activity Times - a distinguishing feature of PERT is its ability to deal with uncertainty in activity completion times. For each activity, the model usually includes three time estimates: * Optimistic time (a) – the shortest time in which the activity can be completed. It is common practice to specify optimistic times to be three standard deviations from the mean so that there is approximately a 1% chance that the activity will be completed within the optimistic time. * Most likely time (m)– the completion time having the highest probability. Note that this time is different from the expected time. * Pessimistic time (b) – the longest time that an activity might require. Three standard deviations from the mean is commonly used for pessimistic time.
PERT assumes a beta probability distribution for the estimates. For a beta distribution, the expected time for each activity can be approximated using the following weighted average Expected time = (optimistic + 4 x most likely + pessimistic) / 6 t = a + 4m + b 6 Standard deviation of an activity = b – a 6 This expected time may be displayed on the network diagram.
To calculate the variance for each activity completion time, if three standard deviation times were selected for the optimistic and pessimistic times, then there are six standard deviations between them, so the variance is given by:
[ (pessimistic – optimistic) / 6 ] 2
5) Determine the Critical Path - critical path is determined by adding the times for the activities in each sequence and determining the longest path in the project. The critical path determines the total calendar time required for the project. If activities outside the critical path speed up or slow down (within limits), the total project time does not change. The amount of time that a non-critical path activity can be delayed without delaying the project is referred to as slack time.
If the critical path is not immediately obvious, it maybe helpful to determine the following four quantities for each activity: ES – Earliest start Time EF – Earliest Finish Time LS – Latest Start Time LF – Latest Finish Time
These times are calculated using the expected time for the relevant activities. ES/EF of each activity are determined by working forward through the network and determining the earliest time at which an activity can start and finish considering its predecessor activities. (Immediate Predecessor – activities that must immediately precede a given activity
LS/LF are the latest times that an activity can start and finish without delaying the project. Can be found by working backward through the network. The difference in the latest earliest time finish of each activity is that activity’s slack. The critical path then is the path through the networking which none of the activities have slack.
6) Update the Project Progress - make adjustment in the PERT chart as the project progress. As the project unfolds, the estimated times can be replaced with actual times. In cases where there are delays, additional resources mat be needed to stay on schedule and the PERT chart may be modified to reflect the new situation.
Using PERT to Plan the Introduction of a New HI-FI Speaker Activity list involved in the promotional campaign for the New Response 1000 speaker. Activity Symbol Activity Description
Immediate Predecesso rs
A
Develop the advertising plan (a detailed plan of projected radio, television, and newspaper advertising)
B
Develop the promotion and training materials plan (a detailed study of the materials that will be required for training the store managers and for the final in-store introduction)
C
Develop the training plan (the design of the training program that the store managers will undertake prior to the final in-store introduction)
D
Schedule the radio, television, and newspaper advertisements that will appear prior to the final introduction
A
E
Develop the advertising copy that will be required
A
F
A “Dummy” activity (one that takes no time) w/c lets us draw networks using only straight lines or which establishes precedence relationships (what activities precede each other)
G
Prepare promotion materials which will be used during the in-store introduction
B
H
Prepare materials which will be used in the training program for the store managers
B
I
Conduct the preintroduction advertising campaign in the media
D, F
J
Screen and select the store managers who will undergo training
C
K
Conduct the training program
L
The final in-store introduction of the Response 1000
H, J G, I, K
Drawing the network Nodes – circles represents the start and the finish of activities. Branches – arrows represents the activities in the project. Schedule radio, television, and newspapers advertisements
3
6 E
D
Preintroduction advertising campaign
F
Develop advertising copy
5
Develop the advertising plan
Dummy I
A
Develop the promotion and training materials plan
Prepare the in-store promotion materials
1
4
8
B
G
H Develop the training plan
K
Conduct the training program Screen and select participating store managers
7 J
9 L
Prepare training materials
C
2
Introduction of the Response 1000
Finding the critical path (longest path) Path – is defined as a sequence of connected activities that leads from the beginning of the project (node 1) to the end of the project (node 9). Activity
a (most m (most likely optimistic time) time)
b (most pessimistic time)
(a+4m+b)/6 (b - a)/6 (activity (expected time) std dev)
A
1
2
3
2
.33
B
1
2
3
2
.33
C
1
2
3
2
.33
D
1
2
9
3
1.33
E
2
3
10
4
1.33
(Dummy activity)
0
0
F
G
3
6
15
7
2.00
H
3
5
14
6
2.00
I
1
4
7
4
1.00
J
4
9
20
10
2.67
K
1
2
9
3
1.33
L
4
4
4
4
0
The Earliest-Start-Time-Rule (All earliest start (ES) and all earliest finish (EF) times) Formula : Earliest finish time = Earliest start time + Expected time EF = ES + t 2
t=3
5
3
6 2
E
2
D
6
t=4
6
F
5 t=2
6
t=0
t=4
6
I
A
10 0
0
t=2
2
1
2
t=7
9
4
15
8
B
2
G 15
H
t=6
C
K
8 2 2
t = 10
2
12
7 J
12
t=3
19
9 L
0
t=2
t=4
The-Latest-Finish-Time-Rule (All latest start (LS) and all latest finish (LF)) Formula : Latest start time = latest finish time – expected time LS = LF - t 8
t=3
11
3
11
6 7
E
7
D
11
t=4
11 F
5 t=2
t=0
t=4
11
I
A
15 5
4
t=2
6
1
8
t=7
15
4
15
8
B
6
G 15
H
t=6
C
K
12 2 2
t = 10
2
12
7 J
12
t=3
19
9 L
0
t=2
t=4
Determination of critical path for Response 1000 Activity
Earliest Start Latest Start Earliest Finish
Latest Finish
Slack (LS–ES or Activity on LF-EF) Critical Path
A
0
5
2
7
5
B
0
4
2
6
4
C
0
0
2
2
0
D
2
8
5
11
6
E
2
7
6
11
5
F
Yes
(Dummy activity)
G
2
8
9
15
6
H
2
6
8
12
4
I
6
11
10
15
5
J
2
2
12
12
0
Yes
K
12
12
15
15
0
Yes
L
15
15
19
19
0
Yes
Listed below are the useful information provided by using PERT about the Response 1000 project : 1) The expected project completion time is 19 weeks. 2) Activities C, J, K, and L are on the critical path, they must be watched more closely that the others, for if they fall behind, the whole project falls behind. 3) If extra effort is needed to finish the project on time, and if resources on one activity can possibly be used on another to reduce time, it can be borrow formanother activity except from th critical path. 4) Activities not on the critical path can fall behind by varying amounts without causing the project to be late.
CPM (Critical Path Method) - the Critical path method of planning and controlling projects has enjoyed the widest use among all the systems that follow the networking principle. The fundamental departure of CPM from PERT is that CPM brings the concept of cost more prominently into the planning and control process. When time can be estimated and cost can be calculated rather accurately in advance , CPM maybe superior to PERT. But when there is a extreme degree of uncertainty and when control over time outweighs control over costs, PERT may well be the better choice. The networking principles used in CPM are like those in the PERT system.
Estimating Time in CPM 1)Normal estimate of time approximates the most likely time estimate in PERT. Normal cost is associated with finishing the project in the normal time. 2)Crash time estimate is the time that would be required if no costs were spared in reducing the project time. Crash cost is the cost associated with doing job on a crash basis so as to minimize completion time.
Crashing a project - to crash a project successfully, note its activities and compare normal costs with crash costs for each activity. Goal is to find those activities on the critical path where time can be cut substantially with minimum extra cost spent. It’s goal is the greatest reduction in project time for the least increase in project cost.
PERT/Cost - PERT and CPM were both time-oriented, that is, they were design to allowed project planners to produce time schedules for the planning and monitoring of complex projects. In neither case was cost a major consideration. Earlier users of PERT and CPM noticed the need of this technique to concern themselves with project cost control as well as time control; and in the early 1960’s after the publication of a US government manual DOD and NASA Guide, PERT/Cost Systems Design, most military and research contracts required the use of PERT/cost on the part of the contractor. Today, there are many different project cost accounting technique
1) Costing by activities - completion time and activities are limited. 2) Estimating project costs by activity - managers should know the amounts of money that are to be expected for each activity over the planned duration of the project; one usually assumes that expenditures of each activity are made at a constant rate during that activity.
Activity information of for nine activity project network Activity
ES
LS
Duration (month)Total Cost ($)
Cost / month ($)
A
0
0
3
30,000
10,000
B
0
8
2
200,000
100,000
C
3
9
1
40,000
40,000
D
3
3
4
20,000
5,000
E
7
7
5
75,000
15,000
F
4
10
2
100,000
50,000
G
4
10
1
75,000
75,000
H
12
12
3
18,000
6,000
I
5
11
4
240,000
60,000
$798,000
D t=4
2
4 E
$20,000
A
t=5
t=3
$75,000
C
$30,000
$40,000
t=1
H t=3
1
B
F
t=2
t=2
$200,000
5
7 $18,000
$100,000
3
$240,000 $75,000
t=4 t=1 G
I
6
3) Project budgeting choices - from technological point of view, the project director can choose when to begin each activity in this project or he could wait to begin until each activity until it’s latest start time. What is the difference?
Project cost with early starts (cost in thousand $) 1
2
A
10
10
B
100
100
3
4
5
6
7
8
9
10
11
12
13
14
15
10
C
40
D
5
5
5
5
E
15
F
50
G
75
15
15
15
15
50
H I
60
60
60
60
6
6
6
Total 110
110
10
45
130
115
65
75
75
15
15
15
6
6
6
Acc 110 total
220
230
275
405
520
585
660
735
750
765
780
766
792
798
Project cost with late starts (cost in thousand $) 1
A
10
2
10
3
4
5
6
7
8
9
10
11
12
13
14
15
10
B
100
C
100 40
D
5
5
5
5
E
15
15
15
15
15
F
50
50
G
75
H I
6
6
6
60
60
60
60
Total 10
10
10
5
5
5
5
15
115
155
140
125
66
66
66
Acc 10 total
20
30
35
40
45
50
65
180
335
475
600
666
732
798
Network Scheduling with resource limitations Problem: Required workers to complete the activity for 9 weeks are 15 persons, but only 9 persons are available. B 2wks, 3 people D 1 wk, 2 people
E 2 wks, 6 people
Begin
F 4 wks, 5 people
A 3 wks, 6 people End G 1 wk, 3 people
H 2 wks, people
I 2 wks, 4 people
C 1 wk, 2 people
t 9 wks
Method for resource levelling
(D) 2 (A) 8
(E) 6
(F) 5
(G) 3
(B) 3
(H) 4
(C) 2
(I) 4
11
9
6
15
14
9
5
5
5
Total workers scheduled
1
2
3
4
5
6
7
8
9
Weeks
The maximal-flow problem - in a network with one source node and one output node, the maximal flow problem seeks to find the maximal flow which can enter the network at the source node, flow through it, and exit at the output node in a given period of time.
The minimal-spanning tree problem - is concerned with finding a way to reach all the nodes in a network from some particular node (a source) in such a way that the total length of all the branches used is minimal.
Distances between nodes for laying water lines To node From node
1
2
3
4
5
6
7
1
0
1100
100
300
600
1000
400
2
1100
0
M
M
M
M
900
3
100
M
0
M
500
M
M
4
300
M
M
0
M
700
M
5
600
M
500
M
0
200
M
6
1000
M
M
700
200
0
800
7
400
900
M
M
M
800
0
M – is a node which cannot be connected
The length of the minimal spanning tree is the sum of all the circled lengths which is 2,400 feet. This will be the required length to connect all the homes. The shortest route problem - in the shortest route problem, we are trying to find the shortest route from a source to a destination through a connecting network; the destination maybe any node in a network.
B 300 250 D 200
A=
warehouse
100
Toronto 150
100 150
400
275
C
E
=F
THANK YOU! GOD BLESS! HAVE A NICE WEEKEND!
Objectives >Introduce the concepts of networks and networking technique as a solution models for complex project-scheduling problems. >Review in detail the concepts and use of PERT and PERT/COST to plan and control projects. >Show the use of CPM in the planning and control of projects. >Demonstrate how to schedule projects involving resource limitations.
Networks - Complex projects requires a series of activities, some of which must be performed sequentially and others that can be performed in parallel with other activities. This collection of series and parallel tasks can be modelled as a network.
PERT (Program Evaluation and Review Technique) - is a network model that allows for randomness in activity completion times. PERT was developed in the late 1950’s for the US Navy’s Polaris project having thousands of contractors. It has the potential to reduce both the time and cost required to complete a project.
Steps in the PERT Planning Process 1) Identify Activities and Milestones - activities are the tasks required to complete the project, milestones are the events marking the beginning and end of one or more activities. It is helpful to list the tasks in a table that in later steps can be expanded to include information on sequence and duration. 2) Determine Activity Sequence - this step may be combined with the activity identification step since the activity sequence is evident for some tasks. Other tasks mat require more analysis to determine the exact order in which they must be performed.
3) Construct the Network Diagram - using the activity sequence information, a network diagram can be can be drawn showing the sequence of the serial and parallel activities. For the original activity-on-arc model, the activities are depicted by arrowed lines and milestones are depicted by circles or “bubbles”.
4) Estimate Activity Times - a distinguishing feature of PERT is its ability to deal with uncertainty in activity completion times. For each activity, the model usually includes three time estimates: * Optimistic time (a) – the shortest time in which the activity can be completed. It is common practice to specify optimistic times to be three standard deviations from the mean so that there is approximately a 1% chance that the activity will be completed within the optimistic time. * Most likely time (m)– the completion time having the highest probability. Note that this time is different from the expected time. * Pessimistic time (b) – the longest time that an activity might require. Three standard deviations from the mean is commonly used for pessimistic time.
PERT assumes a beta probability distribution for the estimates. For a beta distribution, the expected time for each activity can be approximated using the following weighted average Expected time = (optimistic + 4 x most likely + pessimistic) / 6 t = a + 4m + b 6 Standard deviation of an activity = b – a 6 This expected time may be displayed on the network diagram.
To calculate the variance for each activity completion time, if three standard deviation times were selected for the optimistic and pessimistic times, then there are six standard deviations between them, so the variance is given by:
[ (pessimistic – optimistic) / 6 ] 2
5) Determine the Critical Path - critical path is determined by adding the times for the activities in each sequence and determining the longest path in the project. The critical path determines the total calendar time required for the project. If activities outside the critical path speed up or slow down (within limits), the total project time does not change. The amount of time that a non-critical path activity can be delayed without delaying the project is referred to as slack time.
If the critical path is not immediately obvious, it maybe helpful to determine the following four quantities for each activity: ES – Earliest start Time EF – Earliest Finish Time LS – Latest Start Time LF – Latest Finish Time
These times are calculated using the expected time for the relevant activities. ES/EF of each activity are determined by working forward through the network and determining the earliest time at which an activity can start and finish considering its predecessor activities. (Immediate Predecessor – activities that must immediately precede a given activity
LS/LF are the latest times that an activity can start and finish without delaying the project. Can be found by working backward through the network. The difference in the latest earliest time finish of each activity is that activity’s slack. The critical path then is the path through the networking which none of the activities have slack.
6) Update the Project Progress - make adjustment in the PERT chart as the project progress. As the project unfolds, the estimated times can be replaced with actual times. In cases where there are delays, additional resources mat be needed to stay on schedule and the PERT chart may be modified to reflect the new situation.
Using PERT to Plan the Introduction of a New HI-FI Speaker Activity list involved in the promotional campaign for the New Response 1000 speaker. Activity Symbol Activity Description
Immediate Predecesso rs
A
Develop the advertising plan (a detailed plan of projected radio, television, and newspaper advertising)
B
Develop the promotion and training materials plan (a detailed study of the materials that will be required for training the store managers and for the final in-store introduction)
C
Develop the training plan (the design of the training program that the store managers will undertake prior to the final in-store introduction)
D
Schedule the radio, television, and newspaper advertisements that will appear prior to the final introduction
A
E
Develop the advertising copy that will be required
A
F
A “Dummy” activity (one that takes no time) w/c lets us draw networks using only straight lines or which establishes precedence relationships (what activities precede each other)
G
Prepare promotion materials which will be used during the in-store introduction
B
H
Prepare materials which will be used in the training program for the store managers
B
I
Conduct the preintroduction advertising campaign in the media
D, F
J
Screen and select the store managers who will undergo training
C
K
Conduct the training program
L
The final in-store introduction of the Response 1000
H, J G, I, K
Drawing the network Nodes – circles represents the start and the finish of activities. Branches – arrows represents the activities in the project. Schedule radio, television, and newspapers advertisements
3
6 E
D
Preintroduction advertising campaign
F
Develop advertising copy
5
Develop the advertising plan
Dummy I
A
Develop the promotion and training materials plan
Prepare the in-store promotion materials
1
4
8
B
G
H Develop the training plan
K
Conduct the training program Screen and select participating store managers
7 J
9 L
Prepare training materials
C
2
Introduction of the Response 1000
Finding the critical path (longest path) Path – is defined as a sequence of connected activities that leads from the beginning of the project (node 1) to the end of the project (node 9). Activity
a (most m (most likely optimistic time) time)
b (most pessimistic time)
(a+4m+b)/6 (b - a)/6 (activity (expected time) std dev)
A
1
2
3
2
.33
B
1
2
3
2
.33
C
1
2
3
2
.33
D
1
2
9
3
1.33
E
2
3
10
4
1.33
(Dummy activity)
0
0
F
G
3
6
15
7
2.00
H
3
5
14
6
2.00
I
1
4
7
4
1.00
J
4
9
20
10
2.67
K
1
2
9
3
1.33
L
4
4
4
4
0
The Earliest-Start-Time-Rule (All earliest start (ES) and all earliest finish (EF) times) Formula : Earliest finish time = Earliest start time + Expected time EF = ES + t 2
t=3
5
3
6 2
E
2
D
6
t=4
6
F
5 t=2
6
t=0
t=4
6
I
A
10 0
0
t=2
2
1
2
t=7
9
4
15
8
B
2
G 15
H
t=6
C
K
8 2 2
t = 10
2
12
7 J
12
t=3
19
9 L
0
t=2
t=4
The-Latest-Finish-Time-Rule (All latest start (LS) and all latest finish (LF)) Formula : Latest start time = latest finish time – expected time LS = LF - t 8
t=3
11
3
11
6 7
E
7
D
11
t=4
11 F
5 t=2
t=0
t=4
11
I
A
15 5
4
t=2
6
1
8
t=7
15
4
15
8
B
6
G 15
H
t=6
C
K
12 2 2
t = 10
2
12
7 J
12
t=3
19
9 L
0
t=2
t=4
Determination of critical path for Response 1000 Activity
Earliest Start Latest Start Earliest Finish
Latest Finish
Slack (LS–ES or Activity on LF-EF) Critical Path
A
0
5
2
7
5
B
0
4
2
6
4
C
0
0
2
2
0
D
2
8
5
11
6
E
2
7
6
11
5
F
Yes
(Dummy activity)
G
2
8
9
15
6
H
2
6
8
12
4
I
6
11
10
15
5
J
2
2
12
12
0
Yes
K
12
12
15
15
0
Yes
L
15
15
19
19
0
Yes
Listed below are the useful information provided by using PERT about the Response 1000 project : 1) The expected project completion time is 19 weeks. 2) Activities C, J, K, and L are on the critical path, they must be watched more closely that the others, for if they fall behind, the whole project falls behind. 3) If extra effort is needed to finish the project on time, and if resources on one activity can possibly be used on another to reduce time, it can be borrow formanother activity except from th critical path. 4) Activities not on the critical path can fall behind by varying amounts without causing the project to be late.
CPM (Critical Path Method) - the Critical path method of planning and controlling projects has enjoyed the widest use among all the systems that follow the networking principle. The fundamental departure of CPM from PERT is that CPM brings the concept of cost more prominently into the planning and control process. When time can be estimated and cost can be calculated rather accurately in advance , CPM maybe superior to PERT. But when there is a extreme degree of uncertainty and when control over time outweighs control over costs, PERT may well be the better choice. The networking principles used in CPM are like those in the PERT system.
Estimating Time in CPM 1)Normal estimate of time approximates the most likely time estimate in PERT. Normal cost is associated with finishing the project in the normal time. 2)Crash time estimate is the time that would be required if no costs were spared in reducing the project time. Crash cost is the cost associated with doing job on a crash basis so as to minimize completion time.
Crashing a project - to crash a project successfully, note its activities and compare normal costs with crash costs for each activity. Goal is to find those activities on the critical path where time can be cut substantially with minimum extra cost spent. It’s goal is the greatest reduction in project time for the least increase in project cost.
PERT/Cost - PERT and CPM were both time-oriented, that is, they were design to allowed project planners to produce time schedules for the planning and monitoring of complex projects. In neither case was cost a major consideration. Earlier users of PERT and CPM noticed the need of this technique to concern themselves with project cost control as well as time control; and in the early 1960’s after the publication of a US government manual DOD and NASA Guide, PERT/Cost Systems Design, most military and research contracts required the use of PERT/cost on the part of the contractor. Today, there are many different project cost accounting technique
1) Costing by activities - completion time and activities are limited. 2) Estimating project costs by activity - managers should know the amounts of money that are to be expected for each activity over the planned duration of the project; one usually assumes that expenditures of each activity are made at a constant rate during that activity.
Activity information of for nine activity project network Activity
ES
LS
Duration (month)Total Cost ($)
Cost / month ($)
A
0
0
3
30,000
10,000
B
0
8
2
200,000
100,000
C
3
9
1
40,000
40,000
D
3
3
4
20,000
5,000
E
7
7
5
75,000
15,000
F
4
10
2
100,000
50,000
G
4
10
1
75,000
75,000
H
12
12
3
18,000
6,000
I
5
11
4
240,000
60,000
$798,000
D t=4
2
4 E
$20,000
A
t=5
t=3
$75,000
C
$30,000
$40,000
t=1
H t=3
1
B
F
t=2
t=2
$200,000
5
7 $18,000
$100,000
3
$240,000 $75,000
t=4 t=1 G
I
6
3) Project budgeting choices - from technological point of view, the project director can choose when to begin each activity in this project or he could wait to begin until each activity until it’s latest start time. What is the difference?
Project cost with early starts (cost in thousand $) 1
2
A
10
10
B
100
100
3
4
5
6
7
8
9
10
11
12
13
14
15
10
C
40
D
5
5
5
5
E
15
F
50
G
75
15
15
15
15
50
H I
60
60
60
60
6
6
6
Total 110
110
10
45
130
115
65
75
75
15
15
15
6
6
6
Acc 110 total
220
230
275
405
520
585
660
735
750
765
780
766
792
798
Project cost with late starts (cost in thousand $) 1
A
10
2
10
3
4
5
6
7
8
9
10
11
12
13
14
15
10
B
100
C
100 40
D
5
5
5
5
E
15
15
15
15
15
F
50
50
G
75
H I
6
6
6
60
60
60
60
Total 10
10
10
5
5
5
5
15
115
155
140
125
66
66
66
Acc 10 total
20
30
35
40
45
50
65
180
335
475
600
666
732
798
Network Scheduling with resource limitations Problem: Required workers to complete the activity for 9 weeks are 15 persons, but only 9 persons are available. B 2wks, 3 people D 1 wk, 2 people
E 2 wks, 6 people
Begin
F 4 wks, 5 people
A 3 wks, 6 people End G 1 wk, 3 people
H 2 wks, people
I 2 wks, 4 people
C 1 wk, 2 people
t 9 wks
Method for resource levelling
(D) 2 (A) 8
(E) 6
(F) 5
(G) 3
(B) 3
(H) 4
(C) 2
(I) 4
11
9
6
15
14
9
5
5
5
Total workers scheduled
1
2
3
4
5
6
7
8
9
Weeks
The maximal-flow problem - in a network with one source node and one output node, the maximal flow problem seeks to find the maximal flow which can enter the network at the source node, flow through it, and exit at the output node in a given period of time.
The minimal-spanning tree problem - is concerned with finding a way to reach all the nodes in a network from some particular node (a source) in such a way that the total length of all the branches used is minimal.
Distances between nodes for laying water lines To node From node
1
2
3
4
5
6
7
1
0
1100
100
300
600
1000
400
2
1100
0
M
M
M
M
900
3
100
M
0
M
500
M
M
4
300
M
M
0
M
700
M
5
600
M
500
M
0
200
M
6
1000
M
M
700
200
0
800
7
400
900
M
M
M
800
0
M – is a node which cannot be connected
The length of the minimal spanning tree is the sum of all the circled lengths which is 2,400 feet. This will be the required length to connect all the homes. The shortest route problem - in the shortest route problem, we are trying to find the shortest route from a source to a destination through a connecting network; the destination maybe any node in a network.
B 300 250 D 200
A=
warehouse
100
Toronto 150
100 150
400
275
C
E
=F
THANK YOU! GOD BLESS! HAVE A NICE WEEKEND!
