ps with notes required to tackelt project

project

1. IEOR 44051
Basic Project Scheduling

2. IEOR 44052
Overview
Project
Scheduling
No resource
Constraints
Resource
Constraints
Critical Path
Method (CPM)
Program Evaluation
and Review Technique
(PERT)
Heuristic Resource
Leveling
Integer Programming
Formulations

3. IEOR 44053
Planning a Concert
Task Predecessors
APlan concert -
BAdvertise A
CSell tickets A
DHold concert B, C

4. IEOR 44054
Changing a Tire
Task Predecessors
ARemove flat tire from wheel-
BRepair puncture on flat tireA
CRemove spare from trunk -
DPut spare on wheel A, C
EPlace repaired tire in trunkB, C

5. IEOR 44055
Job on Node Network
ABE
DC
❚Concert planning
-chapati
're
7

6. IEOR 44056
Critical Path Method (CPM)
❚Think of unlimited machines in parallel
❚… and njobs with precedence constraints
❚Processing times pjas before
❚Objective to minimize makespan
•
averaging
•
longestpath

7. IEOR 44057
Critical Path Method
❚Forward procedure:
❙Starting at time zero, calculate the earliest
each job can be started
❙The completion time of the last job is the
makespan
❚Backward procedure
❙Starting at time equal to the makespan,
calculate the latesteach job can be started
so that this makespan is realized

8. IEOR 44058
Forward Procedure
Step 1:
Set at time t = 0for all jobs jwith no predecessors,
Sj=0and set Cj= pj.
Step 2:
Compute for each job j
Cj= Sj+ pj.
Step 3:
The optimal makespan is
STOP
,max
'
all
'
k
jk
j
CS
®
=
{ }
''
2
'
1max ,...,,max
nCCCC=
as

