网络计划技术第十章第十章 网络计划技术
第一节 概述
第二节 双代号网络图
第三节 网络时间参数与关键路线
第四节 非确定型网络的完工期评价和预测
第五节 网络优化技术第一节 概 述一、网络计划技术的发展
1917年，亨利?甘特发明了著名的甘特图，使项目经理按日历制作任务图表，用于日常工作安排,
一、网络计划技术的发展
1957年,杜邦公司将关键路径法
（ CPM） 应用于设备维修,使维修停工时间由 125小时锐减为 7小时；
1958年,在北极星导弹设计中,
应用计划评审技术 （ PERT）,将项目任务之间的关系模型化,使设计完成时间缩短了 2年 。
二、网络计划技术的分类
根据活动和事件的表示方法
——双代号网络和单代号网络
根据网络图的时间值类型
——确定型网络和不确定型网络
根据事项与工序的相互关系是否确定
——结构确定网络和随机网络第二节 双代号网络图一、双代号网络图 ——构成活动 ——“→,
事项 ——“〇,
虚工序 ——,”
线路 — 从网络始点事项开始,顺着箭线方向,到网络终点为止,中间由一系列首尾相连的节点和箭线构成的通路 。
二、双代号网络图的绘制规则
不能出现循环线路；
任一节点可与许多箭线相连,但两节点之间只能有 唯一 的一条箭线；
箭线的首尾必须都有节点；
任何一个网络图只能有一个始点和一个终点；
二、双代号网络图的绘制规则
每道工序只能出现一次；
箭线方向一律指向或斜向右方,沿箭线方向节点编号由小到大；
正确反映工序之间的逻辑关系 。
绘制网络图应注意的问题
冗余关系问题
——两道工序之间存在不必要的紧前或紧后关系 。
网络图的分解与综合
——视工序多少,范围大小而定绘制网络图应注意的问题
虚工序问题
——仅用于表明平行工序间的逻辑关系；
——虚工序越少越好 。
判断虚工序是否必要：
——虚工序箭头箭尾连接的两道工序是否源于同一节点；
——虚工序箭头箭尾连接的两道工序不源于同一节点,且不能表示共同完工 。
绘制网络图应注意的问题绘制网络图应注意的问题
网络图的布局
—— 使网络图简便易读；
—— 不改变逻辑关系的情况下合理安排工序间的相对位置,尽量避免箭线交叉 。
第三节 网络时间参数与关键路线一、工序作业时间的确定
最乐观时间：在最顺利的情况下，
完成某道工序的最短时间,a；
最保守时间：在最不顺利的情况下，
完成某道工序的最长时间,b；
一、工序作业时间的确定
最可能时间：在正常情况下,完成某道工序的时间,m。
工序事件的期望值,
6
4
),(
bma
jit e
二、网络时间参数的迭代计算得最晚结束时间工序得最晚开始时间工序的最早结束时间工序的最早开始时间工序的最迟时间节点的最早时间节点作业时间工序
),(),(
),(),(
),(),(
),(),(
)(
)(
),(),(
jijiLF
jijiLS
jijiEF
jijiES
iiLT
iiET
jijit
节点的最早时间
——以该节点为起始节点的所有工序的最早开始时间 。
网络始点的最早时间为 0；
01?)(ET
二、网络时间参数的迭代计算其它节点的最早开始时间 = 沿网络方向指向该节点的节点的最早开始时间 累加取大
)}j,i(t)i(ET{m a x)j(ET
ji
节点的最晚时间
——以该节点为终点的所有工序的最迟必须结束时间 。
网络终点的最晚时间等于网络终点的最早时间；
)()( nETnLT?
箭尾的最晚时间等于所有从该节点直接出发的各箭头节点的最晚时间与该箭头所表示工序作业时间之差的最小值 。
)},()({m i n)( jitjLTiLT
ji
工序的最早开始时间
——工序在其所有紧前工作都结束后的最早可能开始时间 。
)(),( iETjiES?
工序的最早结束时间
——工序的最早可能结束时间,即工序最早可能开始时间与工序作业时间之和
),(),(),( jitjiESjiEF
工序的最晚开始时间
——为了不影响项目以及最短时间完工,工序最晚必须开始的时间 。
)(),( jLTjiLF?
工序的最晚结束时间
——以该节点为终点 的所有工序的最晚必须结束时间 。
),(),(),( jitjiLFjiLS
三、时差与关键路径
工序总时差
——在不影响整个项目 最早结束 的条件下,工序最早开始 （ 结束 ）
可以推迟的的时间 。
),()(),(
),(),(
),(),(),(
jitiETjiLT
jiEFjiLF
jiESjiLSjiTF
工序单时差
——在不影响紧后工序 最早开始 时间的前提下,该工序可以推迟开始或结束的时间 。
),()(
),()()(),(
jiEFjET
jitiETjETjiFF
关键路线
由总时差为 0的工序组成的线路,
关键路线上各工序作业时间之和即为总工期 。
关键路线是网络图的最长路；
关键路线的长度决定了工期；
关键路线可能不止一条；
关键路线缩短到一定程度可以变成非关键路线,非关键路线的总时差被全部利用后也会变成关键路线 。
关键路线第四节 非确定型网络的完工期评价和预测
一般认为,非确定型网络的工序时间服从 分布 。
工序时间期望
工序时间方差
)4(61 bmat e
22 )(
36
1 ab
假设前提
各道工序的作业时间是相互独立的随机变量；
工期服从正态分布；
关键路线上工序多时,依中心极限定理,工期服从正态分布；
关键路线上工序数目少时,由于每道工序工序的作业时间服从分布,可近似看作正态分布；
任何情况下,根据工序作业时间的期望值确定的关键路线长度总比其它路线的长度长 。
非确定型网络的计算
非确定型网络关键路线的工期仅表示工程的期望值,并非确定值 。
非确定型网络线路的长度服从的正态分布； )),(,),((
),(
2
),(
PjiPji
e jijit?
要求工期在 时间内完成，则实现的概率为：
为关键线路
T
}{}{
'
'
'
'
p
p
p
p TETTExPTxP
'p
求已知工期内的完工概率
找出从始点到终点的所有线路；
求出每天线路长度的期望值和方差；
求出已知工期在每条线路上实现的概率；
所有线路上实现的概率中选最小的作为工程项目在已知工期内的完工概率 。
给定项目完工概率，求项目工期
找出从开始点到终点的所有线路；
求出每条线路长度的期望值和方差；
根据每条线路求出一个实现的工期；
选择最长的工期作为项目实现给定完工概率的工期 。
注意：
单纯按工序作业时间的期望值标出的关键路线进行评价和工期预测的根据是不充分的；
某些情况下,非关键路径可以转化为关键路径 。
一、缩短工期
缩短关键工序作业时间
推延非关键工序的开始时间,调出资源支援关键工序；
第五节 网络优化技术
保证非关键工序不会成为关键工序的前提下,适当延长非关键工序的作业时间,调出资源支援关键路线；
赶工期的条件下,从计划外调拨资源支持关键工序,缩短工期 。
一、缩短工期
调整网络结构
组织平行作业；
组织平行交叉作业 。
二、资源有限、工期最短
建立精确的数学模型
启发式算法
最小时差法；
负荷均衡法；
遗传算法；
二、资源有限、工期最短最小时差法：
根据作业清单绘制网络图,计算网络图的时间参数,确定关键路线及其长度；
对工序进行编号；
最小时差法
按编号由小到大的顺序将其资源需要量进行累加,直到资源需要量欲超过可能供应的资源为止；
检查调整,直至不存在资源需要量超过规定供应限度的情况 。
三、工期确定、资源均衡
主要是启发式算法
假设前提
关键工序不能后移；
非关键工序的后移量不能超过其总时差 。
三、工期确定、资源均衡
根据作业清单绘制网络图,计算网络时间参数,确定关键路线及其长度；
假定单位时间资源供应量 LR比现有资源需求量的峰值略小,从最初时段开始检查,如果某时段内需求量超过 LR,则进行调整；
所有时段调整完后,返回第二步,
令资源供应量比新的资源需求量最高峰小,重新进行调整,直到不能调整为止 。
三、工期确定、资源均衡调整资源需求量的方法
若工序内部不允许中断,则某时段内,对所有在 时刻开始的工序,
如果满足 则该工序可以后移 。 如果多道工序满足以上条件,按下述原则进行：
kt
1),( ktjiLS
kt
优先推迟资源需求量最大的工序；
若所有资源需求量相等,优先推迟总时差大的工序；
工序内部允许中断,则在 处将工序分段,按上述办法调整资源需求量 。
调整资源需求量的方法四、工期缩短、成本最低
网络优化的目的就是要找出成本曲线的最低点
T ( 工 期 )
成 本
C
C
*
T
*
直 接 费 用间 接 费 用成 本
C
A
C
B
T
A
T
B
B
A
T 工 期成本工期缩短、成本最低的网络优化方法
计算各工序的时间费用率，并以各工序的正常时间作为作业时间求出每一道工序的时间参数及时差，找出关键工序；
选择关键工序中直接费用率最小而且允许压缩的时间大于零的工序作为被压缩工序；
根据压缩后的作业时间重新计算各工序总时间差及允许压缩时间，依据上一步确定被压缩工序及压缩量。
工期缩短、成本最低的网络优化方法
Thank You!
That’s all！
第一节 概述
第二节 双代号网络图
第三节 网络时间参数与关键路线
第四节 非确定型网络的完工期评价和预测
第五节 网络优化技术第一节 概 述一、网络计划技术的发展
1917年，亨利?甘特发明了著名的甘特图，使项目经理按日历制作任务图表，用于日常工作安排,
一、网络计划技术的发展
1957年,杜邦公司将关键路径法
（ CPM） 应用于设备维修,使维修停工时间由 125小时锐减为 7小时；
1958年,在北极星导弹设计中,
应用计划评审技术 （ PERT）,将项目任务之间的关系模型化,使设计完成时间缩短了 2年 。
二、网络计划技术的分类
根据活动和事件的表示方法
——双代号网络和单代号网络
根据网络图的时间值类型
——确定型网络和不确定型网络
根据事项与工序的相互关系是否确定
——结构确定网络和随机网络第二节 双代号网络图一、双代号网络图 ——构成活动 ——“→,
事项 ——“〇,
虚工序 ——,”
线路 — 从网络始点事项开始,顺着箭线方向,到网络终点为止,中间由一系列首尾相连的节点和箭线构成的通路 。
二、双代号网络图的绘制规则
不能出现循环线路；
任一节点可与许多箭线相连,但两节点之间只能有 唯一 的一条箭线；
箭线的首尾必须都有节点；
任何一个网络图只能有一个始点和一个终点；
二、双代号网络图的绘制规则
每道工序只能出现一次；
箭线方向一律指向或斜向右方,沿箭线方向节点编号由小到大；
正确反映工序之间的逻辑关系 。
绘制网络图应注意的问题
冗余关系问题
——两道工序之间存在不必要的紧前或紧后关系 。
网络图的分解与综合
——视工序多少,范围大小而定绘制网络图应注意的问题
虚工序问题
——仅用于表明平行工序间的逻辑关系；
——虚工序越少越好 。
判断虚工序是否必要：
——虚工序箭头箭尾连接的两道工序是否源于同一节点；
——虚工序箭头箭尾连接的两道工序不源于同一节点,且不能表示共同完工 。
绘制网络图应注意的问题绘制网络图应注意的问题
网络图的布局
—— 使网络图简便易读；
—— 不改变逻辑关系的情况下合理安排工序间的相对位置,尽量避免箭线交叉 。
第三节 网络时间参数与关键路线一、工序作业时间的确定
最乐观时间：在最顺利的情况下，
完成某道工序的最短时间,a；
最保守时间：在最不顺利的情况下，
完成某道工序的最长时间,b；
一、工序作业时间的确定
最可能时间：在正常情况下,完成某道工序的时间,m。
工序事件的期望值,
6
4
),(
bma
jit e
二、网络时间参数的迭代计算得最晚结束时间工序得最晚开始时间工序的最早结束时间工序的最早开始时间工序的最迟时间节点的最早时间节点作业时间工序
),(),(
),(),(
),(),(
),(),(
)(
)(
),(),(
jijiLF
jijiLS
jijiEF
jijiES
iiLT
iiET
jijit
节点的最早时间
——以该节点为起始节点的所有工序的最早开始时间 。
网络始点的最早时间为 0；
01?)(ET
二、网络时间参数的迭代计算其它节点的最早开始时间 = 沿网络方向指向该节点的节点的最早开始时间 累加取大
)}j,i(t)i(ET{m a x)j(ET
ji
节点的最晚时间
——以该节点为终点的所有工序的最迟必须结束时间 。
网络终点的最晚时间等于网络终点的最早时间；
)()( nETnLT?
箭尾的最晚时间等于所有从该节点直接出发的各箭头节点的最晚时间与该箭头所表示工序作业时间之差的最小值 。
)},()({m i n)( jitjLTiLT
ji
工序的最早开始时间
——工序在其所有紧前工作都结束后的最早可能开始时间 。
)(),( iETjiES?
工序的最早结束时间
——工序的最早可能结束时间,即工序最早可能开始时间与工序作业时间之和
),(),(),( jitjiESjiEF
工序的最晚开始时间
——为了不影响项目以及最短时间完工,工序最晚必须开始的时间 。
)(),( jLTjiLF?
工序的最晚结束时间
——以该节点为终点 的所有工序的最晚必须结束时间 。
),(),(),( jitjiLFjiLS
三、时差与关键路径
工序总时差
——在不影响整个项目 最早结束 的条件下,工序最早开始 （ 结束 ）
可以推迟的的时间 。
),()(),(
),(),(
),(),(),(
jitiETjiLT
jiEFjiLF
jiESjiLSjiTF
工序单时差
——在不影响紧后工序 最早开始 时间的前提下,该工序可以推迟开始或结束的时间 。
),()(
),()()(),(
jiEFjET
jitiETjETjiFF
关键路线
由总时差为 0的工序组成的线路,
关键路线上各工序作业时间之和即为总工期 。
关键路线是网络图的最长路；
关键路线的长度决定了工期；
关键路线可能不止一条；
关键路线缩短到一定程度可以变成非关键路线,非关键路线的总时差被全部利用后也会变成关键路线 。
关键路线第四节 非确定型网络的完工期评价和预测
一般认为,非确定型网络的工序时间服从 分布 。
工序时间期望
工序时间方差
)4(61 bmat e
22 )(
36
1 ab
假设前提
各道工序的作业时间是相互独立的随机变量；
工期服从正态分布；
关键路线上工序多时,依中心极限定理,工期服从正态分布；
关键路线上工序数目少时,由于每道工序工序的作业时间服从分布,可近似看作正态分布；
任何情况下,根据工序作业时间的期望值确定的关键路线长度总比其它路线的长度长 。
非确定型网络的计算
非确定型网络关键路线的工期仅表示工程的期望值,并非确定值 。
非确定型网络线路的长度服从的正态分布； )),(,),((
),(
2
),(
PjiPji
e jijit?
要求工期在 时间内完成，则实现的概率为：
为关键线路
T
}{}{
'
'
'
'
p
p
p
p TETTExPTxP
'p
求已知工期内的完工概率
找出从始点到终点的所有线路；
求出每天线路长度的期望值和方差；
求出已知工期在每条线路上实现的概率；
所有线路上实现的概率中选最小的作为工程项目在已知工期内的完工概率 。
给定项目完工概率，求项目工期
找出从开始点到终点的所有线路；
求出每条线路长度的期望值和方差；
根据每条线路求出一个实现的工期；
选择最长的工期作为项目实现给定完工概率的工期 。
注意：
单纯按工序作业时间的期望值标出的关键路线进行评价和工期预测的根据是不充分的；
某些情况下,非关键路径可以转化为关键路径 。
一、缩短工期
缩短关键工序作业时间
推延非关键工序的开始时间,调出资源支援关键工序；
第五节 网络优化技术
保证非关键工序不会成为关键工序的前提下,适当延长非关键工序的作业时间,调出资源支援关键路线；
赶工期的条件下,从计划外调拨资源支持关键工序,缩短工期 。
一、缩短工期
调整网络结构
组织平行作业；
组织平行交叉作业 。
二、资源有限、工期最短
建立精确的数学模型
启发式算法
最小时差法；
负荷均衡法；
遗传算法；
二、资源有限、工期最短最小时差法：
根据作业清单绘制网络图,计算网络图的时间参数,确定关键路线及其长度；
对工序进行编号；
最小时差法
按编号由小到大的顺序将其资源需要量进行累加,直到资源需要量欲超过可能供应的资源为止；
检查调整,直至不存在资源需要量超过规定供应限度的情况 。
三、工期确定、资源均衡
主要是启发式算法
假设前提
关键工序不能后移；
非关键工序的后移量不能超过其总时差 。
三、工期确定、资源均衡
根据作业清单绘制网络图,计算网络时间参数,确定关键路线及其长度；
假定单位时间资源供应量 LR比现有资源需求量的峰值略小,从最初时段开始检查,如果某时段内需求量超过 LR,则进行调整；
所有时段调整完后,返回第二步,
令资源供应量比新的资源需求量最高峰小,重新进行调整,直到不能调整为止 。
三、工期确定、资源均衡调整资源需求量的方法
若工序内部不允许中断,则某时段内,对所有在 时刻开始的工序,
如果满足 则该工序可以后移 。 如果多道工序满足以上条件,按下述原则进行：
kt
1),( ktjiLS
kt
优先推迟资源需求量最大的工序；
若所有资源需求量相等,优先推迟总时差大的工序；
工序内部允许中断,则在 处将工序分段,按上述办法调整资源需求量 。
调整资源需求量的方法四、工期缩短、成本最低
网络优化的目的就是要找出成本曲线的最低点
T ( 工 期 )
成 本
C
C
*
T
*
直 接 费 用间 接 费 用成 本
C
A
C
B
T
A
T
B
B
A
T 工 期成本工期缩短、成本最低的网络优化方法
计算各工序的时间费用率，并以各工序的正常时间作为作业时间求出每一道工序的时间参数及时差，找出关键工序；
选择关键工序中直接费用率最小而且允许压缩的时间大于零的工序作为被压缩工序；
根据压缩后的作业时间重新计算各工序总时间差及允许压缩时间，依据上一步确定被压缩工序及压缩量。
工期缩短、成本最低的网络优化方法
Thank You!
That’s all！