9. IEOR 44059
Backward Procedure
Step 1:
Set at time t = Cmaxfor all jobs jwith no successors,
Cj= Cmaxand set Sj= Cmax-pj.
Step 2:
Compute for each job j
Sj= Cj-pj.
Step 3:
Verify that
STOP
}.,...,min{0
''''
1 nSS=
,min
''
all
''
k
jk
j
SC
®
=

10. IEOR 440510
Comments
❚The forward procedure gives the earliest
possible completion time for each job
❚The backwards procedures gives the latest
possible completion time for each job
❚If these are equal the job is a critical job.
❚If these are different the job is a slack job,
and the difference is the float.
❚A critical pathis a chain of jobs starting at
time 0 and ending at Cmax.

11. IEOR 440511
Example
j1234567891011121314
pj569127121061097875
1
2
3
69
58
47
11
10
1214
13

12. IEOR 440512
Forward Procedure
51+5=56
56
max=C
1
2
3
69
58
47
11
10
1214
13
5
5+6=1111+12=2323+10=33
5+9=14
14+12=26
14+7=21
26+10=36
26+6=32
36+7=4343+7=50
33+9=42
43+8=51
j1234567891011121314
pj569127121061097875
earliest
Completion
time
.
S
ng
agog
If
I
@
←
as a
-
-
•
←②
•
-
go
.
..
÷
.
-
it
•
S
7
-

13. IEOR 440513
Backwards Procedure
1
2
3
69
58
47
11
10
1214
13
14-9=5
24-12=1234-10=2443-9=34
26-12=14
36-10=26
35-10=26
43-7=36
43-7=36
51-8=4356-5=51
51-8=43
56-5=5156
j1234567891011121314
pj569127121061097875
What
is
the
latest
a
job
cancompute
in
'
thief
-
- - -
O
fifty?
(
56
)
Dfg
-
BEE
÷
.
•%o.÷
.
÷÷÷÷÷÷
.
36-6-30

14. IEOR 440514
1691214
Critical Path
2
3
58
47
11
10
13
12$k€04129
A
0%90*0
ear Gist
-
E-At
.
-
D
shadow
uhatisthemnamant
spent
to
reduce
Cmax
to55
.

15. IEOR 440515
Variable Processing Times

16. IEOR 440516
Time/Cost Trade-Offs
❚Assumed the processing times were fixed
❚More money Þshorter processing time
❚Start with linear costs
❚Processing time
❚Marginal cost
maxmin
jjj ppp ££ minmax
jj
b
j
a
j
j
pp
cc
c
-
-
=
r
General
!
[
specificmodel

17. IEOR 440517
Linear Costs
Resources (money)
Processing
time
max
jp
a
jcb
jcmin
jp
Cj
20-12
20
•
O
¥4
$127
$166
X
saws
12
•
O
- -
§ B

18. IEOR 440518
Solution Methods
❚Objective: minimum cost of project
❚Time/Cost Trade-Off Heuristic
❙Good schedules
❙Works also for non-linear costs
❚Linear programming formulation
❙Optimal schedules
❙Non-linear version not easily solved

19. IEOR 440519
Sources, Sinks, and Cuts
Source (dummy) node
Sink node
Minimal cut set
Cut set
t.0D.a.to
.
.:*
.

20. IEOR 440520
Time/Cost Trade-Off Heuristic
Step 1:
Set all processing times at their maximum
Determine all critical paths with these processing times
Construct the graph Gcpof critical paths
Continue to Step 2
max
jjpp=
(
spend
min
amtotmeoey
)

21. IEOR 440521
Time/Cost Trade-Off Heuristic
Step 2:
Determine all minimum cut sets in Gcp
Consider those sets where all processing times are larger
than their minimum
If no such set STOP; otherwise continue to Step 3
cpjj Gjpp Î">,
min
Minimalcutset
in
Gop
AS
a
setofnodes
tht
death
reduce
to
reduce
Cmax

22. IEOR 440522
Time/Cost Trade-Off Heuristic
Step 3:
For each minimum cut set:
Compute the cost of reducing all processing times by one
time unit.
Take the minimum cut set with the lowest cost
If this is less than the overhead per time unit go on to Step
4; otherwise STOP

23. IEOR 440523
Time/Cost Trade-Off Heuristic
Step 4:
Reduce all processing times in the minimum cut set by
one time units
Determine the new set of critical paths
Revise graph Gcpand go back to Step 2

24. IEOR 440524
Example
j 11 2 3 4 5 6 7 8 9 10 11 12 13 14
Pj max 5 6 9 12 7 12 10 6 10 9 7 8 7 5
Pj min 3 5 7 9 5 9 8 3 7 5 6 5 5 2
c
j
a
20 25 20 15 30 40 35 25 30 20 25 35 20 10
c
j 7 2 4 3 4 3 4 4 4 5 2 2 4 8


-
a
&
-
-
→
-
g
Id
ago

25. IEOR 440525
Maximum Processing Times
1
2
3
69
58
47
11
10
1214
13

26. IEOR 440526
Maximum Processing Times
1
2
3
69
58
47
11
10
1214
13
56
max=C
55

27. IEOR 440527
Critical Path Subgraph (Gcp)
1
3
69
11
1214
C1=7
C3=4
C6=3C9=4
C11=2
C12=2C14=8
Minimum cut
set with lowest cost
Cut sets: {1},{3},{6},{9},
{11},{12},{14}.
-
O

28. IEOR 440528
Critical Path Subgraph (Gcp)
1
3
69
11
1214
C1=7
C3=4
C6=3C9=4
C11=2
C12=2C14=8
13
Cut sets: {1},{3},{6},{9},
{11},{12,13},{14}.
C13=4
Minimum cut
set with lowest cost
$2
Gmat58
$2
Came
5744
' g
p
9
'
D
F

29. IEOR 440529
Critical Path Subgraph (Gcp)
1
3
69
11
1214
C1=7
C3=4
C6=3C9=4
C11=2
C12=2C14=8
13
C13=4
247
10
C2=2C4=3C7=4
C10=5
This set cannot be decreased,
Choose 2 and 6 instead
Heuristic
.
It
.
maynot
'
competethe
.fm/n$mg,kgpg$4$qGgaxe5YAnaxe53
$0
.
÷
14,63
{GIG
41413)H)

30. IEOR 440530
Linear Programming
Formulation
Objective is weighted avg. of makespan and cost
❚Here total cost is linear
❚Want to minimize
( )å
=
-++
n
j
jjj
b
j ppccCc
1
max
max0
å
=
-
n
j
jjpcCc
1
max0 .
cost
timeGma
.dec
varis
pj
=
②time
host
$1
min
-0
.
•
in
.
:he:*
EH
"s
•n¥÷• g¥pj
"cos
pin
.
•
Pj

31. min
x
t
300
312
sit
.
1*-12)
X
312
-
12
111
minX
S
-
K
t2
472
)

32. IEOR 440531
Linear Program
Minimize
subject to
jpxC
jx
jpp
jpp
Akjxpx
jj
j
jj
jj
jjk
"³--
"³
"³
"£
ή"³--
,0
,0
,
,
,0
max
min
max
å
=
-
n
j
jjpcCc
1
max0 .
decrees
.
Pj
,
Cmax
*
or=
startto
otodsj
pree
.
•
*
s:÷
:
age
→
Cmax
3Xotp

33. Est
-
TinTradeoffHerr
vs
.
LLP
pablo
by
-
LP
is
slower
-
LP
requires
that
youknow
co
($1
mis
)
-
up
regex
that
costthe
beer
tradeoff
-
LPactuallycompetes
an
aptsdtn
If
yer
meetthecriteriaabove
.
CPM
-
criticalpath
method
.

34. IEOR 440532
PERT

35. IEOR 440533
Program Evaluation and
Review Technique (PERT)
❚Assumed processing times deterministic
❚Processing time of jrandom with mean
µjand variance sj2.
❚Want to determine the expected
makespan
❚Assume we have
pja= most optimistic processing time
pjm= most likely processing time (mode)
pjb= most pessimistic processing time
-[

36. IEOR 440534
Expected Makespan
❚Estimate expected processing time
❚Apply CPM with expected processing times
❚Let Jcpbe a critical path
❚Estimate expected makespan
6
4
bma
j
jjj
ppp ++
=µ
å
Î
=
cp
Jj
j
CE µ)(
ˆ
max
I÷÷÷÷÷
.
As
superriassumption
-
Li
pa
1pm
'
pb
d-

37. IEOR 440535
Distribution of Makespan
❚Estimate the variance of processing times
❚and the variance of the makespan
❚Assume it is normally distributed
6
2
ab
j
jj
pp-
=s å
Î
=
cp
Jj
j
CV
2
max
)(
ˆ
s

38. -
takedistributionforeachjob
-
compile
expectedtieofeachjob
-
pretendthose
are
deterministictie
-
run
CPM
(
mini
,
mode
,
Max
)
Cisl
,
I
)
I
,
5,20
)
p
-
-
H4f5H2I
-
O
→⑦
.
=
411617
Its
,
so
)
"¥
④
<z
e-ope8
PERTi
.

39. 2
nov
.
Xi
,
K
livery
ofexpectation
ECXitXDECXDTECXDE.IE#xDExrexaD
PRRtassune~Elmaxcx.x.D-maolEHD.EU

40. O
→
O
'
3=10
wi
Prez
PozoWIPE
's
40¥
:
:
PERT
gonif
DOECmaxes
what
is
Eochaidfor
a
8
Ego
ECCmaD
0-00¥
=4Dt¥h⑧HgHHgDD
8*0
"
gtfo
=7,5
<z
*
do

41. 0¥:&
;÷÷::÷÷÷÷
RestEGma¥1
RealityEchard
HOO

42. IEOR 440536
Discussion
❚Potential problems with PERT:
❙Always underestimates project duration
❘other paths may delay the project
❙Non-critical paths ignored
❘critical path probability
❘critical activity probability
❙Activities are not always independent
❘same raw material, weather conditions, etc.
❙Estimates by be inaccurate
•
M

43. IEOR 440537
Discussion
❚No resource constraints:
❙Critical Path Method (CPM)
❙Simple deterministic
❙Time/cost trade-offs
❘Linear cost (heuristic or exact)
❘Non-linear cost (heuristic)
❙Accounting for randomness (PERT)

44. IEOR 440538
Adding Resource
Constraints
expensive
machines
e.g.
build
our
renewable
-
reusable
non-renewable
-
dynamite

45. IEOR 440539
Resource Constraints
❚Renewable resources
❚Very hard problem
❚No LP
❚Can develop an IP
❚Let job n+1 be dummy job (sink) and
î
í
ì
=
otherwise.0
at time completed is job if1 tj
x
jt
'
input
:
DAG
,
Pj
r
resources
:
Ro
is
the
amount
of
resource0Rij
:
theAment
of
resourceis
that
gets
j
needs

46. 9=2
Cma
#
Y
'
•
•
g<z
add
resourcesBrceannrtrvnREA
simultaneouslyR.pe/Rie=ICmaxzG
-
needR
,

47. IEOR 440540
Makespan
❚Let Hbound the makespan, e.g.
❚Completion time of job jis
and the makespan
å
=
=
n
j
jpH
1
å
=
×
H
t
jt
xt
1å
=
+
×
H
t
tn
xt
1
,1
Xjt
-
EEE
xx
-
Crip
=
-

48. IEOR 440541
IP Formulation
Minimize
Subject to
å
=
+
×
H
t
tn
xt
1
,1
t⋅xjtt=1
H∑ +pk−txktt=1
H∑≤0
Rijxjuu=t
t+pj−1∑%&'' ()**i=1
n∑ ≤Rjxjtt=1
H∑=1
If j prec k
For each job
Each resource
Used at each
time t
bing.io#attviet,foreaaRi
g.
① f%÷¥
Ri
la
:sE←j⑥
.
.

49. I
¥¥<z
.
EDI
uhxhjdx
are
running
atTinit
anyjob
jwhosecompletion
tire
is
in
theinterval
Ct
,
ttp
;]

50. IEOR 440542
In Practice
❚The IP cannot be solved
❚(Almost) always resource constraints
❚ÞHeuristic:
Resource constraint ®Precedence constraint
❚Example: pouring foundation and sidewalk
❙both require same cement mixer
❙delaying foundation delays building
❙precedence constraint: pour foundation first
❙not a logical constraint

51. IEOR 440543
Optimality of Heuristic
❚Say njobs need the same resource
❚Could otherwise all be done simultaneously
❚Add (artificial) precedence constraints
❚Have n! possibilities
❚Will we select the optimal sequence?
2 3 4 5 6
2 6 24120720

52. IEOR 440544
Decision Support
❚Resource leveling
❙Solve with no resource constraints
❙Plot the resource use as a function of time
❙If infeasible suggest precedence
constraints
❘Longest job
❘Minimum slack
❙User adds constraints
❙Start over

53. IEOR 440545
Example: One Resource
Uses resource
3
611
66
2
9
Time
10 20 30
Resource ProfileCapacity
Are